设计包孕min函数的栈

设计包含min函数的栈

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素，要求函数min，push及pop的时间复杂度都是O(1)

栈的数据结构包含两个普通栈，一个栈存数据，另一个栈存最小值（或最小值的位置，如果用stl里的栈，则不能存最小值的位置，因为stl里的stack不支持下标索引访问）。

1. #include <iostream>   #include <stack>   
2. #include <assert.h>   using namespace std;  
3.   template <typename T>  
4. class StackWithMin  {  
5. private:      stack<T> datastack;  
6.     stack<T> minstack;//存最小值而不是最小值的下标  public:  
7.     void push(const T &data)      {  
8.         datastack.push(data);          if(0==minstack.size())  
9.             minstack.push(data);          else if(minstack.top()>data)  
10.             minstack.push(data);          else  
11.             minstack.push(minstack.top());      }  
12.     void pop()      {  
13.         assert(datastack.size()>0);          assert(minstack.size()>0);  
14.         datastack.pop();          minstack.pop();  
15.     }      int& min()  
16.     {          return minstack.top();  
17.     }    
18. };    
19. void main()  {  
20.     StackWithMin<int> s;      s.push(10);  
21.     s.push(7);      s.push(3);  
22.     s.push(3);      s.push(8);  
23.     s.push(5);      s.push(2);  
24.     s.push(6);      for(int i=0; i<8; i++)  
25.     {          cout<<s.min()<<endl;  
26.         s.pop();      }  
27.   }