包含min函數的棧，包含min函數

包含min函數的棧，包含min函數

題目：定義棧的數據結構，要求添加一個min函數，能夠得到棧的最小元素。要求函數min、push以及pop的時間復雜度都是O(1)。

分析:除了題目要求的棧之外新開一個棧,用來記錄最小值,每當在原棧中push數據後,與最小值棧中的棧頂元素比較,如果新值較小,則在最小值棧中push新值;否則再次push棧頂元素.pop的時候,只要將最小值棧也pop一下就行了.這樣,min函數只需要返回最小值棧的棧頂元素即可.

 1 #include<stack>
 2 #include<assert.h>
 3 #include<stdio.h>
 4 #include<tchar.h>
 5 
 6 template<typename T>class  StackWithMin
 7 {
 8 public:
 9     StackWithMin(void) {}
10     virtual ~StackWithMin(void) {}
11 
12     T& top(void);
13     const T& top(void) const;
14 
15     void push(const T& value);
16     void pop(void);
17 
18     const T& min(void) const;
19 
20     bool empty() const;
21     size_t size() const;
22 
23 private:
24     std::stack<T> m_data;
25     std::stack<T> m_min;
26 };
27 
28 template <typename T>void StackWithMin<T>::push(const T& value)
29 {
30     m_data.push(value);
31 
32     if(m_min.size() == 0 || value < m_min.top())
33         m_min.push(value);
34     else
35         m_min.push(m_min.top());
36 }
37 
38 
39 template <typename T>void StackWithMin<T>::pop()
40 {
41     assert(m_data.size() > 0 && m_min.size() > 0);
42 
43     m_data.pop();
44     m_min.pop();
45 }
46 
47 template<typename T>const T& StackWithMin<T>::min() const
48 {
49     assert(m_data.size()>0 && m_min.size() >0);
50 
51     return m_min.top();
52 }
53 
54 template<typename T>T& StackWithMin<T>::top()
55 {
56     return m_data.top();
57 }
58 template <typename T>const T& StackWithMin<T>::top() const
59 {
60     return m_data.top();
61 }
62 
63 template <typename T> bool StackWithMin<T>::empty() const
64 {
65     return m_data.empty();
66 }
67 
68 template<typename T> size_t StackWithMin<T>::size() const
69 {
70     return m_data.size();
71 }
72 
73 void Test(char* testName, const StackWithMin<int>& stack, int expected)
74 {
75     if(testName != NULL)
76         printf("%s begins: \n", testName);
77     if(stack.min() == expected)
78         printf("Passed.\n");
79     else
80         printf("Failed.\n");
81 }
82 
83 int main()
84 {
85     StackWithMin<int> stack;
86     stack.push(3);
87     printf("min = %d\n", stack.min());
88     stack.push(4);
89     printf("min = %d\n", stack.min());
90     stack.push(2);
91     printf("min = %d\n", stack.min());
92     stack.pop();
93     printf("min = %d\n", stack.min());
94     
95     return 0;
96 }