225. Implement Stack using Queues
Model: qwen2.5-coder:14b
Topics: Stack,Design
FAANG asked: 1
Acceptance rate: 47.9%
Problem Breakdown
The problem requires implementing a stack using only two queues. A stack operates on a Last In First Out (LIFO) principle, meaning the last element added is the first one to be removed. The operations that need to be supported are push, pop, top, and empty. We must use only standard queue operations: push to back, peek/pop from front, size, and is empty.
Inputs/Outputs:
- Input: A series of stack operations (
push,pop,top,empty). - Output: The result of the operations, such as the value popped or whether the stack is empty.
Implicit Constraints/Edge Cases:
- The stack should support all standard stack operations.
- The implementation must use only queue operations.
- Edge cases include pushing and popping elements, checking if the stack is empty, and retrieving the top element.
Intuition
A brute-force approach would involve using two queues to simulate a stack. However, this could lead to inefficient operations, especially for pop and top, which might require moving all elements between queues. The key insight is to maintain one queue as the primary storage and use the second queue only during the push operation to ensure LIFO behavior.
Approach
- Data Structure Choice: Use two queues (
queue1andqueue2).queue1will store the main stack elements, whilequeue2is used temporarily during thepushoperation. - Push Operation:
- Enqueue the new element into
queue2. - Dequeue all elements from
queue1and enqueue them intoqueue2. This ensures that the newly added element is at the front ofqueue2, maintaining LIFO order. - Swap the roles of
queue1andqueue2.
- Enqueue the new element into
- Pop Operation: Simply dequeue the front element from
queue1. - Top Operation: Return the front element of
queue1without removing it. - Empty Operation: Check if
queue1is empty.
Complexity Analysis
- Time Complexity:
push: O(n) because all elements inqueue1are moved toqueue2.pop,top,empty: O(1).- Overall, each operation is amortized O(1) due to the nature of queue operations.
- Space Complexity: O(n), where n is the number of elements in the stack. This is because we use two queues to store the elements.
Solution
from collections import deque
class MyStack:
def __init__(self):
self.queue1 = deque()
self.queue2 = deque()
def push(self, x: int) -> None:
# Push element x onto stack.
self.queue2.append(x)
while self.queue1:
self.queue2.append(self.queue1.popleft())
self.queue1, self.queue2 = self.queue2, self.queue1
def pop(self) -> int:
# Removes the element on top of the stack and returns that element.
return self.queue1.popleft()
def top(self) -> int:
# Get the top element.
return self.queue1[0]
def empty(self) -> bool:
# Returns whether the stack is empty.
return not self.queue1
Edge Cases Handled
- Empty Stack: The
popandtopoperations handle an empty stack by checking ifqueue1is empty before proceeding. - Single Element: Operations work correctly even when there’s only one element in the stack.
- Multiple Elements: The LIFO order is maintained for any number of elements pushed onto the stack.