A stack is Last-In-First-Out (LIFO): you push and pop from the same end. A queue is First-In-First-Out (FIFO): you add at the back and remove from the front. Both support their core operations in O(1).
Match recent vs serve oldest
Use a stack when the answer depends on the most recent unmatched thing — balanced brackets, undo, next-greater-element. Use a queue when items must be handled in arrival order — scheduling and breadth-first traversal.
Balanced parentheses with a stack
for each char c in s:
if c is an opening bracket: push(c)
else:
if stack is empty: return false
if pop() does not match c: return false
return stack is emptyO(n)→O(n)
Each character is pushed/popped at most once.
⚡ The edge
- A stack is the natural tool for 'matching' and 'most recent' problems; a queue is for 'first come, first served' and level-by-level (BFS) processing.
- The Next Greater Element and histogram problems use a monotonic stack — keep the stack increasing or decreasing to get O(n).
Worked example
Is the string '(()' balanced?
'(' -> push stack: [ ( ]
'(' -> push stack: [ (, ( ]
')' -> pop match stack: [ ( ]
end: stack not empty- Push each opening bracket; on a closing bracket, pop and check it matches.
- After processing '(()', one '(' is still left on the stack with nothing to close it.
- A balanced string ends with an empty stack, so this one is not balanced.
Answer: Not balanced (one '(' is left unmatched)
Worked example
Using two stacks to make a queue, after enqueue 1, 2, 3 then one dequeue, what is removed?
- Enqueue pushes onto an 'in' stack: in = [1,2,3] (3 on top).
- Dequeue moves everything to an 'out' stack, reversing order: out = [3,2,1] with 1 on top.
- Popping 'out' returns 1 — the oldest element, as a queue should.
Answer: 1 is dequeued (FIFO order preserved)
⚠ Watch out
- Popping or peeking an empty stack/queue is an error — always check first.
- Deep recursion uses the call stack and can overflow; an explicit stack avoids this.
- A plain array used as a queue with shifting from the front is O(n) per dequeue — use a proper queue or two stacks.