leetcode刷题记录（三十一）——225. 用队列实现栈

（一）问题描述

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/implement-stack-using-queues/description/请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

• 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

• 1 <= x <= 9
• 最多调用100 次 push、pop、top 和 empty
• 每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

（二）解决思路

       这道题没什么特殊的算法，主要是考察队列和栈的特征，以及在不同语言当中队列和栈这两个数据结构的使用。栈的特点是先入后出，队列的特点是先入先出。232.用栈实现队列当中是使用两个栈，一个用来存储出，一个用来存储进。但这道题的两个队列并不是一个存储出一个存储进（这一点想象一下栈和队列进出元素的过程就可以明白了），其中一个队列是用来存储备份的，在存入元素时，为了达到栈的先入后出效果，可以反着存入元素：将第一个队列queue1中的元素都加入到queue2中，再在queue1中加入新元素，最后再将queue2中的元素重新放进queue1，这样无论是弹出还是查看顶端元素，都可以实现先入后出。

        进一步，如果只用一个栈，那么将新加入的元素从末尾放进去之后，再将前面所有元素都弹出并放到末尾就可以了。

        我使用的时JAVA语言，再JAVA中Queue接口的实现是ArrayDeque和LinkedList，使用这两个哪个都可以。

class MyStack {
    
     Queue<Integer> queue1;
     Queue<Integer> queue2;

    public MyStack() {
        //Queue是个接口，不是一个类，不能用来创建实例对象
        queue1=new ArrayDeque<>();
        queue2=new ArrayDeque<>();
    }
    
    public void push(int x) {
        //不能用queue1.size和for循环的原因：size会变化
        while(queue1.size()>0){
            queue2.add(queue1.poll());
        }
        queue1.add(x);
        while(queue2.size()>0){
            queue1.add(queue2.poll());
        }
    }
    
    public int pop() {
        return queue1.poll();
        
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
   
}

（三）易错点

       在逐个操作队列中的元素时最好用while(queue.size()>0)，如果使用for循环，由于size的值会变化，循环会提前终止。

原文地址：https://blog.csdn.net/weixin_45994787/article/details/143832752

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！