最近本博主在复习数据结构，不不不！！！应该是预习，因为把上学期学的基本上全都还给脑四了，之前写过有关实现库里边栈和队列的文章，经过这几天的坚持不懈的努力，硬是啃了几道有关栈和队列的面试频率较高的题，今天就和大家分享一下下啦！

（一）实现一个栈结构 使得pop push min(获得栈中最小元素)操作的时间复杂度为O(1)

思路：可以用两个栈来实现，一个栈用来push,pop,一个栈用来保存这个过程的最小值，

比如有一组数要入栈

s1:8,9,10,3,2,2

s2:8,3,2,2

要实现这种功能我们可以通过给第二个栈中的每个元素添加一个计数器，当有重复元素进栈的时候，只需给计数器加加即可，那么问题来了，当元素很多的时候，这种方法很浪费空间，所以最好的方法就是重复元素只要比当前第二个栈的栈顶元素小，都可以进栈哦

#include<iostream>#include<stack>usingnamespacestd;template<classT>classStack{public:voidPush(constT&d){if(_s2.empty()||_s2.top()>=d){_s2.push(d);}_s1.push(d);}voidPop(){if(_s1.top()==_s2.top()){_s2.pop();}_s1.pop();}Tmin(){if(_s2.empty()){return-1;}return_s2.top();}voidPrintStack(){while(!_s1.empty()){cout<<_s1.top()<<"";_s1.pop();}cout<<"over"<<endl;}private:stack<T>_s1;stack<T>_s2;};voidtest(){Stack<int>_s;_s.Push(9);_s.Push(10);_s.Push(8);_s.Push(5);_s.Push(2);_s.Push(2);_s.Push(23);_s.PrintStack();_s.min();cout<<_s.min()<<endl;}intmain(){test();system("pause");return0;}


（二）两个队列实现一个栈

#include<iostream>#include<stack>#include<queue>usingnamespacestd;template<typenameT>classStack{public:voidPush(constT&d){//刚开始如果两个队列都为空，则给q1压入数据if(q1.empty()&&q2.empty()){q1.push(d);return;}//如果q2不为空q1为空，则给q2压入数据if(!q2.empty()&&q1.empty()){q2.push(d);return;}//如果q1不为空，q2为空。则给q1压入数据if(!q1.empty()&&q2.empty()){q1.push(d);}}TPop(){//如果q2为空，将q1中元素（除了最顶部）一次出队压入q2中，然后再将q1中剩下的那个元素弹出if(q2.empty()){while(q1.size()>1){q2.push(q1.front());q1.pop();}T&data=q1.front();q1.pop();returndata;}//如果q2不为空，将q2中元素一次出队（除了最定部元素）压入q1中，然后再将q2中剩下的那个元素弹出else{while(q2.size()>1){q1.push(q2.front());q2.pop();}T&data=q2.front();q2.pop();returndata;}}private:queue<T>q1;queue<T>q2;};voidtest(){Stack<int>q1;q1.Push(1);q1.Push(2);q1.Push(3);q1.Push(4);cout<<q1.Pop()<<endl;}intmain(){test();system("pause");return0;}（三）一个数组实现两个栈#include<iostream>#include<assert.h>usingnamespacestd;template<typenameT>classTwoStack{public://栈的构造函数实现TwoStack():_a(0),_top1(0),_top2(0),_Capacity(0){}//栈的析构函数实现~TwoStack(){if(_a!=NULL){delete[]_a;}}//栈的拷贝构造函数实现TwoStack(constTwoStack<T>&ts):_a(newT[ts._Capacity-ts._top2+ts._top1]),_top1(ts._top1),_top2(ts._top2),_Capacity(ts._Capacity-ts._top2+ts._top1){//逐次拷贝两个栈对应的数组序列for(size_ti=0;i<=ts._top1;i++){_a[i]=ts._a[i];}for(size_ti=ts._Capacity-1;i>=ts._top2;i--){_a[i]=ts._a[i];}}//栈的赋值运算符重载函数的实现TwoStack<T>&operator=(constTwoStack<T>&ts){_top1=ts._top1;_top2=ts._top2;_Capacity=ts._Capacity;for(size_ti=0;i<_Capacity;i++){_a[i]=ts._a[i];}return*this;}//压栈函数voidPush(constT&d,intchoice){_CheckCapacity();if(choice==1){_a[_top1++]=d;}if(choice==2){_a[_top2--]=d;}}//元素出栈函数voidPop(intchoice){if(choice==1){assert(_top1>0);--_top1;}if(choice==2){assert(_top2<_Capacity-1);++_top2;}}//求栈顶元素函数T&Top(intchoice){if(choice==1){return_a[_top1-1];}if(choice==2){return_a[_top2+1];}}//判空函数boolempty(intchoice){if(choice==1){return_top1==0;}if(choice==2){return_top2==_Capacity-1;}}//求栈的元素个数函数size_tSize(intchoice){if(choice==1){cout<<"栈1的元素个数为："<<endl;return_top1;}if(choice==2){cout<<"栈2的元素个数为："<<endl;return_Capacity-1-_top2;}}//容量检测函数void_CheckCapacity(){if(_a==NULL){//保证如果数组为空的时候至少能开辟到空间_a=newT[2*_Capacity+3];_top2=_Capacity-1;}//当两个栈顶相遇时需要开辟空间if(_top1==_top2){size_t_oldCapacity=_Capacity;//开辟新空间T*_tmp=newT[_Capacity*2+3];//将原来的内容拷贝到新的空间，然后释放原来的旧空间for(size_ti=0;i<=_top1;i++){_tmp[i]=_a[i];}for(size_ti=_Capacity-1;i>=_top2;i--){_tmp[i]=_a[i];}delete[]_a;_a=_tmp;_top2=_Capacity-1-(_oldCapacity-1-_top2);}}voidprint(){cout<<"栈1为："<<endl;for(size_ti=0;i<_top1;i++){cout<<_a[i]<<"";}cout<<"over"<<endl;cout<<"栈2为："<<endl;for(size_ti=_Capacity-1;i>_top2;i--){cout<<_a[i]<<"";}cout<<"over"<<endl;}private:T*_a;//数组size_t_top1;size_t_top2;size_t_Capacity;};voidtest(){TwoStack<int>ts1;ts1.Push(1,1);ts1.Push(2,1);ts1.Push(3,1);ts1.Push(4,1);ts1.Pop(1);ts1.Size(1);ts1.Push(4,2);ts1.Push(5,2);ts1.Push(6,2);ts1.Push(7,2);ts1.print();TwoStack<int>ts2(ts1);cout<<"ts2----------"<<endl;ts2.print();TwoStack<int>ts3;ts3=ts1;cout<<"ts3----------"<<endl;ts3.print();}intmain(){test();system("pause");return0;}


（四）出栈，入栈顺序的合法性

#include<iostream>#include<assert.h>#include<stack>usingnamespacestd;template<classT>boolIsValid(constT*stack_in,constT*stack_out,size_tsize1,size_tsize2){assert(stack_in);assert(stack_out);stack<T>s;//如果两个序列不相等，则直接返回if(size1!=size2){returnfalse;}s.push(*stack_in++);--size1;while(size2){//输入序列为1,2,3,4,5输出序列为1,3,2,4,5if(s.top()==*stack_out){s.pop();stack_out++;--size2;continue;}if(s.empty()&&size1){s.push(*stack_in++);--size1;}while((s.top()!=*stack_out)&&size1){s.push(*stack_in++);--size1;}if(size1==0&&(s.top()!=*stack_out)){returnfalse;}}returntrue;}intmain(){intarr1[]={1,2,3,4,5};intarr2[]={4,3,5,2,1};size_tsize1=sizeof(arr1)/sizeof(arr1[0]);size_tsize2=sizeof(arr2)/sizeof(arr2[0]);boolret=IsValid(arr1,arr2,size1,size2);cout<<ret<<endl;getchar();return0;}

（五）两个栈实现一个队列

#include<iostream>#include<stack>#include<queue>usingnamespacestd;template<typenameT>classQueue{public://队列入队操作voidPush(constT&d){_s1.push(d);}//队列出队操作voidPop(){if(_s1.empty()&&_s2.empty()){cout<<"Queueisempty"<<endl;}if(!_s1.empty()&&_s2.empty()){while(!_s1.empty()){_s2.push(_s1.top());_s1.pop();}}if(_s1.empty()&&!_s2.empty()){cout<<_s2.top()<<"";_s2.pop();}}boolEmpty(){return(_s1.()==0&&_s2.size()==0);}private:stack<T>_s1;stack<T>_s2;};voidtest(){Queue<int>s1;s1.Push(1);s1.Push(2);s1.Push(3);s1.Push(4);s1.Pop();s1.Pop();s1.Pop();}intmain(){test();system("pause");return0;}