定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
自己用c语言编写的一个程序，是按照数据结构书上给出的结构。如果不对的地方请指教。同时会给出c++的设计。
c++代码，我是用vector实现的，但是看到网上还是有高手用到双端队列，我也会试着用双端队列实现一下的，自己写的这两个程序基本没什么大的改变，大家可以用另一种思路，就是记录最小元素的位置。
#include<iostream>#include<vector>using namespace std;class StackWithMin{private:vector<int> m_data;vector<int> min_data;public:StackWithMin() {}~StackWithMin() {while(m_data.size() > 0)m_data.pop_back();while(min_data.size() > 0)min_data.pop_back();}void push(int e) {m_data.push_back(e);if(min_data.size() == 0) {min_data.push_back(e);} else {if(e <= min_data.back())min_data.push_back(e);}}void pop(int *e) {if(m_data.size() > 0) {*e = m_data.back();m_data.pop_back();if(*e <= min_data.back())min_data.pop_back();} else {cout << "error,no elements" << endl;}}void min(int *min) {if(min_data.size() > 0){*min = min_data.back();} else {cout << "error,no elements" << endl;}}};int main() {int min_data;int pop_data;StackWithMin m_stack;m_stack.push(3);m_stack.min(&min_data);cout << "min_data=" << min_data << endl;m_stack.push(4);m_stack.min(&min_data);cout << "min_data=" << min_data << endl;m_stack.push(2);m_stack.min(&min_data);cout << "min_data=" << min_data << endl;m_stack.push(1);m_stack.min(&min_data);cout << "min_data=" << min_data << endl;m_stack.pop(&pop_data);m_stack.min(&min_data);cout << "pop_data=" << pop_data << ","<<"min_data=" << min_data << endl;m_stack.pop(&pop_data);m_stack.min(&min_data);cout << "pop_data=" << pop_data << ","<<"min_data=" << min_data << endl;m_stack.pop(&pop_data);m_stack.min(&min_data);cout << "pop_data=" << pop_data << ","<<"min_data=" << min_data << endl;m_stack.push(0);m_stack.min(&min_data);cout << "min_data=" << min_data << endl;return 0;}
