```
The Idea is very simple. Stack is a data structure widely used for simulating recursion, therefore we could create a recursive queue to simulate it.
One way to do that is
1. A queue with only two element.
2. The first element is the statck.top()
3. The second element is another queue. What's in the queue? Please goto 1.
So when we pushed 1,2,3,4,5 into the queue. The queue ends up looks like this,
(5, (4, (3, (2, (1)))))
from collections import deque
class Stack:
# initialize your data structure here.
def __init__(self):
self.queue = None
# @param x, an integer
# @return nothing
def push(self, x):
if self.queue == None:
self.queue = deque([x])
else:
self.queue = deque([x, self.queue])
# @return nothing
def pop(self):
if self.queue != None:
self.queue.popleft()
try:
self.queue = self.queue.popleft()
except:
self.queue = None
# @return an integer
def top(self):
return self.queue[0]
# @return an boolean
def empty(self):
return self.queue == None
```