EasyNeetCode150StackDesignQueue
Implement Stack using Queues
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).
Examples
Input
MyStack: push(1), push(2), top()=2, pop()=2, empty()=false
Output
null, null, 2, 2, false
Standard stack operations using queues.
Constraints
- •
1 <= x <= 9 - •
At most 100 calls will be made to push, top, pop, and empty - •
All the calls to pop and top are valid
Approaches
Use two queues, on push copy all elements to new queue.
CodeT: O(n) push, O(1) pop/top | S: O(n)
import collections
class MyStack:
def __init__(self): self.q=collections.deque()
def push(self, x): self.q.append(x)
def pop(self): return self.q.pop()
def top(self): return self.q[-1]
def empty(self): return not self.qUse one queue, rotate on push to simulate stack order.
CodeT: O(n) push, O(1) pop/top | S: O(n)
import collections
class MyStack:
def __init__(self): self.q=collections.deque()
def push(self, x):
self.q.append(x)
for _ in range(len(self.q)-1): self.q.append(self.q.popleft())
def pop(self): return self.q.popleft()
def top(self): return self.q[0]
def empty(self): return not self.qSame approach with minimal operations.
CodeT: O(n) push, O(1) pop/top | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Two Queues | O(n) push, O(1) pop/top | O(n) | Use two queues, on push copy all elements to new queue. |
| One Queue Simulation | O(n) push, O(1) pop/top | O(n) | Use one queue, rotate on push to simulate stack order. |
| One Queue Optimized | O(n) push, O(1) pop/top | O(n) | Same approach with minimal operations. |
Two Queues
T: O(n) push, O(1) pop/topS: O(n)
Use two queues, on push copy all elements to new queue.
One Queue Simulation
T: O(n) push, O(1) pop/topS: O(n)
Use one queue, rotate on push to simulate stack order.
One Queue Optimized
T: O(n) push, O(1) pop/topS: O(n)
Same approach with minimal operations.
Common Mistakes
Not rotating queue on push
Using wrong data structure
Off-by-one in queue rotation