实现一个栈，要求实现Push（入栈）、Pop（出栈）、Min（返回最小值的操作）的时间复杂度为O(1)

具体实现如下：

#include<iostream>#include<stack>#include<string>#include<assert.h>usingnamespacestd;template<classT>classStack{public:voidPush(constT&x);voidPop();T&Min();voidPrintS();private:stack<T>Sk;//存放栈中所有元素的stack<T>MinSk;//存放栈中最小元素的};template<classT>voidStack<T>::Push(constT&x){Sk.push(x);//当MinSk为空时，先存放一个元素；当比较入栈元素小于栈顶元素时，入栈if(MinSk.empty()||x<MinSk.top()){MinSk.push(x);}}template<classT>voidStack<T>::Pop(){if(Sk.empty()){cout<<"stackisempty!"<<endl;return;}//如果出栈元素等于MinSk中栈顶元素，则MinSk需pop()该元素，使MinSk栈顶始终存放Sk栈中最小元素if(Sk.top()==MinSk.top()){MinSk.pop();}Sk.pop();}template<classT>T&Stack<T>::Min(){assert(!MinSk.empty());returnMinSk.top();}template<classT>voidStack<T>::PrintS(){if(Sk.empty()){cout<<"stackisempty!"<<endl;return;}stack<T>tmp=Sk;stack<T>mintmp=MinSk;cout<<"stack:";while(!tmp.empty()){cout<<tmp.top()<<"";tmp.pop();}cout<<"\nminstack:";while(!mintmp.empty()){cout<<mintmp.top()<<"";mintmp.pop();}cout<<endl;}//测试用例voidTest4(){//Stack<int>s1;//s1.Push(9);//s1.Push(5);//s1.Push(7);//s1.Push(3);//s1.Push(8);////s1.Pop();////s1.Pop();////s1.Pop();////s1.Pop();////s1.Pop();////s1.Pop();Stack<string>s1;s1.Push("sssss");s1.Push("syikl");s1.Push("yyyyy");s1.Push("fffff");s1.Push("lllll");s1.PrintS();cout<<s1.Min()<<endl;}

【干货小知识】自主实现一个栈，具体实现如下：

template<classT>classStack{public:Stack():_arr(NULL),_size(0),_capacity(0){}Stack(constStack<T>&s):_arr(newT[s._size]),_size(s._size),_capacity(s._size){for(size_ti=0;i<_size;i++){_arr[i]=s._arr[i];}}Stack<T>&operator=(constStack<T>&s){if(this!=&s){T*tmp=newT[s._size];delete[]_arr;for(size_ti=0;i<s._size;i++){tmp[i]=s._arr[i];}_arr=tmp;_size=s._size;_capacity=s._capacity;}return*this;}~Stack(){if(_arr){delete[]_arr;}}public:void_CheckCapacity(size_tsize){if(size>_capacity){_capacity+=_capacity*2+3;}T*tmp=newT[_capacity];if(_arr){for(size_ti=0;i<_size;i++){tmp[i]=_arr[i];}}delete[]_arr;_arr=tmp;}voidPush(constT&x){_CheckCapacity(_size+1);_arr[_size++]=x;}voidPop(){assert(_size>0);--_size;}boolEmpty(){return_size==0;}size_tSize(){return_size;}T&Top(){return_arr[_size-1];}voidPrintStack(){if(_size==0){cout<<"Stackisempty!";}else{for(size_ti=0;i<_size;i++){cout<<_arr[i]<<"";}cout<<endl;}}private:T*_arr;size_t_size;size_t_capacity;};