LeetCode225.用队列实现栈java题解

leetcode /problems/implement-stack-using-queues/submissions/

class MyStack { LinkedList<Integer> queue1; // 和栈中保持一样元素的队列 LinkedList<Integer> queue2; // 辅助队列 public MyStack() { queue1=new LinkedList<>(); queue2=new LinkedList<>(); } /* 只能使用队列的标准操作：放到队尾、弹出队首、size、isEmpty */ /* 入栈：放入非空的队列中 */ public void push(int x) { if(!queue1.isEmpty()){ queue1.addLast(x);//放入队尾 } else{ queue2.addLast(x); } } /* 出栈，把非空队列放入另一个空队列 只留下一个在非空队列，然后弹出，成为了空队列 */ public int pop() { //queue1不为空 if(!queue1.isEmpty()){ while(queue1.size()>1){ queue2.addLast(queue1.removeFirst()); } return queue1.removeFirst();//弹出的是原queue1队尾 } else{ //if(!queue2.isEmpty()){ while(queue2.size()>1){ queue1.addLast(queue2.removeFirst()); } return queue2.removeFirst();//弹出的是原queue2队尾 } // else{//都为空 // return null; // } } //先弹出栈顶元素，再加入进去 public int top() { int res=pop(); push(res); return res; } public boolean empty() { return queue1.isEmpty()&&queue2.isEmpty(); } } /** * 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(); */

优化 其实这道题目就是用一个队列就够了。 一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。