Core Concept Mastery • DSA Module
Queues can be implemented using arrays or linked lists. Array-based queues suffer from a unique problem called 'False Overflow' where the Rear pointer reaches the end even though there are empty slots at the front. The solution is the Circular Queue. The time complexity of all queue operations (Enqueue, Dequeue, Peek) is O(1), and space complexity is O(n).
False Overflow: Imagine a bus with 5 seats. 5 people get on (Rear=4). Then 2 people get off from the front (Front=2). Now seats 0 and 1 are empty, but Rear is at the end, so you think the bus is full! Solution: wrap the Rear pointer around to the empty seats — that's a Circular Queue.
Arrays act weird with Queues. Here's why.
Imagine a bus. 5 people get on (Rear at end). Then 2 get off (Front moves).
The first 2 seats are empty, but REAR is at the end. We cannot add new people even though there is space!
Solution? Circular Queue.
Fixed size. Can waste space. "Sorry, false alarm."
Dynamic size. No false overflow. "Room for everyone."
1// The magic of wrapping around!2void enqueue(int value) {3if ((rear + 1) % SIZE == front) {4printf("Queue Full!"); // Actually full this time5} else {6rear = (rear + 1) % SIZE; // Loop back to 07queue[rear] = value;8}9}1011int dequeue() {12if (front == -1) {13printf("Queue Empty!");14return -1;15}16int val = queue[front];17front = (front + 1) % SIZE; // Front also wraps18return val;19}
| Action | Speed |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Peek | O(1) |
| Search | O(n) |
Space Complexity: O(n) — We need space for n people in the line.
Two Ways to Build a Queue
1. The Array Approach
You use an array to hold the elements and two integer variables — front and rear — to track the beginning and end of the queue.
2. The Linked List Approach
Every time you enqueue, you create a new Node and attach it at the Rear. Every time you dequeue, you remove the Node at the Front.
The "False Overflow" Problem
This is the biggest gotcha of array-based queues. Here's the scenario:
[_, _, _, _, _][A, B, C, D, E] (Rear = 4, full!)[_, _, _, D, E] (Front = 3)The array wastes those 3 empty slots. This is "False Overflow."
The Fix: Circular Queue (using modulo arithmetic)
Instead of moving Front and Rear linearly, we wrap them around using the modulo operator: rear = (rear + 1) % SIZE. When Rear reaches the end, it loops back to index 0.
Time Complexity Report
Space Complexity: O(n) — We need space for n elements in the queue.
Understanding implementation reveals WHY circular queues were invented. If you implement a queue with a simple array and never solve the false overflow problem, you will waste massive amounts of memory in real applications. This is a classic interview topic.
"What is the 'False Overflow' problem and how is it solved?"
False Overflow happens in linear array queues when the Rear reaches the end but there are empty slots at the beginning (from dequeue operations). It is solved by using a Circular Queue where pointers wrap around using modulo: (rear+1) % SIZE.