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

2023-12-21 22:46:44

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

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

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

题目简介

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppop?和?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。

文章来源:https://blog.csdn.net/Leonardo_t/article/details/135140337
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。