Implement a Queue by Two Stacks
As the title described, you should only use two stacks to implement a queue's actions.
The queue should support push(element), pop() and top() where pop is pop the first(a.k.a front) element in the queue.
Both pop and top methods should return the value of first element.
Example
push(1)
pop() // return 1
push(2)
push(3)
top() // return 2
pop() // return 2
Solution:
使用两个Stack, 左边的就是负责不停的往里面push,右边的就是pop(), 当右面的为空,pop 与top的时候需要进行adjust操作,进行左stack 到右stack.
class MyQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def adjust(self):
if len(self.stack2) == 0:
while len(self.stack1) > 0:
self.stack2.append(self.stack1.pop())
def push(self, element):
# write your code here
self.stack1.append(element)
def top(self):
# write your code here
# return the top element
self.adjust()
return self.stack2[-1]
def pop(self):
# write your code here
# pop and return the top element
self.adjust()
return self.stack2.pop()
Last updated
Was this helpful?