Implement Stack using Queues

DesignStackQueue

# Solution

There is no need to implement using 2 queues, as a queue does not change the order of elements after popping and pushing.

# One Queue

There are 2 similar implementations w/ similar runtime: built-in list [] or collections.deque.

Complexity

time: push $O(1)$, pop $O(n)$
space: $O(1)$

# Built-in List

class MyStack:

def __init__(self):
"""
"""
self._q = []

def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self._q.append(x)
for _ in range(1,len(self._q)):
self._q.append(self._q[0])
self._q.pop(0)

def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self._q.pop(0)

def top(self) -> int:
"""
Get the top element.
"""
return self._q[0]

def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return not self._q

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

# Deque

from collections import deque

class MyStack:

def __init__(self):
"""
"""
self._q = deque()

def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self._q.append(x)
for _ in range(1,len(self._q)):
self._q.append(self._q.popleft())

def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self._q.popleft()

def top(self) -> int:
"""
Get the top element.
"""
return self._q[0]

def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return not self._q

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