232. Implement Queue using Stacks

Quick Identifier

• Topic: stack
• Pattern: Two Stacks (amortized queue)
• Difficulty: Easy
• Companies: Amazon, Google, Microsoft, Bloomberg, Apple
• Frequency: High
• LeetCode: 232

Quick Sights

• Time Complexity: inStack from the optimal approach.
• Space Complexity: outStack from the optimal approach.
• Core Mechanism: Implement FIFO push, peek, pop using only stack operations (push, pop, peek/top, empty). Two stacks allowed.

Concept Explanation

Implement FIFO push, peek, pop using only stack operations (push, pop, peek/top, empty). Two stacks allowed.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

• "Queue from stacks"
• Input stack + output stack; lazy transfer on pop/peek
• Amortized O(1) per op

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Naive — pop entire stack to rebuild order each time — O(n) worst per op.
• Better — two-stack lazy reversal — amortized O(1).
• Optimal — inStack for enqueue, move to outStack when dequeue needs data.

Optimal Solution

Go

type MyQueue struct {
	inStack  []int
	outStack []int
}

func Constructor() MyQueue {
	return MyQueue{inStack: []int{}, outStack: []int{}}
}

func (queue *MyQueue) Push(value int) {
	queue.inStack = append(queue.inStack, value)
}

func (queue *MyQueue) Pop() int {
	queue.move()
	top := queue.outStack[len(queue.outStack)-1]
	queue.outStack = queue.outStack[:len(queue.outStack)-1]
	return top
}

func (queue *MyQueue) Peek() int {
	queue.move()
	return queue.outStack[len(queue.outStack)-1]
}

func (queue *MyQueue) Empty() bool {
	return len(queue.inStack) == 0 && len(queue.outStack) == 0
}

func (queue *MyQueue) move() {
	if len(queue.outStack) == 0 {
		for len(queue.inStack) > 0 {
			top := queue.inStack[len(queue.inStack)-1]
			queue.inStack = queue.inStack[:len(queue.inStack)-1]
			queue.outStack = append(queue.outStack, top)
		}
	}
}

JavaScript

class MyQueue {
	constructor() {
		this.inStack = [];
		this.outStack = [];
	}
	push(value) {
		this.inStack.push(value);
	}
	pop() {
		this.move();
		return this.outStack.pop();
	}
	peek() {
		this.move();
		return this.outStack.at(-1);
	}
	empty() {
		return this.inStack.length === 0 && this.outStack.length === 0;
	}
	move() {
		if (this.outStack.length === 0) {
			while (this.inStack.length > 0) {
				this.outStack.push(this.inStack.pop());
			}
		}
	}
}

Walkthrough

After push(1) and push(2), inStack holds [1,2] from bottom to top. The first peek or pop triggers move: transfer pops 2 then 1 onto outStack, so the stack top is 1 (the queue front). Later push calls append to inStack until outStack is emptied again.

Invariant: when outStack is non-empty, its top is the FIFO front; move only refills from inStack when outStack is empty, preserving relative order.

Edge Cases

• Interleaved push/pop heavy patterns
• Single element many times

Pitfalls

• Moving inStack → outStack while outStack non-empty (breaks order)
• Confusing which end is "front"

Similar Problems

• 155. Min Stack — auxiliary structure coordination.
• 020. Valid Parentheses — pure stack fluency.
• 150. Evaluate Reverse Polish Notation — ordered consumption from stacks.

Variants

• Queue using one stack + recursion (system stack as second).
• Stack using two queues — inverse puzzle.

Mind-Map Tags

#stack #queue #two-stack #amortized #fifo