- Implement Queue using Stacks
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
my thoughts:
1. use a temp stack to reverse the stack.
my solution:
**********32ms
class MyQueue(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.q = []
def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
self.q.append(x)
def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
temp = []
while self.q:
t = self.q.pop()
temp.append(t)
res = temp.pop()
while temp:
t = temp.pop()
self.q.append(t)
return res
def peek(self):
"""
Get the front element.
:rtype: int
"""
temp = []
while self.q:
t = self.q.pop()
temp.append(t)
res = temp.pop()
self.q.append(res)
while temp:
t = temp.pop()
self.q.append(t)
return res
def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return len(self.q) == 0
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
my comments:
from other ppl's solution:
1. use to stacks in the constructor can safe some operations, 23 ms:
class MyQueue(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.list1 = []
self.list2 = []
def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
self.list1.append(x)
def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
while len(self.list1) != 0:
val = self.list1.pop()
self.list2.append(val)
result = self.list2.pop()
while len(self.list2) != 0:
val = self.list2.pop()
self.list1.append(val)
return result
def peek(self):
"""
Get the front element.
:rtype: int
"""
while len(self.list1) != 0:
val = self.list1.pop()
self.list2.append(val)
result = self.list2[-1]
while len(self.list2) != 0:
val = self.list2.pop()
self.list1.append(val)
return result
def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return len(self.list1) == 0