Lesson 14 · Linear structures

Queue Implementation and Applications

A queue is a First-In-First-Out (FIFO) data structure. It perfectly models real-world lines, ensuring fairness in task processing. However, a naive array implementation can lead to severe performance issues.

The Array Shifting Problem

If you implement a queue using a standard dynamic array, adding to the end (enqueue) is O(1). However, removing from the front (dequeue) leaves an empty space at index 0.

If you shift all remaining elements left to fill the gap, dequeue becomes an O(N) operation. This makes a naive array unacceptable for high-performance queues.

Enqueue is O(1) in arrays
Dequeue is O(N) due to shifting
Python's standard list is bad for queues

Linked List Implementation

A singly linked list perfectly solves the shifting problem. We maintain a head pointer for the front of the queue and a tail pointer for the rear.

To enqueue, we attach a new node to tail.next and update the tail. To dequeue, we simply move the head to head.next. Both operations are strictly O(1) without any shifting.

Requires head and tail pointers
Strictly O(1) enqueue and dequeue
Standard implementation for unbounded queues

Key reference

Terms, operations, and practical uses

Core operations

EnqueueAdding an element to the rear (tail) of the queue. O(1) time complexity.
DequeueRemoving and returning the element from the front (head) of the queue. O(1) time complexity.
FIFOFirst-In-First-Out. The fundamental ordering rule of a queue.

Implementation problems

Array ShiftingThe fatal flaw of naive array-backed queues where dequeuing requires shifting all remaining elements left in O(N) time.
Two-Stack QueueA clever workaround where one stack is used for enqueuing and another is used for dequeuing, reversing elements when needed.
Linked List QueueThe standard implementation using head and tail pointers to achieve strict O(1) enqueue and dequeue operations.

Practical applications

Breadth-First Search (BFS)Using a queue to explore trees or graphs layer by layer, guaranteeing the shortest path in unweighted graphs.
Task SchedulingBuffering incoming requests so worker threads can process them fairly in the order they were received.
Message BrokersEnterprise software (like Kafka or RabbitMQ) designed specifically to handle massive distributed queues reliably.

Code example

Linked List Queue Operations

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class Queue:
    def __init__(self):
        self.head = self.tail = None
    def enqueue(self, val):
        new_node = Node(val)
        if not self.tail:
            self.head = self.tail = new_node
            return
        self.tail.next = new_node
        self.tail = new_node
    def dequeue(self):
        if not self.head: return None
        val = self.head.val
        self.head = self.head.next
        if not self.head: self.tail = None
        return val
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.dequeue()
q.enqueue(30)
print('Front is ' + str(q.head.val) + ', Rear is ' + str(q.tail.val))

#include <iostream>
using namespace std;

struct Node { int val; Node* next; Node(int x): val(x), next(NULL) {}; };
class Queue {
public:
    Node *head = NULL, *tail = NULL;
    void enqueue(int val) {
        Node* newNode = new Node(val);
        if (!tail) { head = tail = newNode; return; }
        tail->next = newNode; tail = newNode;
    }
    int dequeue() {
        if (!head) return -1;
        int v = head->val;
        Node* temp = head; head = head->next;
        if (!head) tail = NULL;
        delete temp; return v;
    }
};

class Main {
    static class Node { int val; Node next; Node(int x) { val = x; } }
    static class Queue {
        Node head, tail;
        void enqueue(int val) {
            Node newNode = new Node(val);
            if (tail == null) { head = tail = newNode; return; }
            tail.next = newNode; tail = newNode;
        }
        int dequeue() {
            if (head == null) return -1;
            int v = head.val; head = head.next;
            if (head == null) tail = null;
            return v;
        }
    }
}

InputEnqueue 10, Enqueue 20, Dequeue, Enqueue 30

OutputFront is 20, Rear is 30

Example

Run the example step by step

Output

Breadth-First Search (BFS)

Queues are the engine behind Breadth-First Search. When exploring a graph or tree, we push a starting node into the queue. Then, we loop: dequeue a node, process it, and enqueue all of its unvisited neighbors.

Because the queue is FIFO, neighbors discovered first are processed first. This guarantees that BFS explores nodes in layers, finding the shortest path in unweighted graphs.

FIFO ensures level-by-level exploration
Finds the shortest path on unweighted graphs
Queue holds the 'frontier' of discovery

Task Scheduling

In systems engineering, queues manage asymmetric workloads. If a web server receives 10,000 requests per second but can only process 1,000, the requests are placed in a queue.

Worker threads continuously pull from the front of the queue. This buffers traffic spikes and ensures requests are handled in the order they arrived.

Models producer-consumer relationships
Buffers asynchronous workloads
Message brokers (like RabbitMQ) are just giant queues