document.write('由于栈具有后进先出的特点，因此，push和pop只需要对栈顶元素进行操作。如果使用上述的实现方式，
只能访问到栈顶的元素，无法得到栈中最小的元素。当然，可以用另外一个变量来记录栈底的位置，通过遍
历栈中所有的元素找出最小值，但是这种方法的时间复杂度为O(N)，那么如何才能用O(1)的时间复杂度求
出栈中最小的元素呢?
在算法设计中，经常会采用空间换取时间的方式来提高时间复杂度，也就是说，采用额外的存储空间来降
低操作的时间复杂度。具体而言，在实现的时候使用两个栈结构，一个栈用来存储数据，另外一个栈用来存
储栈的最小元素。实现思路如下：如果当前入栈的元素比原来栈中的最小值还小，则把这个值压入保存最小
元素的栈中；在出栈的时候，如果当前出栈的元素恰好为当前栈中的最小值，保存最小值的栈顶元素也出
栈，使得当前最小值变为当前最小值入栈之前的那个最小值。为了简单起见，可以在栈中保存int类型。
实现代码如下：
#模拟栈
class Stack:
def __init__(self):
self.items=[]
#判断栈是否为空
def empty(self):
return len(self.items)==0
#返回栈的大小
def size(self):
return len(setf.items)
#返回栈顶元素
def peek(self):
if notself.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.elemStack=Stack() # 用来存储栈中元素
self.minStack=Stack()# 栈顶永远存储当前elemStack中最小的值
def push(self,data):
self.elemStack.push(data)
#更新保存最小元素的栈
if self.minStack.empty().
self.minStack.push(data)
else:
if data＜self.minStack.peek():
self.minStack.push(data)
def pop(self):
topData=self.elemStack.peek()
self.elemStack.pop()
if topData==self.mins():
self.minStack.pop()
return topData
def mins(self):
if self.minStack.empty():
return 2**32
else:
return self.minStack.peek()
if __name__=="__main__":
stack=MyStack()
stack.push(5)
print "栈中最小值为:"+str(stack.mins())
stack.push(6)
print "栈中最小值为:"+str(stack.mins())
stack.push(2)
print "栈中最小值为:"+str(stack.mins())
stack.pop()
print "栈中最小值为:"+str(stack.mins())
程序的运行结果为：
栈中最小值为：5
栈中最小值为：5
栈中最小值为：2
栈中最小值为：5
算法性能分析：
这种方法申请了额外的一个栈空间来保存栈中最小的元素，从而达到了用O(1)的时间复杂度求栈中最小元
素的目的，但是付出的代价是空间复杂度为O(N)。
');