【正确答案】题目要求用两个栈来模拟队列，假设使用栈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)，当然会有个别操作需要耗费更多的时间(因为需要从两个栈之间传输数据)。