232. Implement Queue using Stacks

Easy

StackDesignQueue

Answered: Apr 29, 2023

Problem Description

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

void push(int x) Pushes element x to the back of the queue.
int pop() Removes the element from the front of the queue and returns it.
int peek() Returns the element at the front of the queue.
boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

Examples

Example 1

Input:

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

Output: [null, null, null, 1, 1, false]

Explanation:

MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Constraints

1 <= x <= 9
At most 100 calls will be made to push, pop, peek, and empty.
All the calls to pop and peek are valid.

Follow-up

Can you implement the queue such that each operation is amortized $O(1)$ time complexity? In other words, performing n operations will take overall $O(n)$ time even if one of those operations may take longer.

Solutions

Complexity Analysis

Time Complexity:

O (n) f or ‘ p o p ‘ an d ‘ p ee k ‘, O (1) f or ‘ p u s h ‘ an d ‘ e m pt y ‘.

Each pop and peek call transfers all n elements to stack2 and then back again, performing 2n stack operations. push and empty are $O(1)$ .

Space Complexity:

O (n)

All n elements are distributed across the two stacks at any time; no extra space is allocated during transfers.

This approach uses two stacks (stack1 and stack2) to simulate a queue, treating stack1 as the single source of truth at all times. For pop and peek, all elements are first transferred from stack1 to stack2 (which reverses the order, bringing the oldest element to the top), the front value is retrieved, and then every remaining element is transferred back to stack1. This ensures the queue invariant is always fully restored after each read operation, at the cost of doing double the transfer work.

Complexity Analysis

Time Complexity:

O (n) w or s t c a se, O (1) am or t i z e df or ‘ p o p ‘ an d ‘ p ee k ‘, O (1) f or ‘ p u s h ‘ an d ‘ e m pt y ‘.

A single pop or peek can cost $O(n)$ when out_stack is empty and all n elements must be transferred, but since each element crosses from in_stack to out_stack at most once total, the amortized cost across n operations is $O(1)$ . push and empty are always $O(1)$ .

Space Complexity:

O (n)

All n elements are distributed across the two stacks at any time; no extra space is allocated during transfers.

This approach also uses two stacks but applies lazy transfer — elements are only moved from in_stack to out_stack when out_stack is completely empty. New elements are always pushed to in_stack, while pop and peek serve exclusively from out_stack, triggering a bulk transfer only when needed. Because each element is moved from in_stack to out_stack at most once across its lifetime, the amortized cost per operation drops to $O(1)$ , which satisfies the follow-up constraint.

Conclusion

Approach	Rating	Time Complexity	Space Complexity	Advantages	Disadvantages
Two Stacks - Eager Transfer		$O(n)$ for `pop`/`peek`, $O(1)$ for `push`	$O(n)$	Easy to reason about; `stack1` always holds the full queue state	⚠️ Double transfer per `pop`/`peek` makes every read $O(n)$
Two Stacks - Lazy Transfer		$O(n)$ worst / $O(1)$ amortized for `pop`/`peek`, $O(1)$ for `push`	$O(n)$	Each element is transferred at most once, giving amortized $O(1)$ per operation	`empty` must check both stacks; worst-case single call is still $O(n)$

Per-operation Time Complexity

Approach	push	pop	peek	empty
Standard Queue	$O(1)$	$O(1)$	$O(1)$	$O(1)$
Two Stacks - Eager Transfer	$O(1)$	$O(n)$ ⚠️	$O(n)$ ⚠️	$O(1)$
Two Stacks - Lazy Transfer	$O(1)$	$O(n)$ worst / $O(1)$ amortized ⚠️	$O(n)$ worst / $O(1)$ amortized ⚠️	$O(1)$

Per-operation Space Complexity

Approach	push	pop	peek	empty	Total
Standard Queue	$O(1)$	$O(1)$	$O(1)$	$O(1)$	$O(n)$
Two Stacks - Eager Transfer	$O(1)$	$O(1)$ ℹ️	$O(1)$ ℹ️	$O(1)$	$O(n)$
Two Stacks - Lazy Transfer	$O(1)$	$O(1)$ ℹ️	$O(1)$ ℹ️	$O(1)$	$O(n)$

The optimal approach for this problem is Solution 2: Two Stacks - Lazy Transfer, which achieves $O(n)$ worst case / $O(1)$ amortized time complexity and $O(n)$ space complexity. By only transferring elements lazily when out_stack is empty, each element crosses stacks at most once, satisfying the follow-up's amortized $O(1)$ requirement.

Problem Description

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

void push(int x) Pushes element x to the back of the queue.
int pop() Removes the element from the front of the queue and returns it.
int peek() Returns the element at the front of the queue.
boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

Examples

Example 1

Input:

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

Output: [null, null, null, 1, 1, false]

Explanation:

MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Solutions

48 lines
1class MyQueue:
2
3    def __init__(self):
4        # We use two stacks: stack1 for enqueue operations and stack2 for dequeue operations
5        self.stack1 = []
6        self.stack2 = []
7
8    def push(self, x: int) -> None:
9        # We always push new elements onto the stack1
10        self.stack1.append(x)
11
12    def pop(self) -> int:
13        # If the stack2 is empty, we need to transfer all elements from stack1 to stack2
14        while self.stack1:
15            self.stack2.append(self.stack1.pop())
16
17        value = self.stack2.pop()
18
19        # After popping the front element, we can transfer the remaining elements back to stack1
20        while self.stack2:
21            self.stack1.append(self.stack2.pop())
22
23        return value
24
25    def peek(self) -> int:
26        # If the stack2 is empty, we need to transfer all elements from stack1 to stack2
27        while self.stack1:
28            self.stack2.append(self.stack1.pop())
29
30        value = self.stack2[-1]
31
32        # After peeking the front element, we can transfer the elements back to stack1
33        while self.stack2:
34            self.stack1.append(self.stack2.pop())
35
36        return value
37
38    def empty(self) -> bool:
39        # The queue is empty if stack1 is empty (since stack2 is always empty after each operation)
40        return len(self.stack1) == 0
41
42
43# Your MyQueue object will be instantiated and called as such:
44# obj = MyQueue()
45# obj.push(x)
46# param_2 = obj.pop()
47# param_3 = obj.peek()
48# param_4 = obj.empty()

Complexity Analysis

Time Complexity:

O (n) f or ‘ p o p ‘ an d ‘ p ee k ‘, O (1) f or ‘ p u s h ‘ an d ‘ e m pt y ‘.

Each pop and peek call transfers all n elements to stack2 and then back again, performing 2n stack operations. push and empty are $O(1)$ .

Space Complexity:

O (n)

All n elements are distributed across the two stacks at any time; no extra space is allocated during transfers.

40 lines
1class MyQueue:
2
3    def __init__(self):
4        # Initialize two stacks: one for incoming elements and one for outgoing elements
5        self.in_stack = []
6        self.out_stack = []
7
8    def push(self, x: int) -> None:
9        # We always push new elements onto the in_stack
10        self.in_stack.append(x)
11
12    def pop(self) -> int:
13        # If the out_stack is empty, we need to transfer all elements from in_stack to out_stack
14        if not self.out_stack:
15            while self.in_stack:
16                self.out_stack.append(self.in_stack.pop())
17
18        # The front element of the queue is now on top of the out_stack
19        return self.out_stack.pop()
20
21    def peek(self) -> int:
22        # If the out_stack is empty, we need to transfer all elements from in_stack to out_stack
23        if not self.out_stack:
24            while self.in_stack:
25                self.out_stack.append(self.in_stack.pop())
26
27        # The front element of the queue is now on top of the out_stack
28        return self.out_stack[-1]
29
30    def empty(self) -> bool:
31        # The queue is empty if both stacks are empty
32        return not self.in_stack and not self.out_stack
33
34
35# Your MyQueue object will be instantiated and called as such:
36# obj = MyQueue()
37# obj.push(x)
38# param_2 = obj.pop()
39# param_3 = obj.peek()
40# param_4 = obj.empty()

Complexity Analysis

Time Complexity:

O (n) w or s t c a se, O (1) am or t i z e df or ‘ p o p ‘ an d ‘ p ee k ‘, O (1) f or ‘ p u s h ‘ an d ‘ e m pt y ‘.

Space Complexity:

O (n)

All n elements are distributed across the two stacks at any time; no extra space is allocated during transfers.

Conclusion

Approach	Rating	Time Complexity	Space Complexity	Advantages	Disadvantages
Two Stacks - Eager Transfer		$O(n)$ for `pop`/`peek`, $O(1)$ for `push`	$O(n)$	Easy to reason about; `stack1` always holds the full queue state	⚠️ Double transfer per `pop`/`peek` makes every read $O(n)$
Two Stacks - Lazy Transfer		$O(n)$ worst / $O(1)$ amortized for `pop`/`peek`, $O(1)$ for `push`	$O(n)$	Each element is transferred at most once, giving amortized $O(1)$ per operation	`empty` must check both stacks; worst-case single call is still $O(n)$

Per-operation Time Complexity

Approach	push	pop	peek	empty
Standard Queue	$O(1)$	$O(1)$	$O(1)$	$O(1)$
Two Stacks - Eager Transfer	$O(1)$	$O(n)$ ⚠️	$O(n)$ ⚠️	$O(1)$
Two Stacks - Lazy Transfer	$O(1)$	$O(n)$ worst / $O(1)$ amortized ⚠️	$O(n)$ worst / $O(1)$ amortized ⚠️	$O(1)$

Per-operation Space Complexity

Approach	push	pop	peek	empty	Total
Standard Queue	$O(1)$	$O(1)$	$O(1)$	$O(1)$	$O(n)$
Two Stacks - Eager Transfer	$O(1)$	$O(1)$ ℹ️	$O(1)$ ℹ️	$O(1)$	$O(n)$
Two Stacks - Lazy Transfer	$O(1)$	$O(1)$ ℹ️	$O(1)$ ℹ️	$O(1)$	$O(n)$

232. Implement Queue using Stacks

Problem Description

Examples

Example 1

Constraints

Follow-up

Solutions

Solution 1: Two Stacks - Eager Transfer

Complexity Analysis

Explanation

Solution 2: Two Stacks - Lazy Transfer

Complexity Analysis

Explanation

Conclusion

Per-operation Time Complexity

Per-operation Space Complexity

232. Implement Queue using Stacks

Problem Description

Examples

Example 1

Constraints

Follow-up

Solutions

Solution 1: Two Stacks - Eager Transfer

Complexity Analysis

Explanation

Solution 2: Two Stacks - Lazy Transfer

Complexity Analysis

Explanation

Conclusion

Per-operation Time Complexity

Per-operation Space Complexity