How to Solve Implement Queue Using Stack on LeetCode
Implement Queue Using Stack is a common data structure problem that tests your understanding of stack and queue operations.
Problem Statement
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all standard queue operations (push, pop, peek, empty).
Example:
Input: ["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output: [null, null, null, 1, 1, false]
Why This Problem Matters for Interviews
- Tests understanding of fundamental data structures
- Teaches the concept of stack-to-queue transformation
- Appears in system design interviews
Approach to Implement Queue Using Stack
Two-Stack Method (Optimal)
Use two stacks: one for input, one for output. Transfer elements from input to output only when needed.
Time Complexity: Amortized O(1) per operation
Space Complexity: O(n)
class MyQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []
def push(self, x):
self.in_stack.append(x)
def pop(self):
self.peek()
return self.out_stack.pop()
def peek(self):
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
return self.out_stack[-1]
def empty(self):
return not self.in_stack and not self.out_stack
Key Interview Talking Points
- Why two stacks are necessary
- How amortized O(1) is achieved
- Difference between queue and stack order
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Stack Queue | O(1) Amortized | O(n) |
Pro Interview Tips
- Draw each step for push/pop operations
- Discuss lazy loading to output stack
- Know follow-up: implement stack using queues