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:
push to top, peek/pop from top, size, and is empty operations are valid.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 <= 9100 calls will be made to push, pop, peek, and empty.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.
The problem #232 Implement Queue using Stacks asks you to design a queue using only stack operations. Since a queue follows FIFO (First In, First Out) while a stack follows LIFO (Last In, First Out), the key challenge is reversing the order of elements using stacks.
A common approach is to use two stacks. The first stack handles incoming elements through the push operation, while the second stack helps retrieve elements in queue order. When a dequeue or peek operation is needed, elements can be transferred from the first stack to the second stack to reverse their order, allowing the oldest element to be accessed first.
This design ensures that most operations run in amortized O(1) time, because elements are transferred between stacks only when necessary. The extra space used is proportional to the number of stored elements. Understanding how stack transfers simulate queue behavior is the core insight for solving this design problem efficiently.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Stacks (Amortized Queue Simulation) | Push: O(1), Pop/Peek: Amortized O(1) | O(n) |
NeetCode
This approach uses two stacks: 'input' for pushing elements and 'output' for popping elements. While pushing, simply add the element to the input stack. For popping or peeking, check if the output stack is empty; if it is, transfer all elements from the input stack to the output stack and then pop or peek from the output stack.
Time Complexity: Each operation (push, pop, peek, empty) has an amortized O(1) complexity. Space Complexity: O(n), where n is the number of elements in the queue.
1class MyQueue:
2 def __init__(self):
3 self.input = []
4 self.output = []
5
6 def push(self, x: int) -> None:
7 self.input.append(x)
8
9 def pop(self) -> int:
10 self.move_input_to_output()
11 return self.output.pop()
12
13 def peek(self) -> int:
14 self.move_input_to_output()
15 return self.output[-1]
16
17 def empty(self) -> bool:
18 return not self.input and not self.output
19
20 def move_input_to_output(self) -> None:
21 if not self.output:
22 while self.input:
23 self.output.append(self.input.pop())The MyQueue class is implemented using two stacks. The 'input' stack holds elements pushed to the queue, and 'output' stack holds elements in the pop/peek order. The move_input_to_output helper method is used to transfer elements from input to output stack when output is empty, ensuring the correct order for queue operations.
This approach is similar to the previous one, but emphasizes minimizing transfers between the stacks by only transferring when absolutely necessary (when the output stack is empty). This optimizes performance in terms of total operations.
Time Complexity: Each operation (push, pop, peek, empty) has an amortized O(1) complexity. Space Complexity: O(n), where n is the number of elements in the queue.
1import java.util.Stack;
2
3
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Two stacks help reverse the LIFO order of elements so that the oldest element can be accessed first. When elements move from the input stack to the output stack, their order reverses, effectively simulating queue operations.
Yes, this is a common design-based interview question often asked in FAANG and other top tech companies. It tests understanding of stack behavior, data structure transformation, and amortized time complexity.
The optimal approach uses two stacks to simulate queue behavior. One stack stores incoming elements while the other helps reverse the order during dequeue operations. This ensures amortized O(1) time for push, pop, and peek operations.
The problem uses a design technique where two stacks are combined to mimic the FIFO behavior of a queue. By transferring elements between stacks, the order of elements can be reversed to access the earliest inserted element.
Like the other solutions, this Java implementation leverages two stacks but specifically reduces data transfer by only moving elements from input to output when the output stack is empty. This ensures minimal effort when dequeue operations are scaffolded by stacked operations.