Implement Queue using Stacks
- 2 min read
- Queue
- Stacks
- LC-Easy
3 years ago
Solution 1 (Less Efficient)
- Use two stacks. The first one has all the elements in it such that the top of the stack is the element that was pushed first
- Whenever a push operation happens, pop from the first stack until first stack is empty and push on to the second stack.
- Now, push the new element.
- Now, pop all of the remaining elements from the second stack and push on the second stack.
- Whenever a top or pop operation is called, just return the stack top- it is equivalent the to the first element of the queue.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(2n) | O(n) for push since we have to move all elements to another stack before pushing |
class MyQueue:
def __init__(self):
self.s1 = []
self.s2 = []
def push(self, x: int) -> None:
while self.s1:
self.s2.append(self.s1.pop())
self.s1.append(x)
while self.s2:
self.s1.append(self.s2.pop())
def pop(self) -> int:
return self.s1.pop()
def peek(self) -> int:
return self.s1[-1]
def empty(self) -> bool:
return len(self.s1) == 0
Solution 1 More Efficient)
- Still maintain two stacks, but call them input and output for understandability.
- Whenever a push operation happens, push to input stack.
- Whenever a pop or push operation is called, return top of output stack. If output stack is empty, push from input stack to output stack until input stack is empty.
| Time | Space | Explanation |
|---|---|---|
O(1) | O(2n) | O(1) is amortized time complexity, not worst case |
class MyQueue:
def __init__(self):
self.input = []
self.output = []
def push(self, x: int) -> None:
self.input.append(x)
def transfer(self) -> None:
if not self.output:
while self.input:
self.output.append(self.input.pop())
def pop(self) -> int:
self.transfer()
return self.output.pop()
def peek(self) -> int:
self.transfer()
return self.output[-1]
def empty(self) -> bool:
return not self.output and not self.input