Golang Queue Implementation

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)