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)