Golang Queue Implementation


GO

Author: Tuan Nguyen
Reviewer: Deepak Prasad

In this tutorial, we will walk through some examples of queue implementation in Golang.

queue: In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. By convention, the end of the sequence at which elements are added is called the back, tail, or rear of the queue, and the end at which elements are removed is called the head or front of the queue, analogously to the words used when people line up to wait for goods or services. The operations of a queue make it a first-in-first-out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed.

Access methods of a queue:

  • enqueue: add a new element to a queue
  • dequeue: remove an element from a queue
  • isEmpty: check if the queue is empty or not
  • peek: return the first element of a queue

 

Queue implementation using a slice

Slice is all you need if you want a simple and easy-to-use FIFO queue.

package main

import "fmt"

func main() {
	queue := make([]int, 0)

	// enqueue
	queue = append(queue, 1)
	queue = append(queue, 5)
	queue = append(queue, 8)
	fmt.Println("enqueue:", queue)

	// peak
	peak := queue[0]
	fmt.Println("peak of the queue:", peak)

	// dequeue
	queue = queue[1:]
	fmt.Println("dequeue:", queue)

	// Is empty ?
	if len(queue) == 0 {
		fmt.Println("Empty queue!")
	} else {
		fmt.Println("Not an empty queue!")
	}
}

Output:

enqueue: [1 5 8]
peak of the queue: 1
dequeue: [5 8]
Not an empty queue!

Note that:

  • append will create a new array whenever there is not enough capacity to hold new elements
  • The issue with this implementation is that the amount of memory it takes up is proportional to the number of dequeue calls.
  • The memory allocated for the first element in the array is never returned.

Here is an fully example of implementing queue using slice and generics. With this way, you can custom your queue and add your own logic to queue, dequeue function:

package main

import "fmt"

func enqueueOps[T comparable](queue []T, element T) []T {
	queue = append(queue, element) //append to slice
	fmt.Println("Enqueue the element:", element)
	return queue
}

func dequeueOps[T comparable](queue []T) []T {
	element := queue[0] // return the first element
	fmt.Println("Dequeue the element :", element)
	return queue[1:]
}

func peakOps[T comparable](queue []T) T {
	element := queue[0] // return the first element
	return element
}

func isEmptyOps[T comparable](queue []T) bool {
	return len(queue) == 0
}

func main() {
	var queue []string // Make a queue of strings.

	queue = enqueueOps(queue, "first")
	queue = enqueueOps(queue, "second")
	queue = enqueueOps(queue, "third")

	fmt.Println("Queue:", queue)

	peak := peakOps(queue)
	fmt.Println("peak:", peak)

	queue = dequeueOps(queue)
	fmt.Println("Queue:", queue)

	isEmpty := isEmptyOps(queue)
	fmt.Println("is empty:", isEmpty)
}

Output:

Enqueue the element: first
Enqueue the element: second
Enqueue the element: third
Queue: [first second third]
peak: first
Dequeue the element : first
Queue: [second third]
is empty: false

 

Queue implementation using a linked list

To avoid memory leaks, we can use a dynamic data structure (linked list). The following is an example of code:

package main

import (
	"container/list"
	"fmt"
)

func main() {
	// new linked list
	queue := list.New()

	// enqueue
	queue.PushBack(36)
	queue.PushBack(49)
	queue.PushBack(42)

	// dequeue
	front := queue.Front()
	// remove the allocated memory so can avoid memory leaks
	queue.Remove(front)

	//peak
	peak := queue.Front()
	fmt.Println("peak:", peak.Value)

	// isEmpty
	fmt.Println("isEmpty:", queue.Len() == 0)
}

Output:

peak 49
isEmpty: false

 

Queue implementation using a buffered channel

This should be the default behavior for small queues that do not require persistence. Even if you're writing into an unbounded queue on disk, writing and reading from a channel is frequently a better option. Here is an example of implementing queue using a channel:

package main

import "fmt"

func main() {
	queueChan := make(chan int, 200)
	value1 := 5
	value2 := 4
	value3 := 6
	// enqueue
	queueChan <- value1
	queueChan <- value2
	queueChan <- value3

	// dequeue and return the value
	receice := <-queueChan
	fmt.Println("dequeue 1st time:  ", receice)
	receice2 := <-queueChan
	fmt.Println("dequeue 2nd time: ", receice2)

	if len(queueChan) == 0 {
		fmt.Println("Queue is empty")
	} else {
		fmt.Println("Queue is not empty")
	}
}

Output:

dequeue 1st time:   5
dequeue 2nd time:  4
Queue is not empty

Note that: while this is elegant, it lacks a peek() function, which sometimes required for queue implementation.

 

Summary

In this article, I demonstrated several approaches to queue implementation in Golang. To accomplish this, we can use slices, lists, or channels. We must select the appropriate implementation based on the situation and problems.

 

References

https://pkg.go.dev/container/list
https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

 

Tuan Nguyen

Tuan Nguyen

He is proficient in Golang, Python, Java, MongoDB, Selenium, Spring Boot, Kubernetes, Scrapy, API development, Docker, Data Scraping, PrimeFaces, Linux, Data Structures, and Data Mining. With expertise spanning these technologies, he develops robust solutions and implements efficient data processing and management strategies across various projects and platforms. You can connect with him on his LinkedIn profile.

Can't find what you're searching for? Let us assist you.

Enter your query below, and we'll provide instant results tailored to your needs.

If my articles on GoLinuxCloud has helped you, kindly consider buying me a coffee as a token of appreciation.

Buy GoLinuxCloud a Coffee

For any other feedbacks or questions you can send mail to admin@golinuxcloud.com

Thank You for your support!!

Leave a Comment