当前位置：首页 > article >正文

栈实现队列，力扣

article 2024/9/27 9:21:51

题目地址：

232. 用栈实现队列 - 力扣（LeetCode）

难度：简单

今天刷栈实现队列，大家有兴趣可以点上看看题目要求，试着做一下。

题目：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

·void push(int x) 将元素 x 推到队列的末尾
·int pop() 从队列的开头移除并返回元素
·int peek() 返回队列开头的元素
·boolean empty() 如果队列为空，返回 true ；否则，返回 false

我们直接看题解吧：

审题目+事例+提示：

·代码实现只能在题目给出的方法进行操作

·这里的输出内容/返回值是调用栈的相关方法时的返回值

解题思路（双栈法）：

根据题意，队列的特性是 FIFO（先入先出），而栈的特性是 FILO（先入后出）。

知道两者特性之后，我们需要用两个栈来模拟队列的特性，一个栈为入队栈，一个栈为出对栈。

·当出队栈存在内容时，出队栈的栈顶，即为第一个出队的元素。

·若出队栈无元素，我们的需求又是出队的话，我们就需要将入队栈的内容逆序导入出队栈，然后弹出栈顶即可。

代码实现：

class MyQueue {
    Deque<Integer> inStack;   //创建Deque双端队列充当入队栈与出队栈
    Deque<Integer> outStack;  //注意，Deque是一个接口
    public MyQueue() {
        inStack = new LinkedList<Integer>();  //在构造方法中创建双向链表集合对象
        outStack = new LinkedList<Integer>(); //利用Deque接口其中的一个实现类
    }
    
    public void push(int x) {          //对入队栈进行压栈操作
        inStack.push(x);
    }
    
    public int pop() {              //对入队栈进行弹出栈操作
        if (outStack.isEmpty()) {  //判出队栈是否为空，空则调用in2out()方法
            in2out();
        }
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) {  //判出队栈是否为空，空则调用in2out()方法
            in2out();
        }
        return outStack.peek();
    }
    
    public boolean empty() {  //返回判断值（入队栈与出队栈是否均为空）
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void in2out() {
        while (!inStack.isEmpty()) {          //若入队栈不为空则进行循环
            outStack.push(inStack.pop());   //将入队栈内容导入出队栈
        }
    }
}
。

代码补充说明：

注意哈：

Java堆栈Stack类已经过时，Java官方推荐使用Deque替代Stack使用。

Deque是一个双端队列接口，继承自Queue接口。

· Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque，其中LinkedList是最常用的。

·Deque堆栈操作方法：push()、pop()、peek()等。

查看全文

http://www.kler.cn/news/155139.html