问题描述：扩展stack的实现，完成正常的push，pop操作，新增访问最小（或最大）元素的接口Min（），使得push，pop，Min的时间复杂度都是O(1)。
问题分析：拿到这道题，我们最先的思考往往是，设计一个算法从栈中拿到最小值，所以开始考虑任何可以用来实现该功能的排序和查找算法。假设栈中有n个元素，一切排序和查找都不可能实现O(1)的时间复杂度找到最小值。
再看题目，既然是扩展stack的实现，stack是一种数据结构，一种数据的组织方式，扩展它，也就允许我们对其数据组织方式和存储内容作一些改变吧。所以我们就有了下面的思路：
把当前最小值存起来，并且在进行push和pop操作的时维护它。维护要求如下：
1、如果有比当前最小值大的元素入栈，当前最小值不变
2、如果有比当前最小值大的元素入栈，当前最小值变为新加入元素（考虑一下等于的时候啊，呵呵）
3、如果有比当前最小值大的元素出栈，当前最小值不变（注意：弹出的操作时，一定不可能弹出比当前最小值还小的元素，也就是说如果你弹出了一个比当前最小值还小的元素，就证明你的那个当前最小值不是当前最小值）
4、如果有和当前最小值的元素相同出栈，当前最小值变为当前当前最小值入栈之前那个最小值，当前最小值退出。
综上，我们发现一个规律：对于最小值而言，如果有更小的数入栈，需要将其保存为当前最小，如果当前最小数出栈，当前最小数变成
当前最小数入栈之前那个最小数，所以，对于最小数而言也具有先进后出，后进先出的特点，只是并不是每次push和pop操作都牵涉到
最小数的进出。所以我们考虑用双栈来实现，一个栈用来存放数据，满足栈数据结构原始要求，一个栈用来存放最小值，在每次push和
pop操作执行时，按照上面的规则维护最小值栈。
下面是扩展栈的实现：（O(1)的pop，push，和Min访问最小值操作）MinStack.h
#ifndef _H_MINSTACK_H_ #define _H_MINSTACK_H_ #include <iostream> template <class T> class MinStack { public: MinStack():MaxSize(20) { top=MinTop=-1; stack=new T[MaxSize]; Mins=new T[MaxSize]; } MinStack(int MaxSize); ~MinStack() { delete [] stack; delete [] Mins; } bool isEmpty(){return top==-1;} bool isFull(){return top==(MaxSize-1);} MinStack<T>& push(const T& x); MinStack<T>& pop(T& x); T Top(){return stack[top];} T Min(){return Mins[MinTop];} private: int top,MinTop,MaxSize; T *stack,*Mins; }; template <class T> MinStack<T>::MinStack(int MaxSize) { top=MinTop=-1; this->MaxSize=MaxSize; stack=new T[MaxSize]; Mins=new T[MaxSize]; } template <class T> MinStack<T>& MinStack<T>::push(const T& x) { if(isEmpty()) { stack[++top]=x; Mins[++MinTop]=x; } else { if(isFull()) { std::cout<<"no space "<<std::endl; } else { stack[++top]=x; if(x<=Mins[MinTop])//注意“==”时也要压入 Mins[++MinTop]=x; } } return *this; } template <class T> MinStack<T>& MinStack<T>::pop(T& x) { if(isEmpty()) { std::cout<<"Stack is empty"<<std::endl; } else { x=stack[top--]; if(x==Mins[MinTop]) --MinTop; } } #endif //_H_MINSTACK_H_
下面是测试（MinStacktest.cc）
#include <iostream> #include "MinStack.h" int main() { MinStack<int> ms(20); ms.push(20);ms.push(22);ms.push(18); std::cout<<"the Minest value is "<<ms.Min()<<std::endl; ms.push(11);ms.push(44);ms.push(5); std::cout<<"the Minest value is "<<ms.Min()<<std::endl; int x; ms.pop(x); std::cout<<"the Minest value is "<<ms.Min()<<std::endl; return 0; }
编译运行结果如下：
[jim@gpu1 stack]$ g++ -o MinStacktest MinStacktest.cc MinStack.h [jim@gpu1 stack]$ ./MinStacktest the Minest value is 18the Minest value is 5the Minest value is 11
2011-04-20
