Python 36ms

• 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):
"""
"""
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)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.