设计包含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. }