首先 要利用 两个栈实现队列就是要将一个数据从一个栈弹出后压入另一个栈
基于这个想法 当有两个栈时大小为m 和 n m>n时
要让所有元素都经过两个栈的push和pop操作 那么重要的就是这个队列大小了
考虑当队列最大容量是 m 时,假设此时有m 次pop操作那么此时就要把所有的元素都pop到n中(最多只能在m中留一个元素) 然后先pop m中的元素,再pop n中元素,这种情况只在 m = n+1 时才能正确模拟一个队列,其他情况都可能会出错
现在考虑队列最大容量为 n 时,因为 m > n 所以不管一连串的操作是什么,都能够模拟一个队列
举个例子当 n 不满时,此时如果要取队列中的第一个元素就将检测 m 中是否有元素,如果有就pop出来,没有就将n中元素pop到m中然后取栈顶元素 同样是当n不满时,此时如果要push一个元素,先检测此时队列是否满了,如果没有就push到n中
在考虑一下可以发现其实n+1的大小也是可以的,即极限情况 m 中有n个元素,n 中有 1个元素
为什么可以呢,考虑一下其实可发现 会造成队列模拟失败的原因就是当 m 中 有元素且当 n 中元素已满时 此时如果再push一个元素,就不得不将所有的n中元素pop到n中.假设此时m中只有一个元素那么此时队列就以经满了 不能再进行push操作,要pop时只要pop出m中元素即可,当m中元素大于等于两个时,虽然此时满了但是在pop出一个m 中元素以后,m还有元素而此时已经可以进行push操作了,就会造成失败,所以队列最多就只能有n+1个元素
代码如下
#include <stack> #include <cstdio> using namespace std; struct myqueue{ int m; int n; stack<int> stm; stack<int> stn int MAX; myqueue(int _m , int _n) { m = _m; n = _n; MAX = n + 1; } bool isfull() { return MAX == stm.size() + stn.size(); } bool isempty() { return 0 == stm.size() + stn.size(); } void push(int v) { if(stn.size() == n) { while(!stn.empty()) { int tmp = stn.top(); stn.pop(); stm.push(tmp); } } stn.push(v); } int pop() { if(!stm.empty()) { int temp = stm.top(); stm.pop(); return temp; }else if(!stn.empty()) { int temp = stn.top(); stn.pop(); return temp; } } }; int main () { myqueue myq(18,10); for(int i= 0 ;i < 100;i++) { if(!myq.isfull()) { myq.push(i); } } while(!myq.isempty()) { printf("%d\n",myq.pop()); } return 0; }转载于:https://www.cnblogs.com/tclan126/p/8665956.html
