What Is a Queue?
A Queue is a FIFO (First-In-First-Out) structure. Picture people lining up at a ticket booth — whoever joined the line first buys a ticket first.
Adding at the back is enqueue; removing from the front is dequeue. Queues appear anywhere you process things "in arrival order": BFS (breadth-first search), job queues, printer spools, network buffers.
Difference from a Stack
| Stack | Queue | |
|---|---|---|
| Rule | LIFO | FIFO |
| Add | push (top) | enqueue (back) |
| Remove | pop (top) | dequeue (front) |
A stack returns the most recently pushed item; a queue returns the earliest-added item.
The Key Is the Circular Queue
The classic pitfall when building a queue on an array is shifting everything forward on each dequeue, which makes dequeue O(n).
The fix is a circular queue: keep separate front and rear indices that wrap to 0 when they reach the end. By rolling indices with (i + 1) % capacity instead of moving elements, both enqueue and dequeue stay O(1).
How It Works
Step 1. Start with front = rear = 0 and size 0.
Step 2. enqueue(x): set arr[rear] = x, then rear = (rear + 1) % cap, size +1. (Reject if full.)
Step 3. dequeue(): return arr[front], then front = (front + 1) % cap, size -1. (Reject if empty.)
Step 4. Full vs empty: front and rear alone can't distinguish the two, so keeping a separate size variable is the safe approach.
The AlgoNote visualization shows the front/rear pointers wrapping around and the queue filling and draining.
Time and Space Complexity
| Operation | Complexity |
|---|---|
| enqueue / dequeue | O(1) |
| peek front | O(1) |
| Space | O(n) |
Walking Through an Example
A circular queue of capacity 3:
- •enqueue A, B → [A, B, _], front=0, rear=2
- •dequeue → returns A, front=1
- •enqueue C, D → C at index 2, D wraps to
(3)%3=0→ [D, B, C], indices wrap around
The order — A and B leaving first — is preserved exactly.
Common Mistakes
- •Shifting from the front: operations like
arr.shift()are O(n). Use a front index, a circular queue, or a deque. - •Empty-queue handling: not checking for empty before dequeue reads a stale value.
- •Full detection: looking only at front==rear without a size variable confuses "full" with "empty".
See It in Action on AlgoNote
Watch elements enter at the back and leave at the front while the front/rear pointers wrap around, step by step on AlgoNote.