Stack vs Queue
Stack and Queue are both data structures. Play them side by side below, then see exactly where they diverge.
Either player can stop before each decision and ask what happens next: turn on Predict mode in its top bar.
Stack
Full topicOnly the top is reachable. The last thing down is the first thing up.
Items drop onto the TOP and lift off the TOP. Nothing below moves.
Queue
Full topicYou join at the back and leave from the front, like a queue at a counter.
FRONT -> items -> REAR. Enqueue slides in at the rear, dequeue leaves from the front.
How they differ
Both add and remove in O(1). What separates them is which end things leave from. A stack hands back the last thing put in - only the top is reachable - while a queue hands back the first: you join at the back and leave from the front. The same difference separates depth-first search, whose frontier is a stack, from breadth-first search, whose frontier is a queue.
The run shown here takes 10 steps for Stack and 10 steps for Queue. That count moves with the input - use the example tabs above either player to see it change.
| Cost | Stack | Queue |
|---|---|---|
| peek | O(1) | O(1) |
| search | O(n) | O(n) |
| push | O(1) | not documented |
| pop | O(1) | not documented |
| enqueue | not documented | O(1) |
| dequeue | not documented | O(1) |
| space | O(n) | O(n) |
A dash means the curriculum entry for that topic documents no cost under that name. It is not a claim that the operation is impossible: push on a stack and enqueue on a queue are written as different operations, so they are listed as different rows rather than paired up here.