Queue Data Structure: Operations, Circular Queues and Worked Examples for GATE

FIFO sounds simple until array indices move, a circular queue wraps, or physical and logical orders differ. A five-slot queue exposes those index changes, while linked lists, two stacks and BFS show how FIFO survives different implementations. For the broader syllabus, use GATE CS Exam Preparation Courses & Test Series.

What a queue stores and the invariants that define it

A queue is an abstract data type with first in, first out removal. enqueue(x) inserts at the rear, dequeue() removes from the front, and peek() or front() reads without removing. It also needs isEmpty() and, when bounded, isFull().

For logical queue [12, 7, 25], 12 leaves first. Enqueuing 9 gives [12, 7, 25, 9]. Arrays, circular buffers, linked lists and two stacks preserve this order. Dequeuing an empty queue causes underflow. A bounded full queue causes overflow; a linked queue is limited by memory.

Why a plain linear array queue wastes freed slots

Use a capacity-five array indexed 0..4. Let front name the next removal, rear the next insertion, and size the active count. Start at front = 0, rear = 0, size = 0, without wraparound.

Enqueue 12, 7, 25, 9. The array becomes [12, 7, 25, 9, _], with front = 0, rear = 4, size = 4 and logical order [12, 7, 25, 9]. Two dequeues return 12, then 7, leaving front = 2, rear = 4, size = 2 and logical order [25, 9].

Enqueue 31 at index 4. Cells become [12*, 7*, 25, 9, 31], with front = 2, rear = 5, size = 3; asterisks mark stale values. The next enqueue cannot use freed indices 0 or 1, causing false overflow. Shifting costs O(n); circular indexing keeps both end operations constant.

Circular queue worked example: every index and value traced

Restart with a clean capacity-five array and the same convention: front = 0, rear = 0, size = 0; rear names the next insertion index. Dequeue sets front = (front + 1) % 5; enqueue sets rear = (rear + 1) % 5. Empty means size = 0; full means size = 5.

The empty start has front = rear = 0, while the final full state has front = rear = 2. The separate size resolves this ambiguity. A different design reserves one slot and declares full when (rear + 1) % capacity == front. It sacrifices one slot, so do not mix formulas.

Linked-list queue: the same FIFO rule without wraparound

A singly linked queue keeps front at the oldest node and rear at the newest. Start with 12 -> 7 -> 25: front points to 12, rear to 25, and rear.next = null. Link 9 after the old rear and move rear to 9, producing 12 -> 7 -> 25 -> 9.

To dequeue, save 12, move front to 7, and return 12. If a queue containing only [9] dequeues 9, set both pointers to null or rear becomes stale. Both operations take O(1) time, with O(n) storage plus one link per node. You can practise array and linked-list implementations to make the pointer changes concrete.

Deques, priority queues and BFS use different parts of the idea

A deque permits operations at both ends. From [20, 30], addFirst(10) gives [10, 20, 30], and addLast(40) gives [10, 20, 30, 40]. Then removeLast() returns 40 and removeFirst() returns 10, leaving [20, 30].

A priority queue removes by priority. For jobs A(priority 2), B(priority 1), C(priority 2), let a smaller number mean higher priority and preserve insertion order for ties. Removal is B, A, C; FIFO applies only within equal priority.

BFS uses an ordinary queue on an undirected graph. For edges A-B, A-C, B-D, B-E, C-F, E-F, process neighbours alphabetically and mark them when enqueued. States are [A], [B, C], [C, D, E], [D, E, F], [E, F], [F], []. Visit order is A, B, C, D, E, F; levels are 0:{A}, 1:{B,C}, 2:{D,E,F}. For focused follow-up, work through Data Structures Graphs MCQs.

How GATE-style questions and interviews probe queues

Typical questions ask you to trace front and rear, decide full or empty under a stated convention, predict output, compare implementations, build a queue with two stacks, or apply BFS.

For the two-stack method, S_in receives elements and S_out supplies dequeues. Enqueue 4, 6, 8 onto S_in, with 8 on top. Since S_out is empty, the first dequeue transfers values in pop order 8, 6, 4. Now 4 tops S_out, so dequeue returns 4. Enqueue 10 onto S_in; the second dequeue returns 6 from S_out. Returned sequence: 4, 6. Remaining logical queue: [8, 10].

A transfer can cost O(n), but each element moves from S_in to S_out only once, making amortised cost O(1) per operation. KnowledgeGate has 170+ Queue questions available for practice. They are not all GATE previous-year questions, so use them as practice alongside broader Data Structures MCQs.

Queue traps that change the answer

A linked queue has O(1) enqueue only with a rear pointer; walking from front costs O(n). Lazy two-stack operations are amortised O(1), though one transfer-triggering dequeue costs O(n).

Short version and the next step

FIFO defines queues; linear arrays can suffer false overflow; modulo arithmetic reuses slots; linked queues need both end pointers; deques and priority queues change removal rules. In the final circular trace, the physical cells are [18, 44, 25, 9, 31] while the logical order is [25, 9, 31, 18, 44].

Self-check, capacity four: enqueue 5, 8; dequeue; enqueue 13, 21; dequeue; enqueue 34. Answer: [34, _, 13, 21], front = 2, rear = 1, size = 3, logical [13, 21, 34]. Use GATE Guidance by Sanchit Sir for structured GATE CS study.