【LeetCode】队列 栈 | 225.用队列实现栈

题目https://leetcode.cn/problems/implement-stack-using-queues/description/思路两个队列利用两个队列倒腾数据保证一个队列始终为空用来暂存除栈顶外的所有元素。每次push总是往非空队列里加保证一个队列为空每次pop/top都把前n-1个元素倒腾到空队列剩下的就是栈顶一个队列利用队列的循环特性通过旋转操作让最后进来的元素跑到最前面。code一个易错的写法使用两个队列classMyStack{DequeIntegerqueue1newArrayDeque();DequeIntegerqueue2newArrayDeque();publicMyStack(){}publicvoidpush(intx){//如果都为空随意放入一个栈中if(empty()){queue1.push(x);}elseif(queue1.isEmpty()true){//queue1为空就放入queue2queue2.push(x);}else{//queue2为空就放入queue1queue1.push(x);}}publicintpop(){//都为空if(empty()){return-1;}elseif(queue1.isEmpty()false){//queue1不为空//前面的都push到queue2中queue2中的顺序也是对的for(inti0;iqueue1.size()-1;i){queue2.push(queue1.pop());}//最后一个popreturnqueue1.pop();}else{//前面的都push到queue1中queue1中的顺序也是对的for(inti0;iqueue2.size()-1;i){queue1.push(queue2.pop());}//最后一个popreturnqueue2.pop();}}publicinttop(){inttmp0;//都为空if(empty()){return-1;}elseif(queue1.isEmpty()false){//前面的都push到queue2中queue2中的顺序也是对的for(inti0;iqueue1.size();i){tmpqueue1.pop();queue2.push(tmp);}//最后一个popreturntmp;}else{//前面的都push到queue1中queue1中的顺序也是对的for(inti0;iqueue2.size();i){tmpqueue2.pop();queue1.push(tmp);}//最后一个popreturntmp;}}publicbooleanempty(){return(queue1.isEmpty()truequeue2.isEmpty()true);}}/** * Your MyStack object will be instantiated and called as such: * MyStack obj new MyStack(); * obj.push(x); * int param_2 obj.pop(); * int param_3 obj.top(); * boolean param_4 obj.empty(); */pop /top方法中的致命错误for(inti0;iqueue1.size()-1;i){queue2.push(queue1.pop());}问题queue1.size()在循环中会动态变化每次queue1.pop()后queue1.size()会减少导致循环次数错误。正确做法应该先保存 size。intsizequeue1.size();for(inti0;isize-1;i){queue2.push(queue1.pop());}修正后的代码使用两个队列classMyStack{DequeIntegerqueue1newArrayDeque();DequeIntegerqueue2newArrayDeque();publicMyStack(){}publicvoidpush(intx){// 简化总是放入非空的队列如果都空则放入 queue1if(queue1.isEmpty()){queue2.push(x);}else{queue1.push(x);}}publicintpop(){if(empty()){return-1;}if(!queue1.isEmpty()){intsizequeue1.size();for(inti0;isize-1;i){queue2.push(queue1.pop());}returnqueue1.pop();}else{intsizequeue2.size();for(inti0;isize-1;i){queue1.push(queue2.pop());}returnqueue2.pop();}}publicinttop(){if(empty()){return-1;}inttmp0;if(!queue1.isEmpty()){intsizequeue1.size();for(inti0;isize;i){tmpqueue1.pop();queue2.push(tmp);}returntmp;}else{intsizequeue2.size();for(inti0;isize;i){tmpqueue2.pop();queue1.push(tmp);}returntmp;}}publicbooleanempty(){returnqueue1.isEmpty()queue2.isEmpty();}}更简洁的实现使用一个队列classMyStack{DequeIntegerqueuenewArrayDeque();publicvoidpush(intx){queue.push(x);intsizequeue.size();// 将前面的元素移到后面实现栈的顺序for(inti0;isize-1;i){queue.push(queue.pop());}}publicintpop(){returnqueue.pop();}publicinttop(){returnqueue.peek();}publicbooleanempty(){returnqueue.isEmpty();}}