浅析 Queue 和 Deque

迈不过友情╰ 2023-09-26 20:37 17阅读 0赞

终于开始了 LeetCode 的练习，看到 [102. 二叉树的层序遍历][102.] 有种解法利用到了队列，想着挨个看看基础队列中的方法，便有了这篇文章。

> 基于 Java 对 Queue 以及 Deque（double ended queue） 实现进行学习介绍，JDK 版本：1.8.0\_361。  
> ![在这里插入图片描述][c0366c8be633400580cca95806a6d8ea.png]

## 全局概览 ##

![在这里插入图片描述][f1c6709a7c8d469c8f24021e36269308.png]  
先看下 Queue 的注释：

1.  A collection designed for holding elements prior to processing. Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations：一个为了处理之前保存元素而设计的集合。除了 Collection 提供的基础操作外，还提供了额外的插入、提取、检查的操作。
2.  Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements’ natural ordering, and LIFO queues (or stacks) which order the elements LIFO (last-in-first-out). ：Queue（队列）一般以 FIFO（先进先出）的方式对元素进行排序（但是不一定按照：优先队列「根据提供的 comparator 或者元素自然排序」以及 LIFO（后入先出） 队列）。

再看下 Deque 的注释：  
A linear collection that supports element insertion and removal at both ends：一个支持两端都支持元素插入删除的线性集合。

扩展下，当需要 LIFO 队列时不推荐使用 Stack，Stack 基于 Vector 实现，原因有以下两个：

1.  Vector 中的方法都有 synchronize 修饰，有性能问题（个人感觉不是重点，并发问题可以考虑：ConcurrentLinkedDeque）
2.  Vector 底层是数组，Stack 基于其实现，可以使用共有方法，**对 LIFO 的特征造成破坏**（感觉这个是重点）

## 基本方法 ##

### Queue ###

插入队尾：

1.  `boolean add(E e)`：插入成功返回 true，***失败抛异常***
2.  `boolean offer(E e)`：插入成功返回 true，失败返回 false

查询队首元素：

1.  `E element()`：队列为空，***抛异常***
2.  `E peek()`：队列为空，返回 null

删除队首元素：

1.  `E remove()`：队列为空，***抛异常***
2.  `E poll()`：队列为空，返回 null

### Deque ###

插入队首

1.  `void addFirst(E e)`：入队失败报异常
2.  `boolean offerFirst(E e)`：入队失败返回 false

插入队尾

1.  `void addLast(E e)`：入队失败报异常
2.  `boolean offerLast(E e)`：入队失败返回 false

删除队首

1.  `E removeFirst()`：队列为空抛异常
2.  `E pollFirst()`：队列为空返回 null

删除队尾

1.  `E removeLast()`:队列为空抛异常
2.  `E pollLast()`：队列为空返回 null

查询队首元素

1.  `E getFirst()`：队列为空抛异常
2.  `E peekFirst()`：队列为空返回 null

查询队尾元素

1.  `E getLast()`：队列为空抛异常
2.  `E peekLast()`：队列为空返回 null

## 推荐阅读 ##

下述各种队列具体实现原理博客等空了分专题学习整理分享，敬请期待。

> 涉及到了堆、锁、`Delayed` 接口。

[深入理解Java PriorityQueue][Java PriorityQueue]（和堆有关）

[Java 阻塞队列][Java]（和锁有关）

[Java 阻塞延迟队列 DelayQueue 原理及使用][Java _ DelayQueue]（和 `Delayed` 接口也有关）

[102.]: https://leetcode.cn/problems/binary-tree-level-order-traversa
[c0366c8be633400580cca95806a6d8ea.png]: https://img-blog.csdnimg.cn/c0366c8be633400580cca95806a6d8ea.png
[f1c6709a7c8d469c8f24021e36269308.png]: https://img-blog.csdnimg.cn/f1c6709a7c8d469c8f24021e36269308.png
[Java PriorityQueue]: https://www.cnblogs.com/CarpenterLee/p/5488070.html
[Java]: https://juejin.cn/post/6844903640709201934
[Java _ DelayQueue]: https://blog.csdn.net/fuzhongmin05/article/details/105716205