在实现栈的基本功能的基础上，再实现返回栈中所有元素的最小值：
其中一种思想是用两个栈，一个栈作为常规的栈dataStack，另一个栈来维护当前栈内最小值minStack。入栈的时候如果常规栈为空，则将入栈值同时放入minStack和dataStack，否则比较入栈值和minStack栈顶元素的大小关系，如果小于或等于minStack栈顶元素值，则同时将入栈值压入minStack，否则不操作minStack。在出栈前比较minStack和dataStack栈顶元素的大小如果dataStack的栈顶元素小于等于minStack的栈顶元素，则同时弹出栈顶元素，否则仅弹出dataStack的栈顶元素，完成出栈操作。
以下操作入栈均使用数组[2, 3, 5, 1, 3, 1, 2]
python实现如下：
class myStack:
dataStack=[]
minStack=[]
def getMin(self):
if self.dataStack:
return self.minStack[-1]
return None
def push(self,ivalue):
if self.minStack:
if self.minStack[-1]>=ivalue:
self.minStack.append(ivalue)
else:
self.minStack.append(ivalue)
self.dataStack.append(ivalue)
print('入栈值',ivalue)
print('dataStack：', self.dataStack)
print(' minStack：', self.minStack)
def pop(self):
p=None
if self.dataStack:
p=self.dataStack.pop()
if p<=self.minStack[-1]:
self.minStack.pop()
print('出栈值', p)
print('dataStack：', self.dataStack)
print(' minStack：', self.minStack)
return p
运行结果如下：
入栈值 2 ,getMin: 2 dataStack： [2] minStack： [2] 入栈值 3 ,getMin: 2 dataStack： [2, 3] minStack： [2] 入栈值 5 ,getMin: 2 dataStack： [2, 3, 5] minStack： [2] 入栈值 1 ,getMin: 1 dataStack： [2, 3, 5, 1] minStack： [2, 1] 入栈值 3 ,getMin: 1 dataStack： [2, 3, 5, 1, 3] minStack： [2, 1] 入栈值 1 ,getMin: 1 dataStack： [2, 3, 5, 1, 3, 1] minStack： [2, 1, 1] 入栈值 2 ,getMin: 1 dataStack： [2, 3, 5, 1, 3, 1, 2] minStack： [2, 1, 1] 出栈值 2 ,getMin: 1 dataStack： [2, 3, 5, 1, 3, 1] minStack： [2, 1, 1] 出栈值 1 ,getMin: 1 dataStack： [2, 3, 5, 1, 3] minStack： [2, 1] 出栈值 3 ,getMin: 1 dataStack： [2, 3, 5, 1] minStack： [2, 1] 出栈值 1 ,getMin: 2 dataStack： [2, 3, 5] minStack： [2] 出栈值 5 ,getMin: 2 dataStack： [2, 3] minStack： [2] 出栈值 3 ,getMin: 2 dataStack： [2] minStack： [2] 出栈值 2 ,getMin: None dataStack： [] minStack： []
上面的实现方式在入栈和出栈都要进行判断，判断是需要时间成本的。入栈的判断是不能省去的，如果每次入栈的时候都压入值到minStack，那出栈的时候就不用做任何判断直接弹出minStack的栈顶值，这样minStack中元素始终和dataStack中元素数目相等。想完成这个想法只需每次向dataStack中压入数据的时候同时向minStack压入min(minStack[-1],待压入元素)即可。
实现如下：
class myStack1:
dataStack=[]
minStack=[]
def getMin(self):
if self.dataStack:
return self.minStack[-1]
return None
def push(self,ivalue):
if self.minStack:
if self.minStack[-1]>=ivalue:
self.minStack.append(ivalue)
else:
self.minStack.append(self.minStack[-1])
else:
self.minStack.append(ivalue)
self.dataStack.append(ivalue)
print('入栈值', ivalue, ',getMin:', self.getMin())
print('dataStack：', self.dataStack)
print(' minStack：', self.minStack)
def pop(self):
p=None
if self.dataStack:
self.minStack.pop()
p= self.dataStack.pop()
print('出栈值', p, ',getMin:', self.getMin())
print('dataStack：', self.dataStack)
print(' minStack：', self.minStack)
return p
运行结果如下，可以看到任何时刻minStack和dataStack中的元素数目都是相等的：
入栈值 2 ,getMin: 2 dataStack： [2] minStack： [2] 入栈值 3 ,getMin: 2 dataStack： [2, 3] minStack： [2, 2] 入栈值 5 ,getMin: 2 dataStack： [2, 3, 5] minStack： [2, 2, 2] 入栈值 1 ,getMin: 1 dataStack： [2, 3, 5, 1] minStack： [2, 2, 2, 1] 入栈值 3 ,getMin: 1 dataStack： [2, 3, 5, 1, 3] minStack： [2, 2, 2, 1, 1] 入栈值 1 ,getMin: 1 dataStack： [2, 3, 5, 1, 3, 1] minStack： [2, 2, 2, 1, 1, 1] 入栈值 2 ,getMin: 1 dataStack： [2, 3, 5, 1, 3, 1, 2] minStack： [2, 2, 2, 1, 1, 1, 1] 出栈值 2 ,getMin: 1 dataStack： [2, 3, 5, 1, 3, 1] minStack： [2, 2, 2, 1, 1, 1] 出栈值 1 ,getMin: 1 dataStack： [2, 3, 5, 1, 3] minStack： [2, 2, 2, 1, 1] 出栈值 3 ,getMin: 1 dataStack： [2, 3, 5, 1] minStack： [2, 2, 2, 1] 出栈值 1 ,getMin: 2 dataStack： [2, 3, 5] minStack： [2, 2, 2] 出栈值 5 ,getMin: 2 dataStack： [2, 3] minStack： [2, 2] 出栈值 3 ,getMin: 2 dataStack： [2] minStack： [2] 出栈值 2 ,getMin: None dataStack： [] minStack： []
既然元素相同行得通，有没有可能只用一个栈来实现题目的要求呢，当然是可以的，我往栈中压入元组如何呢[1,1]，左边元素相当于dataStack中元素，右边元素相当于minStack中的元素。
python实现如下：
class myStack2:
dataStack=[]
def getMin(self):
if self.dataStack:
return self.dataStack[-1][1]
return None
def push(self,ivalue):
if self.dataStack:
tpmin=self.dataStack[-1][1]
if tpmin>ivalue:
self.dataStack.append((ivalue,ivalue))
else:
self.dataStack.append((ivalue,tpmin))
else:
self.dataStack.append((ivalue, ivalue))
print('入栈值', ivalue, ',getMin:', self.getMin())
print('dataStack：', self.dataStack)
def pop(self):
p=None
if self.dataStack:
p=self.dataStack.pop()
p=p[0]
print('出栈值', p, ',getMin:', self.getMin())
print('dataStack：', self.dataStack)
return p
我们来运行一下：
入栈值 2 ,getMin: 2 dataStack： [(2, 2)] 入栈值 3 ,getMin: 2 dataStack： [(2, 2), (3, 2)] 入栈值 5 ,getMin: 2 dataStack： [(2, 2), (3, 2), (5, 2)] 入栈值 1 ,getMin: 1 dataStack： [(2, 2), (3, 2), (5, 2), (1, 1)] 入栈值 3 ,getMin: 1 dataStack： [(2, 2), (3, 2), (5, 2), (1, 1), (3, 1)] 入栈值 1 ,getMin: 1 dataStack： [(2, 2), (3, 2), (5, 2), (1, 1), (3, 1), (1, 1)] 入栈值 2 ,getMin: 1 dataStack： [(2, 2), (3, 2), (5, 2), (1, 1), (3, 1), (1, 1), (2, 1)] 出栈值 2 ,getMin: 1 dataStack： [(2, 2), (3, 2), (5, 2), (1, 1), (3, 1), (1, 1)] 出栈值 1 ,getMin: 1 dataStack： [(2, 2), (3, 2), (5, 2), (1, 1), (3, 1)] 出栈值 3 ,getMin: 1 dataStack： [(2, 2), (3, 2), (5, 2), (1, 1)] 出栈值 1 ,getMin: 2 dataStack： [(2, 2), (3, 2), (5, 2)] 出栈值 5 ,getMin: 2 dataStack： [(2, 2), (3, 2)] 出栈值 3 ,getMin: 2 dataStack： [(2, 2)] 出栈值 2 ,getMin: None dataStack： []
嗯，功能是一样的，但是有什么区别呢。我们来上一千万次入栈和出栈操作试试！！！！
def test():
st = myStack()
tst = time.time()
for i in range(10000000):
st.push(1)
for j in range(10000000):
st.pop()
ted = time.time() - tst
print('myStack time:', ted)
del st
time.sleep(2)
st=myStack1()
tst=time.time()
for i in range(10000000):
st.push(1)
for j in range(10000000):
st.pop()
ted=time.time()-tst
print('myStack1 time:',ted)
del st
time.sleep(2)
st = myStack2()
tst = time.time()
for i in range(10000000):
st.push(1)
for j in range(10000000):
st.pop()
ted = time.time() - tst
print('myStack2 time:', ted)
结果：
myStack time: 7.706661224365234 myStack1 time: 7.179437875747681 myStack2 time: 8.115821123123169
可以看到方案一最节省空间，方案二时间效率最高，方案三在特殊要求的时候例如要求使用一个栈来实现。
