LeetCode 232 - Implement Queue using Stacks

LeetCode Problem 232

Difficulty: 🟢 Easy
Topics: Stack, Design, Queue

Solution

Problem Understanding

The problem asks us to implement a queue using only stack operations. A queue follows the FIFO, First In First Out, principle. The first element inserted into the queue must be the first element removed. In contrast, a stack follows the LIFO, Last In First Out, principle, where the most recently inserted element is removed first.

We must design a MyQueue class that behaves exactly like a normal queue while internally using only stacks. The required operations are:

• push(x) inserts an element at the back of the queue
• pop() removes and returns the element at the front
• peek() returns the front element without removing it
• empty() checks whether the queue contains any elements

The important restriction is that we can only use standard stack operations such as pushing to the top, popping from the top, checking the top element, and testing whether the stack is empty.

The input shown in the example represents a sequence of method calls performed on the queue object. The output array contains the return value for each operation. Operations like push() return null because they do not produce a value, while peek(), pop(), and empty() return actual results.

The constraints are very small, at most 100 operations, so almost any reasonable implementation would pass. However, the follow-up specifically asks for an amortized O(1) implementation, which is the real goal of the problem. This means that although some individual operations may occasionally take longer, the average cost per operation across many operations should remain constant.

A few edge cases are important:

• Calling pop() or peek() when the queue has only one element
• Performing many consecutive push() operations before any pop()
• Performing alternating push() and pop() operations
• Checking empty() after all elements have been removed

The problem guarantees that every pop() and peek() call is valid, so we never need to handle operations on an empty queue.

Approaches

Brute Force Approach

A straightforward solution uses a single stack and rearranges elements every time we insert a new value.

Since a stack removes the most recently inserted element, the newest item always appears on top. However, a queue needs the oldest element at the front. To simulate queue behavior with one stack, we can temporarily move all elements into another stack during insertion.

The process works like this:

1. Move every element from the main stack into a temporary stack.
2. Push the new element into the main stack.
3. Move everything back from the temporary stack.

After this rearrangement, the oldest element ends up on top of the main stack, which allows pop() and peek() to work correctly.

This approach is correct because it preserves queue ordering after every insertion. However, each push() operation may require moving all existing elements twice, making insertion expensive.

Optimal Approach

The optimal solution uses two stacks:

• input_stack stores newly pushed elements
• output_stack provides queue-order access for popping and peeking

The key insight is that reversing elements twice restores FIFO order.

When elements are pushed into input_stack, they are stored in reverse order relative to the queue. When we need to remove or inspect the front element, we transfer all elements from input_stack into output_stack. This reversal makes the oldest inserted element appear on top of output_stack.

Once transferred, we continue using output_stack for future pop() and peek() operations until it becomes empty again.

The important optimization is that each element moves between stacks at most once. Because of this, although a transfer operation may occasionally cost O(n), the average cost per operation across many operations becomes O(1) amortized time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	push: O(n), others O(1)	O(n)	Rearranges all elements during every insertion
Optimal	Amortized O(1)	O(n)	Uses two stacks with lazy transfer

Algorithm Walkthrough

1. Create two stacks named input_stack and output_stack.

The input_stack is used for all incoming elements. The output_stack is used when removing or peeking elements in queue order. 2. For push(x), append the element to input_stack.

This operation is simple because stacks naturally support insertion at the top in constant time. 3. For pop() and peek(), first check whether output_stack is empty.

If it is not empty, the front queue element is already available on top of output_stack. 4. If output_stack is empty, transfer all elements from input_stack into output_stack.

This reversal operation changes insertion order into queue order. The oldest inserted element becomes the top element of output_stack. 5. After the transfer, perform the required operation on output_stack.

• pop() removes and returns the top element
• peek() returns the top element without removing it

6. For empty(), check whether both stacks are empty.

The queue is empty only if neither stack contains elements.

Why it works

The algorithm maintains an important invariant:

• input_stack stores newly inserted elements
• output_stack stores elements in correct dequeue order

Whenever output_stack becomes empty, transferring all elements from input_stack reverses their order. Since stacks reverse order naturally, the oldest inserted element becomes accessible first, exactly matching FIFO queue behavior.

Because each element is pushed and transferred at most once, the total work across many operations remains linear, giving amortized O(1) complexity.

Python Solution

class MyQueue:

    def __init__(self):
        self.input_stack = []
        self.output_stack = []

    def push(self, x: int) -> None:
        self.input_stack.append(x)

    def _transfer(self) -> None:
        while self.input_stack:
            self.output_stack.append(self.input_stack.pop())

    def pop(self) -> int:
        if not self.output_stack:
            self._transfer()

        return self.output_stack.pop()

    def peek(self) -> int:
        if not self.output_stack:
            self._transfer()

        return self.output_stack[-1]

    def empty(self) -> bool:
        return not self.input_stack and not self.output_stack

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

The implementation uses two Python lists as stacks because lists support efficient append and pop operations at the end.

The constructor initializes input_stack and output_stack. The push() method simply appends to input_stack, which is always a constant-time operation.

The _transfer() helper method moves elements from input_stack to output_stack. This method is only called when output_stack is empty and we need access to the queue front.

Both pop() and peek() first ensure that output_stack contains elements. If it does not, they trigger a transfer. After that:

• pop() removes the top element from output_stack
• peek() reads the top element without removing it

The empty() method checks whether both stacks are empty. If either stack contains elements, the queue still has data.

Go Solution

type MyQueue struct {
	inputStack  []int
	outputStack []int
}

func Constructor() MyQueue {
	return MyQueue{
		inputStack:  []int{},
		outputStack: []int{},
	}
}

func (this *MyQueue) Push(x int) {
	this.inputStack = append(this.inputStack, x)
}

func (this *MyQueue) transfer() {
	for len(this.inputStack) > 0 {
		n := len(this.inputStack)

		value := this.inputStack[n-1]
		this.inputStack = this.inputStack[:n-1]

		this.outputStack = append(this.outputStack, value)
	}
}

func (this *MyQueue) Pop() int {
	if len(this.outputStack) == 0 {
		this.transfer()
	}

	n := len(this.outputStack)
	value := this.outputStack[n-1]
	this.outputStack = this.outputStack[:n-1]

	return value
}

func (this *MyQueue) Peek() int {
	if len(this.outputStack) == 0 {
		this.transfer()
	}

	return this.outputStack[len(this.outputStack)-1]
}

func (this *MyQueue) Empty() bool {
	return len(this.inputStack) == 0 && len(this.outputStack) == 0
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */

The Go implementation follows the same logic as the Python version, but slices are used instead of lists.

Go does not have a built-in stack type, so slices naturally serve this purpose. Appending to a slice acts like pushing onto a stack, and removing the last element simulates popping.

Unlike Python, Go requires explicit slice manipulation when removing elements. To pop from a stack, we take the last element and then shrink the slice using slicing syntax.

No special handling for integer overflow is needed because the constraints are very small.

Worked Examples

Example 1

Input:

["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Step-by-step Trace

Operation	input_stack	output_stack	Return Value
Initialize	[]	[]	null
push(1)	[1]	[]	null
push(2)	[1, 2]	[]	null
peek() begins transfer	[]	[2, 1]
peek() returns top	[]	[2, 1]	1
pop()	[]	[2]	1
empty()	[]	[2]	false

Explanation of the transfer:

• Before peek(), output_stack is empty

• Elements move from input_stack to output_stack

• Transfer order:

• Move 2

• Move 1

• Now 1 becomes the top of output_stack, matching queue order

Final queue contents are effectively [2].

Complexity Analysis

Measure	Complexity	Explanation
Time	Amortized O(1)	Each element is pushed and transferred at most once
Space	O(n)	Both stacks together store all queue elements

Although a transfer operation can occasionally take O(n) time, each element only moves from input_stack to output_stack once. Across many operations, the total amount of work is proportional to the number of inserted elements. Therefore, the amortized complexity per operation becomes O(1).

The space complexity is O(n) because all queue elements must be stored in the two stacks.

Test Cases

# Basic example from the problem statement
q = MyQueue()
q.push(1)
q.push(2)
assert q.peek() == 1  # front element should be 1
assert q.pop() == 1   # pop should remove 1
assert q.empty() is False  # queue still contains 2

# Single element queue
q = MyQueue()
q.push(10)
assert q.peek() == 10  # single element peek
assert q.pop() == 10   # single element pop
assert q.empty() is True  # queue should now be empty

# Multiple pushes before pops
q = MyQueue()
q.push(1)
q.push(2)
q.push(3)
q.push(4)
assert q.pop() == 1  # FIFO order
assert q.pop() == 2
assert q.peek() == 3  # next front element

# Alternating push and pop operations
q = MyQueue()
q.push(5)
assert q.pop() == 5  # immediate removal
q.push(6)
q.push(7)
assert q.pop() == 6
q.push(8)
assert q.peek() == 7
assert q.pop() == 7
assert q.pop() == 8
assert q.empty() is True

# Transfer operation stress test
q = MyQueue()
for i in range(100):
    q.push(i)

for i in range(100):
    assert q.pop() == i  # verifies correct order after large transfer

assert q.empty() is True

# Peek should not remove element
q = MyQueue()
q.push(42)
assert q.peek() == 42  # value visible
assert q.peek() == 42  # repeated peek unchanged
assert q.pop() == 42   # still available afterward

Test	Why
Basic example	Verifies standard queue behavior
Single element queue	Ensures edge case with one item works correctly
Multiple pushes before pops	Validates lazy transfer logic
Alternating operations	Checks mixed operation correctness
Large transfer stress test	Confirms FIFO order after many transfers
Repeated peek	Ensures peek does not remove elements

Edge Cases

One important edge case occurs when the queue contains only a single element. A buggy implementation might accidentally remove the element during peek() or fail to update internal state correctly after pop(). In this implementation, peek() only reads the top element from output_stack without removing it, while pop() properly removes it. After removal, both stacks become empty, so empty() correctly returns True.

Another important case is performing many consecutive push() operations before any pop(). In this scenario, all elements accumulate inside input_stack. A naive implementation might repeatedly transfer elements unnecessarily. This solution avoids that inefficiency by delaying transfers until output_stack becomes empty. When the first pop() or peek() occurs, a single transfer restores correct queue order.

A third edge case involves alternating between push() and pop() operations. Some incorrect implementations transfer elements too aggressively or lose ordering during repeated transitions. This implementation preserves correctness because elements already in output_stack remain there until exhausted, while new elements continue accumulating in input_stack. This separation guarantees that older elements are always removed before newer ones.

A final subtle edge case occurs when output_stack becomes empty after several removals, but input_stack still contains newly inserted elements. The implementation handles this cleanly by triggering another transfer only when necessary, ensuring the queue order remains correct without redundant work.