Implement Queue using Stacks
Lazy transfer between two LIFO stacks
A single stack pops in the wrong order for a queue. The trick: keep an inStack for pushes, and only when outStack runs dry do you pour all of inStack into outStack — one pop-and-push per element reverses the order, so the oldest pushed item lands on top of outStack. Reads (peek/pop) always happen from outStack. Each element is moved from inStack to outStack at most once, so the cost amortizes to O(1) per operation.
Details
Animated on: Build a FIFO queue (push, peek, pop, empty) using only two stacks (inStack, outStack).
Problem:Implement Queue using StacksEasy
Lazy transfer between two LIFO stacks
step 1 / 9
push(1): inStack = [1]. outStack stays empty for now.
- top=0· arr[0] = 1
1CLASS MyQueue:2 two stacks: inStack = [], outStack = []3 push(x): push x onto inStack4 peek(): IF outStack is empty:5 pop every item off inStack and push it onto outStack6 RETURN the top of outStack7 pop(): call peek(), then pop and return the top of outStack8 empty(): RETURN true if both inStack and outStack are empty
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- push(1): inStack = [1]. outStack stays empty for now.
- push(2): inStack = [1,2]. Pushes are cheap — always go straight onto inStack.
- peek() is called. outStack is empty, so we must transfer everything from inStack first.
- Pop inStack's top (2) and push it onto outStack. outStack = [2]. inStack is now [1].
- Pop inStack's remaining item (1) and push it onto outStack. outStack = [2,1] — top is 1. inStack is now empty.
- peek() reads outStack's top without removing it: returns 1 — the oldest pushed value, as a queue requires.
- pop(): outStack's top is popped and returned — that's 1. outStack shrinks to [2].
- outStack is now [2]. inStack is still empty.
- empty(): inStack=[] but outStack=[2] — not both empty, so empty() returns false.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.