【练习3.22】
a.提出支持栈的Push和Pop操作以及第三种操作FindMin的数据结构，其中FindMin
返回该数据结构的最小元素，所有操作在最坏情况下的运行时间都是O(1)。
b.证明，如果我们加入第四种操作DeleteMin，那么至少有一种操作必须花费Ω(logN)时间。
【练习3.23】
说明如何用一个数组实现三个栈。
【练习3.24】
在2.4节中用于计算斐波那契的递归例程如果在N=50下运行，栈空间有可能用完吗，为什么？
Answer:
【练习3.22】
a.最简单的想法就是再维护一个最小值域，有更小的值被Push入栈的时候，修改最小值。
但这种方法会导致当前的最小值Pop出栈的时候无法获得新的最小值。
相应地把这个最小值域扩展成一个辅助栈。
当新入主栈的元素大于当前最小值时，不作任何附加操作；当新入主栈的元素小于当前最小值时，拷贝一份压入辅助栈。
同理弹出时如弹出的是当前最小值，则辅助栈同时弹出；否则仅主栈弹出。
Push、Pop、FindMin的时间复杂度都是O(1)。
b.当一个操作集共同拥有Pop、Push、FindMin、DeleteMin的时候，它就可以通过比较的方法来执行一组元素的排序了。
确切地说，只要后三个操作共同存在即可。如共N个元素排序，则Push、FindMin、DeleteMin各需N次必然可以完成条件。
众所周知的结论是，以比较的方法来进行排序，其时间复杂度下界为Ω(NlogN)，相除有：
执行一次Push+FindMin+DeleteMin的时间复杂度下界为Ω(logN)。
这说明这三个操作不能同时以O(1)时间复杂度共存，至少有一个的复杂度必须花费Ω(logN)。
【练习3.23】
其实自己想是没怎么想出来的，看了答案以后觉得答案的方法也是个坑爹方法，如下：
一个数组，就如同之前题目所模拟的，一个栈从左一个从右开始向中间走，这是两个栈。
第三个栈的起点在数组的中间，一开始，选择任意一个方向扩张，当受阻时，计算并将数据位移到当前数组空间的正中。
………………………………(╯‵□′)╯︵┻━┻
这算是解决办法么！一点效率也没有好不好！照这么说一个数组模拟一百个栈都可以了！
总之答案这么说也只能这样了……
【练习3.24】
N=50妥妥地溢出。
求斐波那契用递归就是指数型增长的时间复杂度。栈空间才多少，50次方下来几个T都不够用。