求栈中的最小元素

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

主要难点：将当前最小的元素min出栈之后，如何快速找到下一个最小的元素？因此需要一个辅助栈，每次push一个新元素的时候，同时将最小元素push到辅助栈中；每次pop一个元素出栈的时候，同时pop辅助栈。考虑到栈元素的类型可能是复杂的数据结构，在辅助栈中用最小元素的位置将能减少空间消耗。

代码：

 1 #include <iostream>
 2 #include <deque>
 3 #include <assert.h>
 4 #include <conio.h>
 5 using namespace std;
 6 template <typename T> 
 7 class stackWithMin
 8 {
 9  public :
10      stackWithMin(){};
11      virtual ~stackWithMin(){};
12      T& top();
13      const T& top() const;
14      void pop();
15      void push(const T& value);
16      const T& min() const;
17 private:
18     deque<T> m_data;              // 用一个deque来保存栈里的数据，类型为模板类型T
19     deque<size_t> m_minIndex;     // 用一个deque来保存栈里的最小数据的位置，类型为size_t
20 };
21 
22 template <typename T> T& stackWithMin<T>::top()
23 {
24     return m_data.back();
25 }
26 template <typename T> const T& stackWithMin<T>::top() const
27 {
28     return m_data.back();
29 }
30 template <typename T> void stackWithMin<T>::pop()
31 {
32     m_data.pop_back();
33     m_minIndex.pop_back();
34 }
35 
36 template <typename T> void stackWithMin<T>::push(const T& value)
37 {
38      m_data.push_back(value);
39      if(m_minIndex.size() == 0)
40      {
41          m_minIndex.push_back(0);
42      }
43      else
44      {
45          if(value < m_data[m_minIndex.back()])
46          {
47              m_minIndex.push_back(m_data.size() - 1);
48          }
49          else
50          {
51              m_minIndex.push_back(m_minIndex.back());
52          }
53      }
54 }
55 template <typename T> const T& stackWithMin<T>::min() const
56 {
57      assert(m_data.size() > 0);
58      assert(m_minIndex.size() > 0);
59      return m_data[m_minIndex.back()];
60 }
61 int main()
62 {
63      int data,choice;
64      stackWithMin<int> int_stack;
65       cout << "1.添加数据" << endl;
66           cout << "2.删除数据" << endl;
67           cout << "3.得到堆栈顶部的数据和堆栈里的min数据" <<endl;
68           cout << "0.退出" <<endl;
69      do
70      {
71           choice = getch();
72           switch(choice)
73           {
74           case '1':
75               cout << "1.添加数据" << endl;
76               cin >> data;
77               int_stack.push(data);
78               break;
79           case '2':
80               cout << "2.删除数据" << endl;
81               int_stack.pop();
82               break;
83           case '3':
84               cout << "3.得到堆栈顶部的数据和堆栈里的min数据" <<endl;
85               cout << int_stack.top() << endl;
86               cout << int_stack.min() <<endl;
87               break;
88           case '0':
89               break;
90           } 
91      }while(choice != '0');
92      getch();
93      return 0;
94 }

View Code