栈结构:先进后出,后进先出,只允许在栈尾操作。
队列:先进先出,在队尾入队,在队头出队。
要想用两个栈实现一个队列,就需要使用一个相当于中间量的结构进行队列的入队和出队操作。
用图形象化为:
这样问题就从图中得出了思路:
入队操作:把入队元素一一存入一个栈结构中即可。
出队操作:出队时,先判断另一个栈结构中是否有元素,若有先将元素出栈Pop();若为空,则把栈S1中的元素全部倒入Push()栈S2中,然后让S2栈顶元素出栈Pop(),此时的元素序列和栈S1中刚好相反,即达到出队效果。
那么,用代码实现也变得简单:
#include<iostream> #include<stack> usingnamespacestd; classQueue { public: voidPush_Queue(intval) { s1.push(val);//实现了入队尾入队操作 cout<<s1.top()<<""; } voidPop_Queue() { if(s2.empty()) { while(s1.top()) { s2.push(s1.top()--); } s2.pop();//实现了队头出队操作 } else { s2.pop(); } } voidShow() { cout<<endl; //因为使用的是系统库stack,其pop函数返回值为void,所以不能打印出来,我们只打印pop后的队头元素进行验证 cout<<s2.top()<<endl; } private: stack<int>s1; stack<int>s2; }; intmain() { Queueq;//??构造函数的参数 q.Push_Queue(1); q.Push_Queue(2); q.Push_Queue(3); q.Push_Queue(4); q.Push_Queue(5); q.Pop_Queue(); q.Show();//打印pop后的对头元素 system("pause"); return0; }
如有纰漏,欢迎指正。
本文出自 “Vs吕小布” 博客,请务必保留此出处http://www.jb51.cc/article/p-cvrhtoms-ms.html