Implement Queue using Stacks - Solution
Solutions and explanations
class MyQueue:
def __init__(self):
self.stack_in = []
self.stack_out = []
def push(self, x: int) -> None:
self.stack_in.append(x)
def pop(self) -> int:
self.move_if_needed()
return self.stack_out.pop()
def peek(self) -> int:
self.move_if_needed()
return self.stack_out[-1]
def empty(self) -> bool:
return not self.stack_in and not self.stack_out
def move_if_needed(self) -> None: # Transfer elements only when the output stack is empty
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
Complexity Analysis
Here, n is the number of operations (pushes) performed.
Initialization:
- Time Complexity:
O(1)- Initializing two empty stacks. - Space Complexity:
O(1)- No elements are stored initially.
Push:
- Time Complexity:
O(1)- Appending an element takes constant time. - Space Complexity:
O(1)- per operation (incremental storage).
Pop:
- Time Complexity:
O(1)Amortized - Most calls takeO(1)time. In the worst case, when output stack is empty, it takesO(n)to transfer elements, but this happens only once per element over the lifetime of the queue. - Space Complexity:
O(1)- No additional space used.
Peek:
- Time Complexity:
O(1)Amortized - Most calls takeO(1)time. In the worst case, when output stack is empty, it takesO(n)to transfer elements, but this happens only once per element over the lifetime of the queue. - Space Complexity:
O(1)
Empty:
- Time Complexity:
O(1) - Space Complexity:
O(1)
Overall Space Complexity: O(n) - In the worst case, all n elements pushed into the queue are stored in memory across the two stacks.