【数据结构】队列（queue）-菜鸟笔记

1、队列的基本结构

队列（queue）是一种线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除，插入元素的一端称为队尾（rear），删除元素的一端称为队首（front）。从队列中删除元素称为离队或出队，元素出队后，其后续元素成为新的队首元素。队列的结构示意图，如下所示：

由于队列的插入和删除操作分别在队尾和队首进行，每个元素必然按照进入的次序离队，因此，队列也称为先进先出表（First In First Out，简称 FIFO）。

2、队列的分类

2.1 按线性表的存储结构

由于队列也是一种线性表，那么它就同样有线性表的两种存储形式：顺序队列 和 链式队列。

顺序队列，底层通常采用的是循环数组实现，存储元素的数量受限于数组的大小，在插入和删除元素时，需要使用对队首指针和队尾指针进行队列满和队列空的判断。

在实现顺序队列中，可以将队列当作一般的表用数组实现，而这样的效果并不好。尽管可以用一个指针 last 来指示队尾，使得插入运算可在 Ο(1) 时间内完成，但在执行删除运算时却存在不足，为了删除队首的元素，必须将数组中其他所有元素都向前移动一个位置。这样的话，当队列中有 n 个元素时，执行删除运算就需要 Ο(n) 时间。

为了提高运算的效率，在 Java 中 ArrayQueue 用另一种方法来表达数组中各单元的位置关系，即数组 Arr[0 ... capacity-1] 中的单元不是排成一行，而是围成一个圆环，这样在插入和删除时都可以在 Ο(1) 时间内完成，如图所示：

而链式队列，底层采用的是链表实现，存储元素的数量不受限制，在插入和删除元素时也很简单，插入元素时直接在链表的尾部加入，取出元素时直接从链表的头部取出即可，如图所示：

2.2 按方向性

以 Java 语言为例，Java 定义了队列的接口类型为 java.util.Queue，这种 Queue 是单向的，即只能从尾部插入元素，从头部删除元素。而 Java 同样也定义了双向队列 Deque，可以同时在头部和尾部插入和取出元素，接口类型为 java.util.Deque。

java.util.Queue 定义了两套队列的操作方法，区别如下：

add()、remove()、element() 操作失败会抛出异常；
offer() 操作失败会返回 false 或抛出异常，poll()、peek() 操作失败会返回 null。

java.util.Deque 也同样定义了两套队列操作方法，头部操作方法为 xxxFirst、尾部操作方法为 xxxLast，区别如下：

add、remove、get 操作失败会抛出异常；
offer 操作失败会返回 false 或抛出异常，poll、peek 操作失败会返回 null；
removeFirstOccurrence、removeLastOccurrence 方法用于删除指定元素，元素存在则删除，不存在则队列不变。

2.3 按阻塞性

阻塞队列：在操作队列元素时，可能会一直阻塞直到相关操作的完成。例如，从空队列中取出元素、向满队列中插入元素等，主要有延时队列、同步队列、优先级阻塞队列、链表阻塞队列、数组阻塞队列等。而非阻塞队列，在操作队列元素时会立即执行操作。

Java 在并发工具包（java.util.concurrent）中定义了阻塞队列 BlockingQueue 和 BlockingDueue，它们在前面的队列定义基础上增加了以下几个方法，用以支持阻塞操作：

take：取出并移除元素，如队列为空则一直阻塞直到有元素；
put：插入元素，如队列满则一直阻塞直到有空位可以插入元素；
可超时的offer：插入元素并指定超时时间，如队列满等待指定的时间；
可超时的poll：取出并移除元素，如队列空等待指定的时间。

BlockingQueue 接口存在不同用途的阻塞队列的实现，具体的实现类有：

//无界优先级阻塞队列
BlockingQueue priorityBlockingQueue = new PriorityBlockingQueue();
//基于数组实现的有界的阻塞队列
BlockingQueue arrayBlockingQueue = new ArrayBlockingQueue(1000);
//基于链表实现的有界的阻塞队列
BlockingQueue linkedBlockingQueue = new LinkedBlockingQueue();
//同步队列
BlockingQueue synchronousQueue = new SynchronousQueue();
//无界延时队列
BlockingQueue delayQueue = new DelayQueue();
//用于生产者等待消费者消费元素的链表有界的阻塞队列
BlockingQueue linkedTransferQueue = new LinkedTransferQueue();

同样，BlockingDueue 是双端阻塞队列，实现类为 LinkedBlockingDeque：

//基于链表实现的有界的阻塞双向队列
BlockingDeque linkedBlockingDeque = new LinkedBlockingDeque();

因为存在不同用途的需求，才有这么多的阻塞队列类型，实际应用中按需使用即可：

PriorityBlockingQueue：无界优先级阻塞队列。当队列空或满时才会阻塞相关操作。
ArrayBlockingQueue：基于数组实现的有界阻塞队列。创建队列时需要指定队列长度，且队列大小一旦指定则不会再发生变化。
LinkedBlockingQueue：基于链表实现的有界阻塞队列。创建队列时可以不指定队列长度，如果队列大小一旦指定则不会再发生变化。如果未指定队列大小，默认为Integer.MAX_VALUE。
SynchronousQueue：同步队列。与其他的阻塞队列有所不同，在插入元素时会一直阻塞，直到有另一个线程取元素；在取出元素，同样会一直阻塞直到有另一个线程插入元素。同步队列本身没有容量的概念，不会存储元素，可理解为是线程间的数据交换，因此同步队列也不能执行 size、peek 类型的操作。
DelayQueue：无界的延时队列。该队列的元素只有在延时时间已经过期的情况下才能被访问，也就是说，没有元素过期则没有头部元素，取元素的方法会返回 null，当元素过期时，调用元素的 getDelay 方法会返回 0 或负数。另外，未过期的元素不能被取出，但是统计队列大小时仍然包含未过期元素。
LinkedTransferQueue：阻塞队列经常存在生产者等待消费者消费元素的情况，BlockingQueue 的子接口 TransferQueue 定义了一种新队列来支持这种情况，实现类为 LinkedTransferQueue。TransferQueue 允许生产者调用 transfer 方法来等待消费者调用 take 或 poll 消费元素，如果有消费者正在取元素则直接交给消费者，否则便把元素插入队列尾部并阻塞生产者当前线程直到元素被消费者取走。
LinkedBlockingDeque：基于链表实现的有界的阻塞双向队列。与LinkedBlockingQueue一样，如果未指定队列大小，默认为Integer.MAX_VALUE。

另外，Java 中的非阻塞队列有：PriorityQueue、ArrayQueue、ConcurrentLinkedQueue、LinkedList、ArrayDeque、ConcurrentLinkedDeque 等，区别如下：

PriorityQueue：基于一个优先级堆实现的无界优先级队列。该队列中的元素按自然顺序或者创建时提供的 Comparator 比较先后顺序进行排列的，因此元素不能为null，不支持多线程操作。
ConcurrentLinkedQueue：基于链表实现的线程安全的无界队列。该队列中的元素不能为null，但支持多线程操作。
LinkedList：该链表也实现了 Deque 接口，为了提高操作性能，从链表两端插入和取出元素，不支持多线程操作。
ArrayDeque：基于数组实现的双向队列，支持数组扩容操作，但不支持多线程操作。
ConcurrentLinkedDeque：基于链表实现的线程安全的无界双向队列。该队列中的元素不能为null，但支持多线程操作。

2.4 按并发性

如果考虑程序的并发安全性，则可以把队列分为线程安全的队列，和非线程安全的队列。

在上面的阻塞队列已经涉及到了，线程安全的队列可以保证并发操作是安全的，通常在 Java 并发工具包（java.util.concurrent）中定义，比如 ConcurrentLinkedQueue、ConcurrentLinkedDeque 以及 BlockingQueue 和 BlockingDueue 对应的实现类。

以上的这些类型的队列源码，有时间可以深入阅读和研究下，对自己的算法思维提升是有帮助的！

3、队列_算法刷题

力扣官网提供了有关队列的算法题目，实现不限于某一种语言，如下：

感兴趣的话，可以一起刷起来~

【数据结构】队列（queue）