栈和队列都是常用的数据结构，有时候需要大量进行输出栈/队列里的最大/小值，假如每次都调用min/max函数，效率是O（n），这对于大量操作而言，是不够满意的。因此，可以设计支持平均O（1）时间复杂度返回大小值的min stack和max queue。至于最小最大，原理都是一样的，稍微改一下就可以变成另外一种。
- min stack
class MinStack:
def __init__(self):
self.min = None
self.stack = []
# @param x, aninteger
# @return an integer
def push(self, x):
if not self.stack:
self.stack.append(0)
self.min = x
else:
self.stack.append(x - self.min)
if x < self.min:
self.min = x
# @return nothing
def pop(self):
x = self.stack.pop()
if self.stack:
if x < 0:
self.min = self.min - x
else:
x = self.min
self.min = None
print(x)
# @return aninteger
def top(self):
x = self.stack[-1]
if x > 0:
return x + self.min
else:
return self.min
# @return aninteger
def getMin(self):
return self.min
这个实现很巧妙，只用一个数组就实现了最小栈。关键就是不直接放入数值n，而是放入n-min，这样假如n大于min，那么在数组里面体现就是正数，否则是负数，出栈的时候就可以根据情况更新。
假如出栈的时候是正数，说明其入栈的时候不是最小值，可以直接出；否则，说明其就是最小值，因为当时入栈的值其实是n-min_prev，而现在的min其实是n，因此min_prev = n - (n - min_prev)也就是现在的min去减pop出来的值，从而还原n入栈之前的最小值。
同样，top看的数，也是n-min_prev，只不过不用更新min值，假如大于0，说明min还是之前的，相加即可；否则，说明min更新为当前数，直接返回min。
不过有一点需要注意，就是栈为空的时候的处理。
这个做法效率非常高，空间和时间复杂度都是O（1）（因为本来就需要一个栈，不算额外空间复杂度）。
- max queue
from collections import deque
class maxQ:
def __init__(self):
self.D = deque()
self.Max = deque()
def push(self, n):
self.D.append(n)
while self.Max and self.Max[-1] < n:
self.Max.pop()
self.Max.append(n)
def pop(self):
if self.Max[0] == self.D[0]:
self.Max.popleft()
self.D.popleft()
def getMax(self):
return self.Max[0]
队列的情况和栈完全不一样。可以使用两个双端队列，一个专门放max值，每次push进入一个数，就把其值放在max队列里面，并pop掉前面所有比它小的。这是因为，刚刚进来的这个数比之前所有数保留在队列里的时间都久，因此假如有一些值比它还小，因为那些数在它前面出去，所以不可能有机会成为队列的max。相等的值要留下来，这是为了pop。这样max queue的元素是按照降序排列的。
然后就是pop的时候更新max。假如pop出去的是max，那就把它也从max里面pop掉。因为保留了相等的，假如后面有一样的，也不至于全部都删掉。
max queue的效率低一些，push操作平均是O（1），因为有时候需要连续pop。然后需要额外的O（n）空间。
有了这两个数据结构，max stack和min queue也是可以得到的，原理相同稍作修改，此处不再赘述。
