Queues with an Array
First in, first out. Why a naive array queue makes dequeue O(n), how a front index makes it O(1), and the wasted-slot problem that leads to the circular queue.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
A queue is a line at the bank. New people join at the rear. The person at the front is served and leaves. Whoever arrived first is served first: FIFO, First In, First Out.
| Operation | Meaning |
|---|---|
enqueue(x) | add x at the rear |
dequeue() | remove and return the front item |
front() / peek() | look at the front item |
isEmpty() / isFull() | the usual checks |
Attempt 1: keep the front at index 0
Enqueue is easy: q[++rear] = x. But on dequeue, the front leaves and everyone shuffles forward: q[0] = q[1]; q[1] = q[2]; …. That is n − 1 moves per dequeue, so O(n). It is like a line where every customer takes a step each time someone is served.
Attempt 2: move the front instead
Keep a front index. Dequeue just returns q[front++]. No one moves, so it is O(1). It is like the cashier walking down the line instead of the line walking up.
The catch: front and rear only ever move right. After a few dequeues, the slots before front are empty, but rear hits MAX - 1 and the queue says “full”. Those slots are wasted forever.
The fix is to let the indices wrap around to 0. That is the circular queue, next.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Fill the queue, then dequeue. Count how many elements move each time.
Dequeue a few times, then try to enqueue. It says full, although the front slots are empty.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
using namespace std;
const int MAX = 6;
// Naive queue: dequeue shifts everything left -> O(n)
struct NaiveQueue {
int q[MAX]; int rear = -1; int moves = 0;
void enqueue(int x) { if (rear == MAX - 1) { cout << "Full\n"; return; } q[++rear] = x; }
int dequeue() {
if (rear == -1) { cout << "Empty\n"; return -1; }
int x = q[0];
for (int i = 0; i < rear; i++) { q[i] = q[i + 1]; moves++; }
rear--;
return x;
}
};
// Front-index queue: dequeue just moves front -> O(1), but wastes slots
struct FrontQueue {
int q[MAX]; int front = 0, rear = -1;
void enqueue(int x) { if (rear == MAX - 1) { cout << "Full (front=" << front << ")\n"; return; } q[++rear] = x; }
int dequeue() {
if (front > rear) { cout << "Empty\n"; return -1; }
return q[front++];
}
};
int main() {
NaiveQueue a;
for (int i = 1; i <= 5; i++) a.enqueue(i);
cout << "naive: ";
for (int i = 0; i < 5; i++) cout << a.dequeue() << " ";
cout << "| element moves: " << a.moves << "\n";
FrontQueue b;
for (int i = 1; i <= 6; i++) b.enqueue(i);
cout << "front-index: " << b.dequeue() << " " << b.dequeue() << "\n";
b.enqueue(7); // "Full" although 2 slots at the front are free
}naive: 1 2 3 4 5 | element moves: 10 front-index: 1 2 Full (front=2)
05Complexity
| enqueue (at rear) | O(1) |
|---|---|
| dequeue, naive (shift left) | O(n) |
| dequeue, with front index | O(1) |
| front / isEmpty | O(1) |
| Extra space | O(MAX) |
The front-index version is fast but cannot reuse the slots it leaves behind. The circular queue fixes that.
06Watch
Introduction to Queues
Why this one: The queue ADT, FIFO and real examples, before code.
Array implementation of Queue
Why this one: Builds the array queue, shows the wasted space, and then the circular fix.
Original class slides (Python, by the course's lecture authors):Stacks, Queues and Monotonicity
07Exam lens
Likely questions
- Define a queue and its operations. What does FIFO mean?
- Why is dequeue O(n) in a naive array queue? How does a front index make it O(1)?
- Show front, rear and the array after: enqueue 5, enqueue 3, dequeue, enqueue 8.
- Explain why a linear array queue can report "full" when it has free slots.
Common mistakes
- Confusing front and rear (items enter at the rear, leave at the front).
- Dequeuing without checking for empty.
- With a front index, testing
rear == -1for empty. The correct test isfront > rear. - Forgetting that the naive shift costs n − 1 moves on every dequeue.
08Quick check
09Practice
🟢 Trace by hand
Naive queue, MAX = 5. enqueue 10, 20, 30, 40; dequeue; dequeue; enqueue 50. Write the array, rear, and the number of element moves after each dequeue.
Show answer
- after 4 enqueues:
[10,20,30,40], rear 3 - dequeue → 10, array
[20,30,40], rear 2, 3 moves - dequeue → 20, array
[30,40], rear 1, 2 moves - enqueue 50 →
[30,40,50], rear 2
🟡 Implement it
Add int size() and void print() to the front-index queue, and make enqueue reset front = 0, rear = -1 whenever the queue becomes empty.
Hint
Size is rear - front + 1. The reset is a cheap trick that recovers space only when the queue empties completely.
🔴 Solve problems
Hint
Enqueue every ping time; dequeue from the front while it is older than
t - 3000. Return the size.Hint
An
instack for push and anoutstack for pop. Only move items from in to out when out is empty.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.