1 /************************************************************************* 2     > File Name: 19_MinInStack.cpp 3     > Author: Juntaran 4     > Mail: JuntaranMail@gmail.com 5     > Created Time: 2016年08月30日 星期二 19时29分48秒 6  ************************************************************************/ 7  8 #include <stdio.h> 9 #include <bits/stdc++.h>10 11 using namespace std;12 13 template<class T>14 class minStack15 {16 private:17     stack<T> stack_data;18     stack<T> stack_min;19     20 public:21 22     void push(T &value)23     {24         // 新元素入栈25         stack_data.push(value);26         27         // 新元素比之前最小元素小的时候，新元素进入辅助栈28         // 否则把之前最小元素重复插入辅助栈29         if (stack_min.size()==0 || value<stack_min.top())30             stack_min.push(value);31         else32             stack_min.push(stack_min.top());33     }34     T pop()35     {36         assert(stack_data.size()>0 && stack_min.size()>0);37         stack_data.pop();38         stack_min.pop();39         return stack_data.top();40     }41     T min()42     {43         assert(stack_data.size()>0 && stack_min.size()>0);44         return stack_min.top();45     }46 };47 48 int main()49 {50     minStack<int> mStack;51     for (int i = 0; i < 5; i++)52     {53         cout << i << " push" << endl;54         mStack.push(i);55     }56     cout << "min is " << mStack.min() << endl;57     for (int i = 1; i < 3; i++)58     {59         cout << mStack.pop() << " pop" << endl;60     }61     cout << "min is " << mStack.min() << endl;62     for (int i = 5; i < 7; i++)63     {64         cout << i << " push" << endl;65         mStack.push(i);66     }67     cout << "min is " << mStack.min() << endl;68     for (int i = 1; i < 3; i++)69     {70         cout << mStack.pop() << " pop" << endl;71     }72     int k = -1;73     mStack.push(k);74     cout << "min is " << mStack.min() << endl;75     cout << endl;76 }