232. Implement Queue using Stacks

At a Glance

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

Problem (one-liner)

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

Recognition Cues

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

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());
			}
		}
	}
}

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.