阻塞队列有哪些（阻塞队列和普通队列）

队列（Queue）是一种常见的数据结构，它的设计灵感来自于生活中的排队场景。今天我们来认识一下队列的基本概念、常见操作、队列的分类，以及队列的经典应用和练习题。

队列是一种“先进先出”（FIFO, First In First Out）的线性数据结构，意味着最先进入队列的元素最先被处理。就像生活中的排队场景，先到的人会先离开队伍。队列的这种特性在许多应用场景中非常实用，尤其是在需要按顺序处理数据时。

1. 入队（Enqueue）：将元素添加到队列的末尾。

2. 出队（Dequeue）：从队列的头部移除元素。

3. 查看队首元素（Peek/Front）：查看队列头部的第一个元素。

4. 判断是否为空（IsEmpty）：检查队列是否为空。

队列通常可以用数组或链表实现：

1. 数组实现：

适合小规模的队列，但会出现“假溢出”现象（即数组未满却不能入队），需要循环队列来解决。

2. 链表实现：

适合动态调整大小的队列，链表结构可以避免假溢出，内存利用更高效。

- 入队（Enqueue）和出队（Dequeue）的时间复杂度均为O(1)。

- 查看队首元素（Peek/Front）的时间复杂度为O(1)。

1. 普通队列（Simple Queue）：

先进先出，最常用的一种队列。

2. 循环队列（Circular Queue）：

尾部连接头部，避免数组实现中的假溢出问题。

3. 双端队列（Deque, Double-ended Queue）：

可以从两端进行插入和删除操作。

4. 优先队列（Priority Queue）：

每个元素有优先级，按优先级顺序出队而非按进入顺序。

队列因其“先进先出”特性，在多个场景中非常适用：

1. 任务调度：

队列在操作系统中用于管理任务调度，让任务按照进入队列的顺序执行。

2. 消息队列：

用于在分布式系统中管理消息的传递，确保消息按顺序处理。

3. 广度优先搜索（BFS）：

在图或树的广度优先搜索中，使用队列来追踪节点遍历顺序。

1. 假溢出（Overflow）：

在数组实现的队列中，如果头尾指针没有循环使用，会出现队列空位仍无法入队的情况。

2. 出队操作的边界：

在队列为空时尝试出队，容易引发错误。

3. 双端队列的操作混淆：

在双端队列中，容易混淆从哪一端入队或出队。

1. 循环队列实现：

   - 问题描述：用数组实现循环队列，使头尾可以循环连接，避免假溢出问题。

   - 算法思路：定义两个指针`front`和`rear`，当`rear`指针达到数组末尾时，重新指向数组开头，形成循环结构。

   - 时间复杂度：入队和出队操作均为O(1)。

2. 用栈实现队列：

   - 问题描述：使用两个栈实现一个队列，完成队列的入队和出队操作。

   - 算法思路：使用一个栈负责入队，另一个栈负责出队。入队时，将元素直接压入第一个栈。出队时，将第一个栈的所有元素依次弹出并压入第二个栈，然后弹出第二个栈的栈顶元素。

   - 时间复杂度：每个操作的均摊时间复杂度为O(1)。

3. 滑动窗口最大值：

   - 问题描述：给定一个数组和一个滑动窗口的大小，找出每个窗口内的最大值。

   - 算法思路：用双端队列保存当前窗口内的最大值的下标。遍历数组，每次滑动窗口更新队列，移除队列中小于当前元素的下标。

   - 时间复杂度：O(n)

以下是几个关于队列的判断题，看看你对队列的理解如何：

1. 队列的特点是“先进后出”。（错误）

   - 队列的特点是“先进先出”。

2. 循环队列可以避免假溢出问题。（正确）

   - 循环队列将尾部与头部连接，避免了数组实现中的假溢出。

3. 优先队列是一种特殊的队列，其中元素按照优先级而非进入顺序出队。（正确）

   - 优先队列根据元素优先级出队。

4. 双端队列只能在一端进行入队和出队操作。（错误）

   - 双端队列可以在两端进行入队和出队操作。