代码随想录算法训练营第九天| 232.用栈实现队列，225.用队列实现栈

232. 用栈实现队列

232.用栈实现队列

这里用两个栈来模拟队列以此实现队列的先进先出，

注意点

1.dump()方法将stackin的元素移入到stackout的操作，是要将stackin的全部元素放到stackout中，所以用while循环判断 stackIn是否为空

2.新建栈的方法

class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;public MyQueue() {stackIn=new Stack<>();stackOut=new Stack<>();}public void push(int x) {// 将元素 x 推到队列的末尾stackIn.push(x);}public int pop() {//从队列的开头移除并返回元素dump();return stackOut.pop();}public int peek() {//返回队列开头的元素dump();return stackOut.peek();}public boolean empty() {// 如果队列为空，返回 true ；否则，返回 falsereturn stackIn.isEmpty()&&stackOut.isEmpty();}public void dump(){//如果stackout为空，那么把stackin的元素放到stackout中if(!stackOut.isEmpty()){return;}while(!stackIn.isEmpty()){//注意这里是while,这里如果是while(stackOut.isEmpty())，那么push进去一个就结束了// System.out.println(stackIn.pop());这里先pop了，导致后面empty()方法输出错误stackOut.push(stackIn.pop());}}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

225. 用队列实现栈

225.用队列实现栈

队列实现栈（需要二刷）

解法1 使用两个队列实现栈

• offer() 是往队列中添加一个元素，若队列已满而仍往队列中添加，则会返回false
• poll() 是删除队列中的第一个元素，在对空队列进行操作时，返回null
• peek() 是输出队列的第一个元素，队列为空时，返回null

class MyStack {//使用两个队列实现站Queue<Integer> q1;Queue<Integer> q2;public MyStack() {q1=new LinkedList<>();q2=new LinkedList<>();}public void push(int x) {q2.offer(x);//先给q2添加一个元素while(!q1.isEmpty()){q2.offer(q1.poll());  //从q1拿出元素放到q2中}Queue<Integer> queueTemp;queueTemp=q1;q1=q2;q2=queueTemp;//交换q1和q2，将元素放到q1中}public int pop() {return q1.poll();}public int top() {return q1.peek();}public boolean empty() {return q1.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();*/

解法2 使用1个队列实现栈

思路是每次向队列添加一个元素后，对队列中的元素进行重新排序

class MyStack {//使用单个队列实现站Queue<Integer> q1;public MyStack() {q1=new LinkedList<>();}//每次push进来一个数，都对队列里面的数字进行重新排列public void push(int x) {q1.offer(x);//添加一个数字int size=q1.size();while(size-->1){q1.offer(q1.poll());}}public int pop() {return q1.poll();}public int top() {return q1.peek();}public boolean empty() {return q1.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();*/