Implement Queue using Stacks
Build a first-in, first-out queue from two last-in, first-out stacks, moving values across only when the output stack runs empty.
Problem Understanding
Implement Queue using Stacks (LeetCode 232): build a queue class, MyQueue, with push(x) to add at the back, pop() to remove and return the front, peek() to return the front, and empty(). You may only use stack operations: push to top, peek or pop from top, size and is empty. LeetCode never calls pop or peek on an empty queue.
Example: push(1), push(2), peek(), pop(), empty() returns 1, 1, false.
The Intuition: Pour One Stack into the Other
A stack gives back the newest value; a queue must give back the oldest. Pouring a stack into a second stack reverses it, so the oldest value ends up on top.
- Pushes go to inStack.
- Reads come from outStack. If outStack is empty, first pour all of inStack into it.
- Never pour while outStack has values. Everything on outStack is older than anything in inStack, so its top is still the front.
That last rule is what makes it cheap: each value is poured exactly once. Compare Min Stack, which also pairs two stacks so that every operation stays O(1).
Interactive Walkthrough
EACH VALUE MOVES ONCE
EMPTY
operations
inStack
empty
outStack
empty
Size
0
Moves
0
returned
Nothing read yet
Two empty stacks: inStack takes every push, outStack hands values back out in queue order
Next
push 1: put it on top of inStack
Ops
Legend & Complexity
The value just pushed, or just moved onto outStack
The front of the queue, read by peek
Each operation
O(1) amortized
Space
O(n)
Each move is its own step, so you can watch the order flip as values cross from inStack to outStack. Try Moves once: eight operations and only four moves, because value 4 waits in inStack until outStack runs dry.
Dry Run Table
Input: push 1, push 2, peek, pop, empty. Stacks are written bottom first.
| Operation | What happens | inStack | outStack | Returns |
|---|---|---|---|---|
| push 1 | onto inStack | [1] | [] | |
| push 2 | onto inStack | [1, 2] | [] | |
| peek | outStack is empty: move 2, then 1 | [] | [2, 1] | 1 |
| pop | outStack is not empty: no move | [] | [2] | 1 |
| empty | 2 is still in outStack | [] | [2] | false |
The Solution Template
Two stacks and a move helper that only runs when outStack is empty. The C version uses fixed arrays, since LeetCode makes at most 100 calls.
Implement Queue using Stacks Code
1class MyQueue {2 constructor() {3 this.inStack = [];4 this.outStack = [];5 }67 push(x) {8 this.inStack.push(x);9 }1011 move() {12 if (this.outStack.length === 0) {13 while (this.inStack.length) {14 this.outStack.push(this.inStack.pop());15 }16 }17 }1819 pop() {20 this.move();21 return this.outStack.pop();22 }2324 peek() {25 this.move();26 return this.outStack[this.outStack.length - 1];27 }2829 empty() {30 return this.inStack.length === 0 && this.outStack.length === 0;31 }32}
Edge Cases & Common Mistakes
- Moving when outStack is not empty: values pushed later would land on top of older ones, and pop would return the wrong value.
- empty checking one stack: values can sit in either stack, so check both.
- Pushing straight onto outStack: a new value belongs at the back of the queue, which is inStack.
- Moving values back after every pop: correct, but O(n) per operation instead of O(1) amortized.
Summary
Push onto inStack; pop and peek from outStack, pouring inStack across only when outStack is empty. Each value moves once, so every operation is O(1) amortized, with O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet