【LeetCode】225. 用队列实现栈(Queue接口 & Deque类)

??今日学习的文章链接和视频链接

leetcode题目地址：225. 用队列实现栈

?代码随想录题解地址：代码随想录

题目简介

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop?和?empty）。

实现?MyStack?类：

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

看到题目的第一想法(可以贴代码）

1.?Java Queue类

队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    public void push(int x) {
        if(q1.isEmpty()) q2.offer(x);
        else q1.offer(x);
    }
    
    public int pop() {
        if(q1.isEmpty()){
            dump();
            return q2.poll();
        } else{
            dump();
            return q1.poll();
        }
    }
    
    public int top() {
        if(q1.isEmpty()){
            dump();
            int res = q2.element();
            q1.offer(q2.poll());
            return res;
        } else{
            dump();
            int res = q1.element();
            q2.offer(q1.poll());
            return res;
        }
    }
    
    public boolean empty() return q1.isEmpty() && q2.isEmpty();
    
    public void dump(){
        if(q1.isEmpty()) while (q2.size() > 1) q1.offer(q2.poll());
        else while (q1.size() > 1) q2.offer(q1.poll());
    }
}

实现过程中遇到哪些困难

无

看完代码随想录之后的想法

【解题思路】Java Queue 的基础操作。

看完视频自己写的ACC：

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) q2.offer(q1.poll());
        Queue<Integer> temp = q2;
        q2 = q1;
        q1 = temp;
    }
    
    public int pop() {
        return q1.poll();
    }
    
    public int top() {
        return q1.element();
    }
    
    public boolean empty() {return q1.isEmpty();}
    
}

学习时长

略

---

今日收获

1.?Java Queue类

队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

【初始化】Queue<String> queue = new LinkedList<String>();

队列 Queue接口(LinkeList类) 常用方法?

//add()和remove()方法在失败的时候会抛出异常(不推荐)

　　add? ? ? ? ?增加一个元索? ? ? ? ? ? ? ? ? ? ? ? 如果队列已满，则抛出IIIegaISlabEepeplian异常
　　remove???移除并返回队列头部的元素??如果队列为空，则抛出NoSuchElementException异常
　　element??返回队列头部的元素?????????????如果队列为空，则抛出NoSuchElementException异常
　　offer???????添加一个元素并返回true? ? ? ? 如果队列已满，则返回false
　　poll?????????移除并返问队列头部的元素???如果队列为空，则返回null
　　peek???????返回队列头部的元素? ? ? ? ? ? ? 如果队列为空，则返回null
　　put?????????添加一个元素? ? ? ? ? ? ? ? ? ? ? ? ??如果队列满，则阻塞
　　take????????移除并返回队列头部的元素????如果队列为空，则阻塞
? ? ? ?drainTo(list)? ?一次性取出队列所有元素

1. queue.isEmpty(), 为空返回true，不为空返回false。
2. queue.size(), 为空返回0，不为空返回一个大于1的整数。

知识点： remove、element、offer?、poll、peek?其实是属于Queue接口。?

2. 【初始化】

Queue<String> q1 = new LinkedList<String>();

Queue<Integer> q1 = new ArrayDeque<>();

Deque<Integer> q1?= new ArrayDeque<>();

3.?双端队列 Deque类 常用方法

由于Deque继承了Queue接口，因此它继承了Queue接口的所有方法，Deque还包括以下方法：

• addFirst()?- 在双端队列的开头添加指定的元素。如果双端队列已满，则引发异常。

• addLast()?- 在双端队列的末尾添加指定的元素。如果双端队列已满，则引发异常。

• offerFirst()?- 在双端队列的开头添加指定的元素。如果双端队列已满，则返回false。

• offerLast()?- 在双端队列的末尾添加指定的元素。如果双端队列已满，则返回false。

• getFirst()?- 返回双端队列的第一个元素。如果双端队列为空，则引发异常。

• getLast()?- 返回双端队列的最后一个元素。如果双端队列为空，则引发异常。

• peekFirst()?- 返回双端队列的第一个元素。如果双端队列为空，则返回null。

• peekLast()?- 返回双端队列的最后一个元素。如果双端队列为空，则返回null。

• removeFirst()?- 返回并删除双端队列的第一个元素。如果双端队列为空，则引发异常。

• removeLast()?- 返回并删除双端队列的最后一个元素。如果双端队列为空，则引发异常。

• pollFirst()?- 返回并删除双端队列的第一个元素。如果双端队列为空，则返回null。

• pollLast()?- 返回并删除双端队列的最后一个元素。如果双端队列为空，则返回null。