Pattern visualizer
Implement Queue using 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. Animated on: Build a FIFO queue (push, peek, pop, empty) using only two stacks (inStack, outStack)..
Lazy transfer between two LIFO stacks
time O(1) amortizedspace O(n)step 1 / 9
1
[0]line 3
push(1): inStack = [1]. outStack stays empty for now.
Pseudocode
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