原題
利用兩個(gè)隊(duì)列來(lái)實(shí)現(xiàn)一個(gè)棧的功能
樣例
push(1)
pop()
push(2)
isEmpty() // return false
top() // return 2
pop()
isEmpty() // return true
解題思路
- 使用兩個(gè)queue
q1 = [] q2 = []
push 1
q1 = [1] q2 = []
q1 = [] q2 = [1]
push 2
q1 = [2] q2 = [1]
q1 = [2, 1] q2 = []
q1 = [] q2 = [2, 1]
push 3
q1 = [3] q2 = [2, 1]
q1 = [3, 2, 1] q2 = []
q1 = [] q2 = [3, 2, 1]
完整代碼
import Queue
class Stack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.q1 = Queue.Queue()
self.q2 = Queue.Queue()
def push(self, x):
"""
:type x: int
:rtype: nothing
"""
self.q1.put(x)
while self.q2.qsize() != 0:
self.q1.put(self.q2.get())
while self.q1.qsize() != 0:
self.q2.put(self.q1.get())
def pop(self):
"""
:rtype: nothing
"""
self.q2.get()
def top(self):
"""
:rtype: int
"""
return self.q2.queue[0]
def empty(self):
"""
:rtype: bool
"""
return self.q2.qsize() == 0
