document.write('
题目要求用两个栈来模拟队列,假设使用栈A与栈B模拟队列Q,A为插入栈,B为弹出栈,以实现队列
Q。
再假设A和B都为空,可以认为栈A提供入队列的功能,栈B提供出队列的功能。
要入队列,入栈A即可,而出队列则需要分两种情况考虑:
(1)如果栈B不为空,则直接弹出栈B的数据。
(2)如果栈B为空,则依次弹出栈A的数据,放入栈B中,再弹出栈B的数据。
实现代码如下:
class Stack:
#模拟栈
def __init__(self):
self.items=[]
#判断栈是否为空
def empty(self):
return len(self.items)==0
#返回栈的大小
def size(self):
return len(self.items)
#返回栈项元素
def peek(self):
if not self.empty():
return self.items[len(self.items)-1]
else:
return None
#弹栈
def pop(self):
if len(self.items)>0:
return self.items.pop()
else:
print "栈已经为空"
return None
#压栈
def push(self,item):
self.items.append(item)
class MyStack:
def __init__(self):
self.A=Stack()#用来存储栈中元素
self.B=Stack()#用来存储当前栈中最小的元素
def push(self,data):
self.A.push(data)
def pop(self):
if self,B.empty():
while notself.A.empty():
self.B.push(self.A.peek())
self.A.pop()
first=self.B.peek()
self.B.pop()
return first
if __name__=="__main__":
stack=MyStack()
stack.push(1)
stack.push(2)
print "队列首元素为: "+str(stack.pop())
print "队列首元素为: "+str(stack.pop())
程序的运行结果为:
队列首元素为:1
队列首元素为:2
算法性能分析:
这种方法入队列操作的时间复杂度为O(1),出队列操作的时间复杂度则依赖于入队列与出队列执行的
频率。总体来讲,出队列操作的时间复杂度为O(1),当然会有个别操作需要耗费更多的时间(因为需要
从两个栈之间传输数据)。
');