[LeetCode]225. 用队列实现栈(java实现)

1. 题目

在这里插入图片描述

2. 读题(需要重点注意的东西)

队列的特性—先进先出
思路:由于队列的先进先出特性,因此与用栈实现队列的思路不同,用队列来实现栈需要思考如何能将先入先出,转化为先入后出。

3. 解法

class MyStack {
    private Queue<Integer> queueIn;//输入队列
    private Queue<Integer> queueOut;//输出队列
    
    public MyStack() {
        queueIn = new LinkedList<>();
        queueOut = new LinkedList<>();
    }
    
    public void push(int x) {
        queueIn.offer(x);
        //接下来四句代码实现了由先入先出转换为先入后出,详见后文总结
        while(!queueOut.isEmpty()){queueIn.offer(queueOut.poll());}
        Queue temp = queueIn;
        queueIn = queueOut;
        queueOut = temp;
    }
    
    public int pop() {
        return queueOut.poll();
    }
   
    public int top() {
        return queueOut.peek();
    }
    
    public boolean empty() {
        return queueOut.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();
 */

4. 可能有帮助的前置习题

[LeetCode]232. 用栈实现队列(java实现)

5. 所用到的数据结构与算法思想

6. 总结

public void push(int x) {
    queueIn.offer(x);
    //接下来四句代码实现了由先入先出转换为先入后出,详见后文总结
    while(!queueOut.isEmpty()){queueIn.offer(queueOut.poll());}
    Queue temp = queueIn;
    queueIn = queueOut;
    queueOut = temp;
}

对上文代码的理解: 输入 1 、2两个元素;

  1. 当输入x = 1时:(详细的队列信息见注释)
// 输入前queueIn = [ ] ,queueOut = [ ]
queueIn.offer(x); //queueIn = [ 1 ]
 while(!queueOut.isEmpty()){queueIn.offer(queueOut.poll());} // queueIn = [ 1 ],queueOut = [ ]
Queue temp = queueIn; // queueIn = [ 1 ],queueOut = [ ],temp = [ 1 ]
queueIn = queueOut; // queueIn = [  ],queueOut = [  ],temp = [ 1 ]
queueOut = temp;// queueIn = [  ],queueOut = [ 1 ],temp = [ 1 ]
  1. 当输入x = 2时:(详细的队列信息见注释)
// 输入前queueIn = [ ] ,queueOut = [ 1 ]
queueIn.offer(x); //queueIn = [ 2 ]
 while(!queueOut.isEmpty()){queueIn.offer(queueOut.poll());} // queueIn = [ 2, 1 ],queueOut = [  ] (queueOut已经poll出元素了,所以当执行完当前操作时,queueOut为空)
Queue temp = queueIn; // queueIn = [ 2, 1 ],queueOut = [  ],temp = [ 2, 1 ]
queueIn = queueOut; // queueIn = [  ],queueOut = [  ],temp = [ 2, 1 ]
queueOut = temp;// queueIn = [  ],queueOut = [ 2, 1 ],temp = [ 2, 1 ]

因此,在执行完上述五行代码后,能够实现由先入先出,变为先入后出;并且在每次输入元素时,queueIn都为空。


版权声明:本文为weixin_43972154原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。