232. Implement Queue using Stacks
Model: qwen2.5-coder:14b
Topics: Stack,Design
FAANG asked: 1
Acceptance rate: 52.7%
Problem Breakdown
The problem requires implementing a queue using only two stacks. A queue operates on a first-in-first-out (FIFO) principle, meaning the first element added is the first one to be removed. The stack data structure operates in a last-in-first-out (LIFO) manner by default, so we need to cleverly use two stacks to simulate queue behavior.
Inputs:
push(int x): Adds an element to the back of the queue.pop(): Removes and returns the element from the front of the queue.peek(): Returns the element at the front of the queue without removing it.empty(): Checks if the queue is empty.
Outputs:
- For
push, no output (void). - For
popandpeek, an integer representing the element at the front of the queue. - For
empty, a boolean indicating whether the queue is empty.
Implicit Constraints/Edge Cases:
- The stack operations allowed are only
push to top,peek/pop from top,size, andis empty. - The number of calls to each operation is limited (at most 100).
- All calls to
popandpeekare guaranteed to be valid, meaning the queue will not be empty when these operations are called.
Intuition
A brute-force approach would involve using one stack for all operations, which would not efficiently simulate a queue’s FIFO behavior. The key insight is to use two stacks: one for enqueue operations (stack1) and another for dequeue operations (stack2). When dequeuing or peeking, if stack2 is empty, we transfer all elements from stack1 to stack2, reversing their order to maintain the correct FIFO sequence.
Approach
-
Data Structures:
- Use two stacks,
stack1for enqueue operations andstack2for dequeue operations.
- Use two stacks,
-
Push Operation:
- Simply push the element onto
stack1.
- Simply push the element onto
-
Pop Operation:
- If
stack2is empty, transfer all elements fromstack1tostack2(this reverses their order). - Pop and return the top element of
stack2.
- If
-
Peek Operation:
- Similar to pop, if
stack2is empty, transfer all elements fromstack1tostack2. - Return the top element of
stack2without popping it.
- Similar to pop, if
-
Empty Operation:
- The queue is empty if both
stack1andstack2are empty.
- The queue is empty if both
Complexity Analysis
-
Time Complexity:
- Each operation (
push,pop,peek) has an amortized time complexity of (O(1)). This is because each element is moved between the stacks at most once per operation.
- Each operation (
-
Space Complexity:
- The space complexity is (O(n)), where (n) is the number of elements in the queue. This is due to the storage required for both stacks.
Solution
class MyQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, x: int) -> None:
# Push element x to the back of stack1
self.stack1.append(x)
def pop(self) -> int:
# Ensure stack2 has the elements in FIFO order
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
# Pop and return the top element from stack2
return self.stack2.pop()
def peek(self) -> int:
# Ensure stack2 has the elements in FIFO order
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
# Return the top element from stack2 without popping it
return self.stack2[-1]
def empty(self) -> bool:
# The queue is empty if both stacks are empty
return not self.stack1 and not self.stack2
Edge Cases Handled
- Empty Queue: The
emptymethod correctly returnstruewhen both stacks are empty. - Single Element: Operations work correctly even when there’s only one element in the queue.
- Multiple Elements: The FIFO order is maintained for multiple elements pushed and popped.