概述

队列(queue) 是一种 先进先出(FIFO) 的、操作受限的线性表

队列的 主要种类:

  1. [顺序队列](# 1、顺序队列)
  2. [链式队列](# 2、链式队列)
  3. [循环队列](# 3、循环队列)
  4. [优先队列](# 4、优先队列)
  5. [双端队列](# 5、双端队列)
  6. [单调队列](# 6、单调队列)

1、顺序队列

2、链式队列

3、循环队列

4、优先队列

优先队列 - 知乎 (zhihu.com)

5、双端队列

抛砖引玉 | 图解双端队列Deque - 知乎 (zhihu.com)

  • 双端队列又名double ended queue,简称deque,双端队列没有队列和栈这样的限制级,它允许两端进行入队和出队操作,也就是说元素可以从队头出队和入队,也可以从队尾出队和入队。

  • 1
    public interface Deque<E> extends Queue<E> {}
    • Deque是一个双端队列接口,继承自Queue接口,Deque的实现类是LinkedListArrayDequeLinkedBlockingDeque

      其中LinkedList是最常用的。

    Deque有三种用途

    • 普通队列(一端进另一端出):
      Queue queue = new LinkedList()Deque deque = new LinkedList()
    • 双端队列(两端都可进出)
      Deque deque = new LinkedList()
    • 堆栈
      Deque deque = new LinkedList()

    注意:Java堆栈Stack类已经过时,Java官方推荐使用Deque替代Stack使用。Deque堆栈操作方法:push()、pop()、peek()。

    此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式:一种形式在操作失败时抛出异常,另一种形式返回一个特殊值(null 或 false,具体取决于操作)。插入操作的后一种形式是专为使用有容量限制的 Deque 实现设计的;在大多数实现中,插入操作不能失败。

    第一个元素 (头部) 最后一个元素 (尾部)
    抛出异常 特殊值 抛出异常 特殊值
    插入 addFirst(e) offerFirst(e) addLast(e) offerLast(e)
    删除 removeFirst() pollFirst() removeLast() pollLast()
    检查 getFirst() peekFirst() getLast() peekLast()

    Deque 中有下面几种添加元素的方法:

    • add():可以使用 Deque的addFirst()方法在Deque的头部添加元素, 如果Deque不能添加元素,addFirst()方法会抛异常, offerFirst()方法则返回 false。
    • addLast()addLast()方法也可以在 Deque的尾部添加元素,这是Deque接口与从Queue接口继承的add()方法等效
    • addFirst() 可以使用 Deque的addFirst()方法在Deque的头部添加元素
    • offer() offer()方法可以在Deque的尾部添加元素,如果元素没满则添加成功返回true,否则返回false
    • offerFirst() offerFirst()方法是在 Deque 的头部添加元素,如果添加成功返回true,否则返回false
    • offerLast() offerLast()方法在Deque的尾部添加元素
    • push()push()方法是在Deque的头部添加元素,如果Deque中的元素满了,则会抛异常,

    可以查看Deque中的元素

    可以查看Deque中的第一个或者最后一个元素,查看元素意味着获取元素的引用而不是移除元素,有下面几种方法:

    • peek()peek()返回Deque中的第一个元素并且不删除,如果Deque是空则返回null

    • peekFirst() peekFirst()方法返回Deque的第一个元素,如果Deque是空则返回null,这和 peek()非常相似

    • peekLast()peekLast()方法返回最后一个元素,如果Deque是空则返回null

    • getFirst()getFirst()方法获取Deque的第一个元素并且不删除,如果Deque是空则抛异常

    • getLast() getLast()获取Deque的最后一个元素,如果Deque是空则返回null

    Deque接口扩展(继承)了 Queue 接口。在将双端队列用作队列时,将得到 FIFO(先进先出)行为。将元素添加到双端队列的末尾,从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法,

    Queue方法 等效Deque方法
    add(e) addLast(e)
    offer(e) offerLast(e)
    remove() removeFirst()
    poll() pollFirst()
    element() getFirst()
    peek() peekFirst()

    双端队列也可用作 LIFO(后进先出)堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时,元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法,如下表所示:

    堆栈方法 等效Deque方法
    push(e) addFirst(e)
    pop() removeFirst()
    peek() peekFirst()

    Deque的使用场景
    在一般情况,不涉及到并发的情况下,有两个实现类,可根据其自身的特性进行选择,分别是:

    • LinkedList 大小可变的链表双端队列,允许元素为插入null。
    • ArrayDeque 大下可变的数组双端队列,不允许插入null。
    • ConcurrentLinkedDeque 大小可变且线程安全的链表双端队列,非阻塞,不允许插入null。
    • LinkedBlockingDeque 为线程安全的双端队列,在队列为空的情况下,获取操作将会阻塞,直到有元素添加。

    注意:LinkedList 和 ArrayDeque 是线程不安全的容器。

6、单调队列

算法学习笔记(66): 单调队列 - 知乎 (zhihu.com)

单调队列 - OI Wiki (oi-wiki.org)

单调队列是一种主要用于解决滑动窗口类问题的数据结构,

  • 即,在长度为 n 的序列中,求每个长度为 m 的区间的区间最值。它的时间复杂度是 O(n) ,

  • 单调” 指的是元素的的 “规律”——递增(或递减)

  • 队列” 指的是元素只能从队头和队尾进行操作

1
2
3
4
5
6
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}

public interface Deque<E> extends Queue<E> {}
public interface Queue<E> extends Collection<E> {}

剑指 Offer 59 - I. 滑动窗口的最大值 - 力扣(LeetCode)