A queue plays a fundamental part in storing and managing the collection of elements in specific order. They follow the First-In-First-Out principle which means that the element that are added first are the one to be removed first.
You will find queues in a wide variety of use cases such as task scheduling and more.
In this tutorial, we will learn how to implement and work with queues in the Go programming language. This can help cement our knowledge of data structures.
What Is a Queue?
A queue is a linear data structure that operates in a sequential manner where the elements are added to the back which is also known as enqueue and removed from the front which is also known as dequeue of the queue.
This feature of a queue ensures that the oldest elements in the queue are processed first before the newly added ones.
Think of it as a line of people who are waiting for a service where the person who arrived first gets served first.
Some key characteristics of a queue include:
- FIFO (First-In-First-Out) – The first added element is the first one to be removed.
- Linear Structure – The elements in a queue are organized in linear format.
- Two Primary Operations – Queues support two primary operations: enqueue and dequeue.
Implement a Queue in Go
With the basics of queues out of the way, let us proceed and learn how to implement a queue in Go.
Using Slices
The most common method of implementing a queue in Go involves using a list. Let us look at an example as shown in the following:
import "fmt"
type Queue []int
func (q *Queue) Enqueue(val int) {
*q = append(*q, val)
}
func (q *Queue) Dequeue() (int, error) {
if len(*q) == 0 {
return 0, fmt.Errorf("queue is empty")
}
val := (*q)[0]
*q = (*q)[1:]
return val, nil
}
func main() {
q := Queue{}
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
for len(q) > 0 {
val, err := q.Dequeue()
if err != nil {
fmt.Println(err)
break
}
fmt.Printf("Dequeued: %d\n", val)
}
}
In the given example, we start by defining a new type called “Queue” which is basically a slice of integers. This allows us to represent a queue data structure.
We then define an enqueue method which is associated with the Queue type. The method takes an integer as an argument and adds it to the end of the queue using the “append” function. The “*q” syntax allows us to modify the underlying slice that is pointed by “q”.
Next, we proceed to implement the dequeue which we also associate with the Queue type. The role of this method is to remove and return the front element of the queue.
The method also checks if the queue is empty by determining the length of the underlying slice before removing the element. If the queue is empty, it returns an error message. Otherwise, it retrieves the front element by slicing the underlying array from index 1 onwards.
This effectively shifts the front to the next element and returns the removed value.
That is how we implement a queue in Go using a slice.
Using the Linked Lists
Another approach to implement the queues is using the linked lists. This approach is more low-level compared to the one that we used previously.
Let us a look at the following source code:
import (
"fmt"
)
type Node struct {
data int
next *Node
}
type Queue struct {
front, rear *Node
}
func (q *Queue) Enqueue(val int) {
newNode := &Node{data: val, next: nil}
if q.rear == nil {
q.front = newNode
q.rear = newNode
} else {
q.rear.next = newNode
q.rear = newNode
}
}
func (q *Queue) Dequeue() (int, error) {
if q.front == nil {
return 0, fmt.Errorf("queue is empty")
}
val := q.front.data
q.front = q.front.next
if q.front == nil {
q.rear = nil
}
return val, nil
}
func main() {
q := Queue{}
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
for {
val, err := q.Dequeue()
if err != nil {
fmt.Println(err)
break
}
fmt.Printf("Dequeued: %d\n", val)
}
}
In this example, we start by defining a node struct which allows us to represent an element in the queue. Each node contains two fields:
- Data – This stores the integer value of the element.
- Next – This points to the next node in the queue.
Doing this creates a singly linked list where each node points to the next node in the queue.
In the next step, we define a queue struct to represent the queue data structure. This contains two main fields:
- Front – This is a pointer to the front node of the queue.
- Rear – This is a pointer to the rear node of the queue.
The role of these pointers is to help maintain the structure and order of the queue.
Next part is the enqueue method which basically adds a new element at the end of the queue. This works by creating a new node with the input value.
If the queue is initially empty (both front and rear are nil), the method sets both front and rear elements to the new node.
Otherwise, the method updates the rear node’s next pointer to point to the new node and updates the rear to the new node.
Finally, we have the dequeue methods which allows us to remove the front element from the queue. The method first checks if the queue is empty by checking whether the front pointer is nil.
If it is empty, the method returns an error message. Otherwise, it retrieves the data value from the front node, updates the front to point to the next node in the queue, and checks if the queue is finally empty.
If the queue is finally empty, the method updates the rear to nil as well and returns the dequeued value.
Conclusion
In this tutorial, we learned how to build one of the most important data structures in the programming: a queue using the Go programming language. This includes using a slice and a linked list.
