My solution only uses one queue. The idea for the pop() is that: for example, there are 4 items in the queue `x1, x2, x3, x4`

, dequeue the first three and enqueue them, so it becomes `x4, x1, x2, x3`

. Then we can pop `x4`

. In this implementation, push() is O(1), while pop() and top() are O(n).

```
class MyStack(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.q = Queue()
def push(self, x):
"""
Push element x onto stack.
:type x: int
:rtype: void
"""
self.q.push(x)
def pop(self):
"""
Removes the element on top of the stack and returns that element.
:rtype: int
"""
count = self.q.size()
while (count > 1):
self.q.push(self.q.pop())
count -= 1
return self.q.pop()
def top(self):
"""
Get the top element.
:rtype: int
"""
temp = self.pop()
self.q.push(temp)
return temp
def empty(self):
"""
Returns whether the stack is empty.
:rtype: bool
"""
return self.q.size() == 0
```

I implemented the class `Queue`

using list.

```
class Queue:
def __init__(self):
self.items = []
def push(self, data):
self.items.append(data)
def pop(self):
return self.items.pop(0)
def isEmpty(self):
return items == []
def peek(self):
return self.items[0]
def size(self):
return len(self.items)
```