# Implement Queue using Stacks

DesignStackQueue

## # Solution

Solve using two stacks.

### # Vanilla Two Stacks

Code is omitted but here is the explanation:

• __init__: initialize s1 as the main stack and s2 as auxiliary
• push: add the newly pushed element to the bottom of s1
• move all s1 to s2
• push the new element to s1
• move back old elements from s2 to s1

All other operations are quite straightforward and have constant time and space complexities.

Complexity for push

time: $O(n)$
space: $O(n)$ due to additional space taken by s2

### # Improved Two Stacks

The new element is always pushed to s1. Pop elements from s2. If s2 is empty, _move all elements from s1 to s2.

Complexity for pop

time: amortized $O(1)$ (worst case $O(n)$)
space: $O(n)$ due to additional space taken by s2

• normal case: if s2 is not empty, pop from s2
• worst case: if s2 is empty, _move doesn't pop s1 and append to s2

All other operations are quite straightforward and have constant time and space complexities.

class MyQueue:

def __init__(self):
"""
"""
self.s1 = []
self.s2 = []

def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.s1.append(x)

def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
self._move()
return self.s2.pop()

def peek(self) -> int:
"""
Get the front element.
"""
self._move()
return self.s2[-1]

def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return not self.s1 and not self.s2

def _move(self) -> None:
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39