AlgoDaily - Understanding the Queue Data Structure and Its Implementations

A queue is a collection of items whereby its operations work in a FIFO - First In First Out manner. The two primary operations associated with them are enqueue and dequeue.

**Lesson Objectives**: At the end of this lesson, you will be able to: 1. Know what the *queue* data structure is and appreciate it's real-world use cases. 2. Learn how queues work and their operations. 3. Know and implement queues with two different approaches.

I'm sure all of us have been in queues before-- perhaps at billing counters, shopping centers, or cafes. The first person in the line is usually serviced first, then the second, third, and so forth.

We have this concept in computer science as well. Take the example of a printer. Suppose we have a shared printer, and several jobs are to be printed at once. The printer maintains a printing "queue" internally, and prints the jobs in sequence based on which came first.

Another instance where queues are extensively used is in the operating system of our machines. An OS maintains several queues such as a job queue, a ready queue, and a device queue for each of the processes. If you're interested, refer to this link to know more about them.

I hope we've got a solid high-level understanding about what queues are. Let's go ahead and understand how they work!

How do queues work?

Consider a pipe, perhaps a metal one in your bathroom or elsewhere in the house. Naturally, it has two open ends. Imagine that we have some elements in the pipe, and we're trying to get them out. There will be one end through which we have inserted the elements, and there's another end from which we're getting them out. As seen in the figure below, this is precisely how the queue data structure is shaped.

Unlike the stack data structure that we primarily think of with one "open end", the queue has two open ends: the front and rear. They have different purposes-- with the rear being the point of insertion and the front being that of removal. However, internally, the front and rear are treated as pointers. We'll learn more about them in the subsequent sections programmatically.

Note that the element that got inside first is the initial one to be serviced, and removed from the queue. Hence the name: First In First Out (FIFO).

Queue operations and Implementation of queues

Similar to how a stack has push and pop operations, a queue also has two pairwise operations:

1. Enqueue: To add elements
2. Dequeue: To remove elements.

Let's move on and cover each.

Click here to check out our lesson on the stack data structure!

1. Enqueue

The enqueue operation, as said earlier, adds elements to your queue from the rear end. Initially, when the queue is empty, both our front (sometimes called head) and rear (sometimes called tail) pointers are NULL.

Now, let's add an element-- say, 'a' to the queue. Both our front and rear now point to 'a'.

Let's add another element to our queue-- 'b'. Now, our front pointer remains the same, whereas the rear pointer points to 'b'. We'll add another item 'c' and you'll see that that element is also added at the rear end. Note that, a must somehow point to be internally, and b must point to c.

2. Dequeue

To dequeue means to remove or delete elements from the queue. This happens from the front end of the queue. A particular element is removed from a queue after it is done being processed or serviced. We cannot dequeue an empty queue, and we require at least one element to be present in the queue when we want to dequeue. The following figure explains the dequeuing of our previous queue.

Implementation

Let's use python for our implementation. In python, queues can be implemented using three different modules from the python library.

• list (using a list or array is generalizable to most languages)
• collections.deque (language-specific)
• queue.Queue (language-specific)

Using the list class can be a costly affair since it involves shifting of elements for every addition or deletion. This requires O(n) time. But, with the round-robin technique, even with lists, we can achieve the time complexity of O(1). We have shown the implementation below.

Instead, we can also use the 'deque' class, which is a shorthand for 'Double-ended queue' and requires O(1) time, which is much more efficient.

So first-- we can quickly implement a queue using a list or array in most languages! This is intuitive given that they're both linear data structures, and we just need to enforce some constraints on data flow:

1. To enqueue an item in the queue, we can use the list function append.
2. To dequeue an item from the queue, we can use the list function pop(0).
3. If we want the "top-most" (or last element to be processed) item in the queue, we can get the last index of the list using the [-1] index operator.

This is by far the easiest approach, but not necessarily the most performant.

# Initialize a queue list
queue = [] 

# Add elements 
queue.append(1) 
queue.append(2) 
queue.append(3) 

print("Initial queue state:") 
print(queue) 

# Removing elements from the queue 
print("Elements dequeued from queue") 
print(queue.pop(0)) 
print(queue.pop(0)) 
print(queue.pop(0)) 

print("Queue after removing elements") 
print(queue) 

// Initialize a queue list
queue = [];

// Add elements
queue.push(1);
queue.push(2);
queue.push(3);

console.log("Initial queue state:");
console.log(queue);

// Removing elements from the queue
console.log("Elements dequeued from queue");
console.log(queue.pop());
console.log(queue.pop());
console.log(queue.pop());

console.log("Queue after removing elements");
console.log(queue);

List<int> queue = new List<int>();
queue.Add(1);
queue.Add(2);
queue.Add(3);

Console.WriteLine("Initial queue state: ");
queue.ForEach(i => Console.WriteLine(i));

Console.WriteLine("Elements dequeued from queue");
Console.WriteLine(queue[0]);
queue.RemoveAt(0);            
Console.WriteLine(queue[0]);
queue.RemoveAt(0);            
Console.WriteLine(queue[0]);
queue.RemoveAt(0);

Console.WriteLine("Queue after removing elements");
queue.ForEach(i => Console.WriteLine(i));

List<Integer> queue = new ArrayList<Integer>();
queue.add(1);
queue.add(2);
queue.add(3);

System.out.println("Initial queue state: ");
System.out.println(queue);

System.out.println("Elements dequeued from queue");
System.out.println(queue.remove(0));
System.out.println(queue.remove(0));
System.out.println(queue.remove(0));


System.out.println("Queue after removing elements");
System.out.println(queue);

package main

import "fmt"

func main() {
    // Initialize a queue slice
    queue := []int{}

    // Add elements
    queue = append(queue, 1)
    queue = append(queue, 2)
    queue = append(queue, 3)

    fmt.Println("Initial queue state:")
    fmt.Println(queue)

    // Removing elements from the queue
    fmt.Println("Elements dequeued from queue")
    for i := 0; i < 3; i++ {
        fmt.Println(queue[0])
        queue = queue[1:]
    }

    fmt.Println("Queue after removing elements")
    fmt.Println(queue)
}

#include <iostream>
#include <queue>

int main() {
    // Initialize a queue
    std::queue<int> queue;

    // Add elements
    queue.push(1);
    queue.push(2);
    queue.push(3);

    std::cout << "Initial queue state:\n";
    std::queue<int> tempQueue = queue;
    while (!tempQueue.empty()) {
        std::cout << tempQueue.front() << ' ';
        tempQueue.pop();
    }
    std::cout << '\n';

    // Removing elements from the queue
    std::cout << "Elements dequeued from queue\n";
    for (int i = 0; i < 3; i++) {
        std::cout << queue.front() << '\n';
        queue.pop();
    }

    std::cout << "Queue after removing elements\n";
    // The queue is now empty, so there's nothing to print
}

Note that in C++, I used the standard queue container, which doesn't allow for direct access to its elements. The initial printout of the queue state is achieved by copying the queue to a temporary one and iterating through it. In the Go version, I used slices, which provide direct access to the underlying array, making it easier to print the entire queue.

To make this more efficient with lists, we can create a fixed-sized list and use it with two pointers and modular operations. It will yield a queue with O(1) access and deletion time.

SIZE = 10
queue = [-1 for _ in range(SIZE)] # A queue with 10 capacity

front_pointer = -1
rear_pointer = -1

def enqueue(data):
    # Check if queue is empty
    if front_pointer == -1 and rear_pointer == -1:
        front_pointer = 0
        rear_pointer = 0
        queue[front_pointer] = data
        return

    # Check if overflow
    if (rear_pointer + 1) % SIZE == front_pointer:
        print("Queue overflow")
        return

    # Enqueue
    rear_pointer = (rear_pointer + 1) % SIZE
    queue[rear_pointer] = data

def dequeue(data):
    # Check if underflow
    if front_pointer == -1 and rear_pointer == -1:
        print("Queue underflow")
        return

    # Check if queue becomes empty
    if rear_pointer == front_pointer:
        rear_pointer = -1
        front_pointer = -1
        return

    # Dequeue
    data = queue[front_pointer]
    front_pointer = (front_pointer + 1) % SIZE
    return data

def is_empty():
    return front_pointer == -1

def is_full():
    return front_pointer != -1 and front_pointer == rear_pointer

function Queue() {
  this.items = [];
}

Queue.prototype.enqueue = function (val) {
  this.items.push(val);
};

Queue.prototype.dequeue = function () {
  return this.items.shift();
};

// Check if the queue is empty
Queue.prototype.isEmpty = function () {
  return this.items.length == 0;
};

// Get the element at the front of the queue
Queue.prototype.peek = function () {
  return !this.isEmpty() ? this.items[0] : undefined;
};

Queue.prototype.length = function () {
  return this.items.length;
};

let q = new Queue();
console.log(q);

private static List<int> queue = new List<int>(10); // A List with size 10

public static void Enqueue(int value)
{
    queue.Add(value);
}

public static void Dequeue()
{
    queue.RemoveAt(0);
}

public static bool IsEmpty()
{
    return queue.Count == 0;
}

public static int Peek()
{
    return queue[0];
}

public static int Length()
{
    return queue.Count;
}

public static bool IsFull()
{
    return queue.Count == 10;
}

private static List<Integer> queue = new ArrayList<Integer>(10); // A List with size 10

public static void Enqueue(int value) {
    queue.add(value);
}

public static void Dequeue() {
    queue.remove(0);
}

public static Boolean IsEmpty() {
    return queue.size() == 0;
}

public static int Peek() {
    return queue.get(0);
}

public static int Length() {
    return queue.size();
}

public static Boolean IsFull() {
    return queue.size() == 10;
}

package main

import "fmt"

var queue []int

func Enqueue(value int) {
    queue = append(queue, value)
}

func Dequeue() {
    queue = queue[1:]
}

func IsEmpty() bool {
    return len(queue) == 0
}

func Peek() int {
    return queue[0]
}

func Length() int {
    return len(queue)
}

func IsFull() bool {
    return len(queue) == 10
}

func main() {
    // Example usage
    Enqueue(5)
    fmt.Println(Peek()) // Output: 5
}

#include <iostream>
#include <vector>

class Queue {
private:
    std::vector<int> queue;
    const int maxSize = 10;

public:
    void Enqueue(int value) {
        if (queue.size() < maxSize) {
            queue.push_back(value);
        }
    }

    void Dequeue() {
        if (!queue.empty()) {
            queue.erase(queue.begin());
        }
    }

    bool IsEmpty() {
        return queue.empty();
    }

    int Peek() {
        return queue.front();
    }

    int Length() {
        return queue.size();
    }

    bool IsFull() {
        return queue.size() == maxSize;
    }
};

int main() {
    // Example usage
    Queue queue;
    queue.Enqueue(5);
    std::cout << queue.Peek() << std::endl; // Output: 5
}

Linked List Implementation

There is another way to implement a queue. This is very similar to the Linked List implementation of stacks we used in a previous lesson.

Implementation of queue using queue class

Another way of using queues in python is via the queue class available in Queue module. It has numerous functions and is widely used along with threads for multi-threading operations. It further has FIFO, LIFO, and priority types of queues. However, we'll implement a simple queue using the queue class of the python library.

The queue class is imported from the Queue module. The queue is initialized using the Queue() constructor. Note that it accepts a maxsize() argument, specifying an upper boundary of queue size to throttle memory usage.

We use the put() function to add elements to the queue, and the get() function to remove elements from the queue. Since we have a maxsize check here, we have two other functions to check empty and full conditions. The function empty() returns a boolean true if the queue is empty and false if otherwise. Likewise, the full() function returns a boolean true if the queue is full and false if otherwise.

Here, we added elements to the queue and checked for the full condition using q.full(). Since the maxsize is four and we added four elements, the boolean is set to true.

Later, we removed three elements, leaving one element in the queue. Hence the q.empty() function returned boolean false.

You can find more functions on deque collections here.

Implementation of queue using deque class

Let's go ahead and utilize a queue along with its operations in python language using the deque class!

The deque class is imported from the collections module. We use append() function to add elements to the queue and popleft() function to remove elements from the queue.

We can see that after enqueuing, our initial queue looks like this:

Initial queue:
deque(['a', 'b', 'c', 'd'])

And after dequeuing, our final queue looks something like this:

Final queue
deque(['d'])

You can find more functions on deque collections here.

Conclusion

In this article, we began right from the basics of queues then learned the queue operations later scaled to two different approaches in implementing queues using python. We saw how the FIFO approach works in queues and how using collections is effective in terms of time complexity. I recommend you to go through the resources linked in-line with the article for further reading on queues.

One Pager Cheat Sheet

• A queue is a collection of items whereby its operations are arranged in a FIFO (First In First Out) format and involve two main operations: enqueue and dequeue.
• The queue is a data structure with two open ends, the rear for adding elements and the front for removing them, which follows the First In First Out (FIFO) principle.
• Queues work on the First In First Out (FIFO) principle of enqueuing and dequeuing elements.
• A Queue has two main operations - Enqueue to add elements and Dequeue to remove elements.
• The enqueue operation adds elements to the rear end of the queue, and updates the front and rear pointer accordingly.
• To dequeue an element from a queue, it is removed from the front end, if it is present, and at least one element must be in the queue for it to be possible.
• Dequeuing an element from the queue does not affect the front pointer, which remains the same, pointing at the first element added, while the rear pointer increases with new elements.
• We can implement queues using a list, collections.deque, or queue.Queue in python, with the list involving costly O(n) time complexity but with the use of the round-robin technique also requiring O(1) time, or using collections.deque or queue.Queue requiring O(1) time complexity.
• The complexity of implementing a queue with a list class in any programming language is O(n) due to the time needed to shift all items on each addition or deletion.
• We can quickly enqueue and dequeue items in a queue using most languages by either using a list or array, or with more efficient time complexity by implementing a fixed-sized list with two pointers.
• The Linked List implementation of Queues is similar to the Linked List implementation of Stacks we used previously.
• The python library provides the queue class from the Queue module to enable users to implement simple queues and check for the empty and full conditions using the empty() and full() functions respectively.
• We can implement a queue using the deque class from the collections module to append() and popleft() elements from the queue.
• The deque class from the collections module can be used to popleft() the first element and reduce the size of the queue in Python.
• The FIFO approach and using collections are effective approaches for implementing queues in python.