网站公告

本次更新：没啥更新的

“钱塘江上潮信起，今日方知我是我”

朕知道了
Noctiflorous Garden

外观

Queue ​

字数: 0 字 时长: 0 分钟

1. Queue ​

Queue 表示：

text
队列

普通队列通常遵循：

text
FIFO
First In First Out
先进先出

也就是：

text
队尾添加元素
    ↓
队首取出元素

例如：

text
入队
A → B → C

出队
A → B → C
↑
先取 A

常用方法：

操作抛异常版本返回特殊值版本
添加元素add()offer()
删除队首remove()poll()
查看队首element()peek()

其中日常使用通常更常见：

text
offer()
poll()
peek()

因为队列为空或添加失败时，可以通过：

text
false

null

表示，而不是直接抛出异常。

这里主要看三个常见实现：

text
Queue
├── ArrayDeque
├── LinkedList
└── PriorityQueue

1.1 ArrayDeque ​

ArrayDeque 是一个基于可扩容数组实现的双端队列。

text
Array
+
Deque
    ↓
ArrayDeque

Deque 全称：

text
Double Ended Queue
双端队列

意味着：

队首和队尾都可以添加、删除元素。

1.1.1 底层结构 ​

ArrayDeque 底层使用循环数组。

可以简单理解：

text
        ┌────────────────────┐
        ↓                    │
[ ][A][B][C][ ][ ][ ][ ]────┘
   ↑       ↑
 head     tail

其中：

text
head
    ↓
指向队首元素


tail
    ↓
指向下一次可以插入元素的位置

由于底层采用：

text
循环数组

所以：

text
head 不一定等于 0

tail 也不一定始终位于 head 后面

原来的结构图：

image-20250304174510582

1.1.2 基本使用 ​

java
Deque<String> deque =
        new ArrayDeque<>();

// 队尾添加
deque.offerLast(
        "周芷若"
);

deque.offerLast(
        "张无忌"
);

deque.offerLast(
        "赵敏"
);

// 查看队首
String first =
        deque.peekFirst();

// 队首删除
deque.pollFirst();

// 判断元素是否存在
boolean exists =
        deque.contains(
                "张无忌"
        );

System.out.println(
        exists
);

如果只是把它当普通队列：

java
Queue<String> queue =
        new ArrayDeque<>();

queue.offer(
        "周芷若"
);

queue.offer(
        "张无忌"
);

queue.offer(
        "赵敏"
);

System.out.println(
        queue.poll()
);

输出：

text
周芷若

符合：

text
FIFO
先进先出

1.1.3 双端操作 ​

因为它实现了：

java
Deque

所以可以操作两端：

java
deque.addFirst(
        "A"
);

deque.addLast(
        "B"
);

deque.pollFirst();

deque.pollLast();

deque.peekFirst();

deque.peekLast();

可以理解：

text
        队首                 队尾
         ↓                    ↓
        A ⇄ B ⇄ C ⇄ D
         ↑                    ↑
    First 操作            Last 操作

1.1.4 ArrayDeque 的特点 ​

主要特点：

text
底层基于循环数组

支持队首、队尾操作

容量不足时自动扩容

不支持通过下标随机访问

不允许存放 null

需要特别注意：

ArrayDeque 虽然底层是数组，但它没有提供 get(index) 这样的随机访问 API。

所以不能写：

java
// 不存在
// deque.get(0);

ArrayDeque 很适合实现：

text
普通队列

双端队列

栈

例如实现栈：

java
Deque<String> stack =
        new ArrayDeque<>();

stack.push("A");
stack.push("B");
stack.push("C");

System.out.println(
        stack.pop()
);

输出：

text
C

所以现代 Java 中：

text
实现队列
    ↓
ArrayDeque


实现栈
    ↓
ArrayDeque

都非常常见。

1.2 LinkedList ​

LinkedList 前面在 List 中已经讲过。

它比较特殊，因为同时实现了：

java
List

Deque

接口。

源码关系：

java
public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>,
                   Deque<E>,
                   Cloneable,
                   Serializable {
}

所以：

text
LinkedList
    ↓
既可以当 List
    ↓
也可以当 Queue / Deque

需要注意：

LinkedList 可以提供普通队列和栈式操作，但它并不等于 PriorityQueue，也不具备优先级队列的排序语义。

1.2.1 LinkedList 作为队列 ​

java
Queue<String> queue =
        new LinkedList<>();

// 入队
queue.offer(
        "周芷若"
);

queue.offer(
        "赵敏"
);

queue.offer(
        "张无忌"
);

System.out.println(
        queue
);

结果：

text
[周芷若, 赵敏, 张无忌]

删除队首：

java
String first =
        queue.poll();

System.out.println(
        first
);

输出：

text
周芷若

查看队首但不删除：

java
String first =
        queue.peek();

整个过程：

text
offer()
    ↓
队尾添加


poll()
    ↓
队首取出并删除


peek()
    ↓
只查看队首

1.2.2 LinkedList 作为双端队列 ​

如果声明成：

java
Deque<String> deque =
        new LinkedList<>();

同样可以：

java
deque.addFirst(
        "A"
);

deque.addLast(
        "B"
);

deque.pollFirst();

deque.pollLast();

因此：

text
LinkedList
    ↓
双向链表
    ↓
天然适合两端插入和删除

1.2.3 LinkedList 和 ArrayDeque ​

两者都实现：

java
Deque

但是底层结构不同：

text
LinkedList
    ↓
双向链表


ArrayDeque
    ↓
循环数组

简单比较：

对比ArrayDequeLinkedList
底层结构循环数组双向链表
两端插入删除快快
是否支持 null不支持支持
额外节点引用无有
内存占用通常更低通常更高
作为普通队列推荐可以

普通的：

text
队列

双端队列

栈

场景中，一般优先考虑：

java
ArrayDeque

而不是因为：

text
LinkedList 是链表

就默认认为它一定更快。

1.3 PriorityQueue ​

PriorityQueue 是：

优先级队列。

普通队列：

text
先进先出
FIFO

而优先级队列：

text
谁优先级更高
    ↓
谁先出队

它底层通常可以理解为：

text
数组
+
二叉堆

Java 的 PriorityQueue 使用：

text
堆结构

维护队首元素。

默认情况下：

按照元素的自然顺序，较小的元素具有更高优先级。

例如：

java
Queue<Integer> queue =
        new PriorityQueue<>();

queue.offer(30);
queue.offer(10);
queue.offer(20);

System.out.println(
        queue.poll()
);

System.out.println(
        queue.poll()
);

System.out.println(
        queue.poll()
);

输出：

text
10
20
30

虽然插入顺序：

text
30
10
20

但出队顺序：

text
10
20
30

1.3.1 基本使用 ​

java
PriorityQueue<String> queue =
        new PriorityQueue<>();

queue.offer(
        "张无忌"
);

queue.offer(
        "赵敏"
);

queue.offer(
        "周芷若"
);

// 查看优先级最高的队首元素
String first =
        queue.peek();

// 取出并删除队首元素
String value =
        queue.poll();

// 判断是否存在
boolean exists =
        queue.contains(
                "赵敏"
);

需要注意：

不要根据 PriorityQueue 直接打印或 foreach 遍历的结果判断整体排序。

例如：

java
System.out.println(
        queue
);

得到的内部顺序：

text
不保证是完整排序后的顺序

PriorityQueue 只保证：

text
peek()

poll()

每次访问到当前：

text
优先级最高的队首元素

如果需要按优先级顺序全部取出：

java
while (
        !queue.isEmpty()
) {

    System.out.println(
            queue.poll()
    );
}

1.3.2 PriorityQueue 的排序规则 ​

元素的优先级可以来自：

text
Comparable

或者：

text
Comparator

如果元素本身实现：

java
Comparable

可以按照自然顺序排列。

如果希望自己定义优先级，则传入：

java
Comparator

例如学生：

java
class Student {

    private final String name;

    private final int chineseScore;

    private final int mathScore;

    public Student(
            String name,
            int chineseScore,
            int mathScore) {

        this.name =
                name;

        this.chineseScore =
                chineseScore;

        this.mathScore =
                mathScore;
    }

    public String getName() {

        return name;
    }

    public int getTotalScore() {

        return chineseScore
                + mathScore;
    }

    @Override
    public String toString() {

        return name
                + "："
                + getTotalScore();
    }
}

按照：

text
总成绩从高到低

设置优先级：

java
Comparator<Student> comparator =
        Comparator.comparingInt(
                Student::getTotalScore
        ).reversed();

创建：

java
PriorityQueue<Student> queue =
        new PriorityQueue<>(
                comparator
        );

添加：

java
queue.offer(
        new Student(
                "周芷若",
                80,
                90
        )
);

queue.offer(
        new Student(
                "张无忌",
                95,
                95
        )
);

queue.offer(
        new Student(
                "赵敏",
                90,
                95
        )
);

queue.offer(
        new Student(
                "小昭",
                90,
                80
        )
);

按照优先级依次取出：

java
while (
        !queue.isEmpty()
) {

    System.out.println(
            queue.poll()
    );
}

结果：

text
张无忌：190
赵敏：185
周芷若：170
小昭：170

总成绩越高：

text
优先级越高
    ↓
越早被 poll()

需要注意：

当两个元素比较结果为 0 时，PriorityQueue 不保证它们按照插入顺序出队。

所以：

text
周芷若 170

小昭 170

两者谁先出来，不应该依赖上面的示例顺序。

1.3.3 PriorityQueue 的特点 ​

可以简单记：

text
PriorityQueue
    ↓
优先级队列
    ↓
底层使用堆
    ↓
队首始终保持高优先级元素

默认：

text
自然顺序

自定义：

text
Comparator

常见方法：

text
offer()
    ↓
加入元素


peek()
    ↓
查看当前优先级最高元素


poll()
    ↓
取出当前优先级最高元素

PriorityQueue 同样不允许：

java
null

元素。

2. 小结 ​

三个常见队列实现：

实现底层结构顺序规则主要特点
ArrayDeque循环数组队列顺序高效双端队列
LinkedList双向链表队列顺序同时实现 List、Deque
PriorityQueue堆优先级顺序优先级最高的元素先出队

可以简单记：

text
普通队列
    ↓
ArrayDeque


双端队列
    ↓
ArrayDeque


LinkedList
    ↓
既能作为 List
也能作为 Deque


优先级队列
    ↓
PriorityQueue

三者最核心的区别：

text
ArrayDeque
    ↓
循环数组
    ↓
适合普通队列 / 双端队列 / 栈


LinkedList
    ↓
双向链表
    ↓
同时具备 List 和 Deque 能力


PriorityQueue
    ↓
堆
    ↓
不按照普通 FIFO
    ↓
按照优先级出队

一句话概括：

普通 Queue 强调先进先出，Deque 强调两端都可以操作，而 PriorityQueue 强调“谁优先级高，谁先出队”。

Noctiflorous Garden · MIT License

© 2024 Kerwim · 冀ICP备2024088775号-1 · Built in silence. Running against entropy.