Back to Study Material Data Structures and Algorithms

Queue

A queue is a linear data structure that follows the first-in, first-out principle: the element that has been in the queue the longest is the next to be rem...

Queue

Queue Fundamentals: First-In, First-Out Order

A queue is a linear data structure that follows the first-in, first-out principle: the element that has been in the queue the longest is the next to be removed. This mirrors everyday waiting lines: the person who arrives first is served first. In computing, queues govern scheduling, buffering, and breadth-first traversal.

A queue has two ends with distinct roles. Elements are added at the rear (also called tail or back) and removed from the front (also called head). The operation that adds to the rear is called enqueue or offer. The operation that removes from the front is called dequeue or poll. A peek operation reads the front element without removing it.

An array-based queue uses two pointers: front and rear. Enqueue increments rear and stores the element at that position. Dequeue reads the element at front and increments front. A naive implementation wastes space as front moves rightward and the positions behind it become unusable. The solution is a circular buffer, discussed in the Circular Queue topic, which reuses those positions by wrapping the pointers around.

A linked list queue uses a head pointer for the front and a tail pointer for the rear. Enqueue creates a new node and links it from the current tail, then updates the tail pointer. Dequeue reads the head node, advances the head pointer, and frees the old node. Both operations are O(1) with no wasted space, making linked list queues suitable when the maximum size is unknown.

Space complexity is O(n) for all queue implementations. Time complexity for enqueue and dequeue is O(1) in both array (circular) and linked list implementations. Peek is also O(1).

Worked example: enqueue 1, enqueue 2, enqueue 3. Dequeue returns 1 (first in, first out). Enqueue 4. Dequeue returns 2. The queue now holds [3, 4] with 3 at the front. Peek returns 3 without modifying the queue.

Interview tip: when asked to implement a queue, clarify whether the maximum size is bounded. For bounded queues, a circular array is memory-efficient. For unbounded queues, a linked list avoids the risk of overflow without resizing overhead.

Queue Applications: BFS, Task Scheduling, and Buffering

Queues are indispensable in scenarios that require processing items in the order they arrive. Three major application domains illustrate their importance: graph traversal, operating system task scheduling, and data buffering between producers and consumers.

Breadth-first search traverses a graph level by level, visiting all neighbors of the starting node before visiting any node two hops away. A queue drives this traversal naturally. Enqueue the start node and mark it visited. While the queue is not empty, dequeue the front node, process it, and enqueue all its unvisited neighbors, marking them visited immediately to prevent duplicate enqueues. The queue guarantees that nodes are visited in the order they were first discovered, which is the defining property of BFS. Time complexity is O(V + E) where V is the number of vertices and E is the number of edges.

In operating systems, the ready queue holds processes that are waiting for CPU time. The simplest scheduling policy, first-come-first-served, dequeues the front process, runs it to completion, then dequeues the next. Round-robin scheduling gives each process a fixed time slice, and when the slice expires, the process is re-enqueued at the rear, allowing all processes to make progress proportionally.

Producer-consumer systems use queues as buffers to decouple the rates of production and consumption. A web server receiving requests at variable rates buffers them in a queue and a pool of worker threads dequeue and handle them at a steady rate. This smooths out traffic spikes without dropping requests. Blocking queues add the constraint that a dequeue on an empty queue blocks until an element is enqueued, and an enqueue on a full bounded queue blocks until space is available, enabling safe coordination between threads.

Worked example: BFS on graph with nodes 1-5, edges 1-2, 1-3, 2-4, 3-5. Start at 1. Queue: [1]. Dequeue 1, enqueue 2 and 3. Queue: [2, 3]. Dequeue 2, enqueue 4. Queue: [3, 4]. Dequeue 3, enqueue 5. Queue: [4, 5]. Dequeue 4, no unvisited neighbors. Dequeue 5. BFS order: 1, 2, 3, 4, 5.

Interview tip: for shortest path problems on unweighted graphs, immediately state that BFS finds the minimum hop count because it explores nodes in non-decreasing order of distance from the source. Dijkstra is only needed when edges have weights.

Linked List Queue Implementation in Detail

Implementing a queue with a singly linked list demonstrates how two simple pointers can eliminate the index management complexity of array-based queues while providing O(1) operations without capacity limits.

The structure consists of nodes, each containing a value and a next pointer, a head pointer pointing to the front node, a tail pointer pointing to the rear node, and a size counter. Initialize head and tail to null and size to zero for an empty queue.

Enqueue creates a new node with the given value and a null next pointer. If the queue is empty, both head and tail are set to the new node. Otherwise, the current tail's next pointer is updated to the new node and tail advances to the new node. Size increments. This always operates on the tail and never touches any other node, so it is O(1).

Dequeue checks whether the queue is empty by testing head against null. If empty, raise an underflow error. Otherwise, store the value from the head node, advance head to head.next, and decrement size. If the queue is now empty (head became null), also set tail to null to avoid a dangling reference. In languages with manual memory management, free the old head node. Return the stored value. This always operates on the head and is O(1).

A common mistake is forgetting to update tail to null when the last element is dequeued. After removing the final element, head becomes null but tail still points to the freed node. Any subsequent enqueue that tries to set tail.next will corrupt memory or reference garbage.

Size can be computed by traversing the list in O(n), but maintaining a separate counter gives O(1) size queries, which is almost always worth the small bookkeeping cost.

Worked example: enqueue A. Head and tail both point to node A. Enqueue B. Tail.next points to node B; tail advances to B. Head still points to A. Enqueue C. Tail.next points to C; tail advances to C. Queue: A -> B -> C. Dequeue: return A, head advances to B. Queue: B -> C, size = 2.

Interview tip: draw the head and tail pointers on paper during the interview and update them step by step. Pointer manipulation bugs in linked list code are almost always caught during a careful visual trace.