队列 | 自在学队列
队列（Queue）是计算机科学中一种基础的线性数据结构，它遵循先进先出（First-In, First-Out，简称FIFO） 的原则。与栈（Stack）的后进先出（LIFO）特性形成对比，队列确保了数据元素按照它们进入的顺序被处理，这种特性使得队列在任务调度、数据流处理和算法实现中发挥着不可替代的作用。
在抽象数据类型（ADT）的层次上，队列定义了一组操作，这些操作共同维护了一个有序的元素集合，其中元素的访问顺序严格遵循FIFO原则。这种数据结构在系统编程、网络通信、算法设计等多个领域都有广泛应用。操作系统使用队列管理进程调度和I/O请求，网络服务器通过队列处理并发请求，编译器利用队列进行语法分析和代码生成。队列的FIFO特性保证了处理的公平性和顺序性，这对于需要按时间顺序处理事件的系统至关重要。
队列的抽象定义与基本操作
从抽象数据类型的角度来看，队列是一个有序的元素序列，它支持两种基本的修改操作：入队（Enqueue）和出队（Dequeue）。队列有两个逻辑端点：队头（Front/Head）和队尾（Rear/Back）。新元素总是从队尾加入，而元素的移除总是发生在队头。这种设计确保了最早进入队列的元素会最先被处理。
除了核心的修改操作，队列还提供了一些查询操作来检查其状态。front()操作允许我们访问队头元素而不移除它，这对于需要查看下一个将被处理的元素而不实际处理它的情况很有用。isEmpty()操作检查队列是否为空，这对于循环处理队列中的元素直到队列为空的情况是必要的。size()操作返回队列中当前元素的数量，这在需要监控队列状态或进行性能分析时很有价值。
这个操作序列清晰地展示了FIFO原则：元素A最先进入队列，因此也最先被移除。队列中元素的相对顺序在整个操作过程中保持不变，这正是队列区别于其他数据结构（如栈）的核心特征。
从算法复杂度的角度来看，一个设计良好的队列实现应该保证enqueue和dequeue操作的时间复杂度为O(1)，即常数时间复杂度。这意味着无论队列中有多少元素，这两个核心操作的执行时间都是固定的。front()、isEmpty()和size()操作同样应该在O(1)时间内完成。这种高效的性能特征使得队列能够胜任高频率的数据处理场景。
队列的实现方式
队列的抽象定义可以通过多种底层数据结构来实现，每种实现方式都有其特定的优势和适用场景。最常用的两种实现方式是基于链表的队列和基于循环数组的队列。选择哪种实现方式取决于具体的应用需求，包括对内存使用的限制、对性能的要求、以及对动态大小的需求等因素。
基于链表的队列实现
链表实现队列的核心思想是利用动态内存分配来存储队列元素。每个元素被封装在一个节点中，节点之间通过指针连接形成链式结构。这种实现方式的优势在于它不需要预先分配固定大小的内存空间，队列可以根据需要动态增长，只要系统内存允许。
在链表实现的队列中，我们需要维护两个关键指针：head指针指向链表的第一个节点（队头），tail指针指向链表的最后一个节点（队尾）。这种设计使得我们可以在O(1)时间内完成入队和出队操作。
- **入队操作（Enqueue）**的算法流程如下：首先为新元素分配内存并创建节点，如果队列为空，则将
head和tail都指向新节点；否则，将当前tail节点的next指针指向新节点，然后更新tail指针指向新节点。这个操作只涉及指针的赋值，时间复杂度为O(1)。
- **出队操作（Dequeue）**的流程相对复杂一些：首先检查队列是否为空，如果为空则抛出异常；否则，保存
head节点中的数据，将head指针移动到下一个节点，释放原head节点的内存。如果出队后队列变为空，需要将tail指针也设置为nullptr以避免悬空指针。这个操作同样只需要常数时间。
链表实现的空间复杂度为O(n)，其中n是队列中元素的数量。每个节点除了存储数据本身，还需要存储一个指针，这带来了额外的内存开销。然而，这种开销换来了动态大小的灵活性，使得链表实现特别适合元素数量变化较大的场景。
#include <iostream>
#include <stdexcept>
// 链表节点结构定义
template <typename T>
struct Node {
T data; // 节点存储的数据
Node* next; // 指向下一个节点的指针
Node(T val) : data(val), next(nullptr) {}
};
// 基于链表的队列实现
template <typename T>
链表实现的优势在于其动态性和灵活性。它不需要预先知道队列的最大容量，可以随着元素的添加和移除动态调整大小。然而，这种灵活性也带来了内存管理的复杂性，需要仔细处理节点的分配和释放，以避免内存泄漏。此外，链表节点在内存中的分布可能不连续，这可能导致缓存性能不如数组实现。
基于循环数组的队列实现
使用数组实现队列时，我们面临一个关键问题：如果简单地使用线性数组，随着元素的出队，数组前部会留下空位，但新元素只能添加到数组末尾。当rear索引到达数组末尾时，即使数组前部有空位，我们也无法继续添加元素。这种现象被称为假溢出（False Overflow），因为数组实际上还有可用空间，但由于实现方式的限制而无法使用。
循环队列（Circular Queue） 通过将数组视为一个环形结构来解决这个问题。当rear索引到达数组末尾时，下一个位置会"绕回"到数组开头，只要那个位置是空的。这种循环特性通过模运算（Modulo Operation） 来实现，具体来说，我们使用(index + 1) % capacity来计算下一个索引位置。
循环队列的实现需要维护两个索引：front_idx指向队头元素的位置，rear_idx指向队尾元素的下一个位置（即下一个元素应该插入的位置）。这种设计使得我们可以通过比较front_idx和rear_idx来判断队列的状态。
判断队列为空的充要条件是front_idx == rear_idx。判断队列为满的条件是(rear_idx + 1) % capacity == front_idx。注意这里我们通常让数组的实际容量比用户指定的容量大1，这个额外的空间用于区分空队列和满队列的状态。如果不使用这个技巧，空队列和满队列的判断条件会相同，导致无法区分这两种状态。
入队操作的算法：首先检查队列是否已满，如果已满则抛出溢出异常；否则，在rear_idx位置存储新元素，然后更新rear_idx = (rear_idx + 1) % capacity。出队操作的算法：首先检查队列是否为空，如果为空则抛出异常；否则，保存front_idx位置的元素，然后更新front_idx = (front_idx + 1) % capacity。
循环队列的空间复杂度为O(n)，其中n是队列的容量。与链表实现不同，这个空间是预先分配的，因此即使队列中元素很少，占用的内存也是固定的。然而，数组在内存中的连续存储特性使得循环队列具有更好的缓存局部性，这在某些场景下可以带来显著的性能提升。
#include <vector>
#include <stdexcept>
// 基于循环数组的队列实现
template <typename T>
class CircularQueue {
public:
// 构造函数：初始化指定容量的循环队列
CircularQueue(size_t cap) : capacity(cap + 1), front_idx(0), rear_idx(0) {
// 容量加1是为了区分空队列和满队列的状态
// 空队列：front_idx == rear_idx
// 满队列：(rear_idx + 1) % capacity == front_idx
elements.
循环队列的实现相比链表实现更加紧凑，内存使用效率更高，因为不需要为每个元素存储额外的指针。然而，循环队列的容量是固定的，一旦创建就无法动态调整。如果需要在运行时动态改变队列容量，就需要重新分配更大的数组并复制现有元素，这个操作的时间复杂度为O(n)。
无论是链表实现还是循环数组实现，这两种方式都保证了队列核心操作（入队和出队）的时间复杂度为O(1)。选择哪种实现方式取决于具体的应用场景：需要动态大小和灵活内存使用时选择链表实现；需要更好的缓存性能和固定容量时选择循环数组实现。
队列的应用场景与算法
队列的FIFO特性使其成为许多算法和系统设计中的核心组件。从操作系统内核到高级算法，队列的应用贯穿整个计算机科学领域。
任务调度与资源管理
在操作系统中，队列是任务调度的基础数据结构。当多个进程或线程竞争有限的系统资源（如CPU时间片、I/O设备、打印机等）时，操作系统使用队列来维护等待资源的任务列表。这种调度策略确保了公平性：先提交的任务会先获得资源，避免了某些任务长时间等待的情况。
在多线程编程中，队列常用于实现生产者-消费者模式。生产者线程将任务放入队列，消费者线程从队列中取出任务并执行。队列作为两者之间的缓冲区，解耦了生产者和消费者的执行速度，使得系统能够更灵活地处理不同速度的生产和消费过程。这种模式在消息队列系统、事件驱动架构和异步任务处理中都有广泛应用。
广度优先搜索算法
在图论和树结构中，广度优先搜索（Breadth-First Search，BFS） 是一种重要的遍历算法，而队列是实现BFS的核心数据结构。BFS算法从起始节点开始，逐层探索图中的节点，确保在探索距离起始节点更远的节点之前，先探索完所有距离较近的节点。
BFS算法的正确性依赖于队列的FIFO特性。算法的基本流程是：将起始节点入队并标记为已访问；只要队列不为空，就从队头取出一个节点进行探索，将该节点的所有未访问邻居节点入队并标记为已访问；重复此过程直到队列为空。队列保证了节点按照距离起始节点的距离（即层数）被处理，这使得BFS能够找到从起始节点到目标节点的最短路径（在无权图中）。
BFS算法的时间复杂度为O(V+E)，其中V是顶点数，E是边数。空间复杂度为O(V)，主要用于存储访问标记和队列。队列在BFS中的最大长度不会超过图中任意一层节点的最大数量，在最坏情况下（如完全图），队列可能包含所有节点。
缓冲区与数据流处理
在数据流处理系统中，队列作为缓冲区（Buffer）连接数据生产者和消费者。典型的例子包括网络视频流播放、音频处理、数据采集系统等。在这些场景中，生产者的数据产生速度可能与消费者的处理速度不匹配，队列起到了平滑这种差异的作用。
当生产者速度大于消费者速度时，队列会积累数据，为消费者提供缓冲；当生产者速度小于消费者速度时，队列中的数据会被逐渐消耗。这种设计使得系统能够应对短期的速度波动，提供更稳定的性能表现。队列的大小需要根据具体的应用场景进行权衡：队列太小可能导致数据丢失或处理中断，队列太大则会占用过多内存并增加延迟。
在网络编程中，队列还用于实现滑动窗口协议、流量控制和拥塞控制等机制。这些机制都依赖于队列来管理待发送或待确认的数据包，确保网络通信的可靠性和效率。
队列的变体与扩展
除了基本的FIFO队列，还存在一些重要的队列变体，它们扩展了队列的功能以适应不同的应用需求。
- 双端队列（Deque，Double-Ended Queue） 允许在队列的两端进行插入和删除操作。这种数据结构结合了队列和栈的特性，可以在队头和队尾都进行高效的添加和移除操作。双端队列在实现某些算法（如滑动窗口最大值问题）时非常有用。
- 优先队列（Priority Queue） 不遵循严格的FIFO原则，而是根据元素的优先级来决定处理顺序。高优先级的元素会先于低优先级的元素被处理，即使它们后进入队列。优先队列通常使用堆（Heap）数据结构实现，插入和删除操作的时间复杂度为O(logn)。优先队列在任务调度、事件模拟、图算法（如Dijkstra最短路径算法）中都有重要应用。
- 阻塞队列（Blocking Queue） 是一种线程安全的队列实现，当队列为空时，试图出队的线程会被阻塞直到队列中有元素；当队列满时，试图入队的线程会被阻塞直到队列有空间。这种机制在并发编程中非常有用，可以简化线程间的同步和通信。
小练习
- 队列的enqueue和dequeue操作的时间复杂度是？
- 使用两个栈模拟队列时，dequeue操作的最坏时间复杂度是？
4. 栈和队列的输出序列差异练习
如果我们将相同的输入序列 A, B, C, D 分别输入到一个栈和一个队列中，它们的输出序列会有什么不同？请分析为什么会出现这种差异，并说明栈和队列在元素处理顺序上的本质区别。
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main()
{
// 栈：后进先出（LIFO）
stack<string> stk;
stk.push("A");
stk.push("B");
stk.push("C");
stk.push(
5. 循环队列的模运算练习
在循环队列的实现中，模运算 (rear + 1) % capacity 是如何实现索引的循环回绕的？请用具体的数值例子（如 capacity = 5, rear = 4）来详细说明这个表达式的计算过程，并解释为什么这种方法能够正确地将索引从数组末尾绕回到开头。
#include <iostream>
#include <vector>
using namespace std;
class CircularQueue
{
private:
vector<int> data;
int front;
int rear;
int capacity;
public:
CircularQueue(int cap) : capacity(cap), front(0), rear(-1
6. 用两个栈模拟队列练习
设计并实现一个使用两个栈来模拟队列的数据结构。你需要实现 Enqueue 和 Dequeue 两个操作，并分析这种实现方式的时间复杂度。
要求：一个栈用于入队操作，另一个栈用于出队操作。当需要出队时，如果出队栈为空，则将入队栈的所有元素依次弹出并压入出队栈，这样就能反转元素的顺序。
#include <iostream>
#include <stack>
#include <stdexcept>
using namespace std;
class QueueUsingStacks
{
private:
// 入队栈：用于存储新入队的元素
stack<int> enqueueStack;
// 出队栈：用于存储待出队的元素
stack<int> dequeueStack;
public:
QueueUsingStacks()
{
// 栈会自动初始化
}
// 入队操作 - O(1)
void enqueue(int
7. 优先级队列应用练习
假设你需要为一个银行系统设计排队叫号功能。系统中存在两种类型的客户：普通客户和VIP客户，VIP客户具有更高的优先级。
请分析使用单一FIFO队列是否能够满足需求。如果不能，你会考虑使用什么样的数据结构？请说明你的选择理由，并分析不同数据结构在时间复杂度、空间复杂度和实现复杂度方面的权衡。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stdexcept>
using namespace std;
// 客户类型枚举
enum class CustomerType
{
Normal,
VIP
};
// 客户类
class Customer
{
public:
string name;
CustomerType type;
int ticketNumber;
class
LinkedListQueue
{
public:
// 构造函数：初始化空队列
LinkedListQueue() : head(nullptr), tail(nullptr), count(0) {
// 初始状态下，头指针和尾指针都指向空，表示队列为空
}
// 析构函数：释放所有节点内存，防止内存泄漏
~LinkedListQueue() {
while (!isEmpty()) {
dequeue(); // 通过出队操作逐个释放节点
}
}
// 检查队列是否为空
bool isEmpty() const {
return head == nullptr; // 头指针为空等价于队列为空
}
// 获取队列中元素的数量
size_t size() const {
return count; // 返回维护的计数器值
}
// 入队操作：在队尾添加新元素
void enqueue(const T& data) {
Node<T>* newNode = new Node<T>(data); // 动态分配新节点
if (isEmpty()) {
// 队列为空时，新节点既是队头也是队尾
head = tail = newNode;
} else {
// 将新节点链接到当前队尾，然后更新尾指针
tail->next = newNode;
tail = newNode;
}
count++; // 更新元素计数
}
// 出队操作：移除并返回队头元素
T dequeue() {
if (isEmpty()) {
throw std::out_of_range("Queue is empty, cannot dequeue!");
}
T data = head->data; // 保存队头元素的值
Node<T>* temp = head; // 保存待释放节点的指针
head = head->next; // 将头指针移动到下一个节点
delete temp; // 释放原队头节点的内存
// 如果出队后队列变为空，需要将尾指针也置为空
if (head == nullptr) {
tail = nullptr;
}
count--; // 更新元素计数
return data; // 返回被移除的元素
}
// 访问队头元素（不移除）
T& front() {
if (isEmpty()) {
throw std::out_of_range("Queue is empty, no element at front!");
}
return head->data; // 返回队头元素的引用
}
private:
Node<T>* head; // 指向队头节点的指针
Node<T>* tail; // 指向队尾节点的指针
size_t count; // 队列中元素的数量（可选，用于快速查询大小）
};
resize
(capacity);
}
// 检查队列是否为空
bool isEmpty() const {
// 当队头索引等于队尾索引时，队列为空
return front_idx == rear_idx;
}
// 检查队列是否已满
bool isFull() const {
// 当队尾的下一个位置等于队头时，队列已满
// 模运算确保索引在到达数组末尾时能正确绕回开头
return (rear_idx + 1) % capacity == front_idx;
}
// 获取队列中元素的数量
size_t size() const {
// 通过队尾和队头索引的相对位置计算元素数量
// 需要考虑循环的情况，所以加上capacity再取模
return (rear_idx - front_idx + capacity) % capacity;
}
// 入队操作：在队尾添加新元素
void enqueue(const T& item) {
if (isFull()) {
throw std::overflow_error("Queue is full, cannot enqueue!");
}
elements[rear_idx] = item; // 在队尾位置存储新元素
rear_idx = (rear_idx + 1) % capacity; // 更新队尾索引，使用模运算实现循环
}
// 出队操作：移除并返回队头元素
T dequeue() {
if (isEmpty()) {
throw std::out_of_range("Queue is empty, cannot dequeue!");
}
T item = elements[front_idx]; // 保存队头元素的值
front_idx = (front_idx + 1) % capacity; // 更新队头索引，使用模运算实现循环
return item; // 返回被移除的元素
}
// 访问队头元素（不移除）
T& front() {
if (isEmpty()) {
throw std::out_of_range("Queue is empty, no element at front!");
}
return elements[front_idx]; // 返回队头元素的引用
}
private:
std::vector<T> elements; // 存储队列元素的数组
size_t capacity; // 队列的容量（实际为用户指定容量+1）
size_t front_idx; // 队头元素的索引
size_t rear_idx; // 队尾元素的下一个位置索引
// 注意：不需要count变量，可以通过front_idx和rear_idx计算得出
};
"D"
);
cout << "栈的输出序列（LIFO）:" << endl;
while (!stk.empty())
{
cout << stk.top() << " ";
stk.pop();
}
cout << endl; // 输出: D C B A
// 队列：先进先出（FIFO）
queue<string> que;
que.push("A");
que.push("B");
que.push("C");
que.push("D");
cout << "队列的输出序列（FIFO）:" << endl;
while (!que.empty())
{
cout << que.front() << " ";
que.pop();
}
cout << endl; // 输出: A B C D
return 0;
}
栈的输出序列（LIFO）:
D C B A
队列的输出序列（FIFO）:
A B C D
- 栈的输出序列：
D C B A（后进先出）
- 最后入栈的元素
D 最先出栈
- 体现了 LIFO（Last In First Out）特性
- 队列的输出序列：
A B C D（先进先出）
- 最先入队的元素
A 最先出队
- 体现了 FIFO（First In First Out）特性
- 本质区别：
- 栈：像一摞盘子，只能从顶部取放
- 队列：像排队，先来的人先服务
- 这种差异源于它们不同的数据组织方式和访问规则
)
{
data.resize(capacity);
// 初始时 rear 为 -1，表示队列为空
}
// 入队操作
void enqueue(int value)
{
// 使用模运算实现循环回绕
int prevRear = rear;
rear = (rear + 1) % capacity;
data[rear] = value;
cout << "Enqueue(" << value << "): rear = (" << prevRear
<< " + 1) % " << capacity << " = " << rear << endl;
}
// 出队操作
int dequeue()
{
int value = data[front];
int prevFront = front;
front = (front + 1) % capacity;
cout << "Dequeue(): front = (" << prevFront
<< " + 1) % " << capacity << " = " << front << endl;
return value;
}
void printState()
{
cout << "当前状态: front = " << front << ", rear = " << rear << endl;
}
};
int main()
{
CircularQueue queue(5);
cout << "循环队列模运算示例（capacity = 5）:" << endl;
cout << endl;
// 示例1: rear = 4 时，下一个位置应该是 0
cout << "示例1: rear = 4 时" << endl;
cout << "计算: (4 + 1) % 5 = " << (5 % 5) << " = 0" << endl;
cout << "结果: 索引从 4 绕回到 0" << endl;
cout << endl;
// 示例2: rear = 3 时，下一个位置应该是 4
cout << "示例2: rear = 3 时" << endl;
cout << "计算: (3 + 1) % 5 = " << (4 % 5) << " = 4" << endl;
cout << "结果: 索引正常递增到 4" << endl;
cout << endl;
// 示例3: rear = 0 时，下一个位置应该是 1
cout << "示例3: rear = 0 时" << endl;
cout << "计算: (0 + 1) % 5 = " << (1 % 5) << " = 1" << endl;
cout << "结果: 索引正常递增到 1" << endl;
cout << endl;
// 实际演示
cout << "实际演示:" << endl;
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
queue.enqueue(50); // rear = 4
cout << "\n当 rear = 4 时，再次入队:" << endl;
cout << "计算: (4 + 1) % 5 = 5 % 5 = 0" << endl;
cout << "索引从 4 绕回到 0，实现循环" << endl;
return 0;
}
循环队列模运算示例（capacity = 5）:
示例1: rear = 4 时
计算: (4 + 1) % 5 = 0 = 0
结果: 索引从 4 绕回到 0
示例2: rear = 3 时
计算: (3 + 1) % 5 = 4 = 4
结果: 索引正常递增到 4
示例3: rear = 0 时
计算: (0 + 1) % 5 = 1 = 1
结果: 索引正常递增到 1
实际演示:
Enqueue(10): rear = (-1 + 1) % 5 = 0
Enqueue(20): rear = (0 + 1) % 5 = 1
Enqueue(30): rear = (1 + 1) % 5 = 2
Enqueue(40): rear = (2 + 1) % 5 = 3
Enqueue(50): rear = (3 + 1) % 5 = 4
当 rear = 4 时，再次入队:
计算: (4 + 1) % 5 = 5 % 5 = 0
索引从 4 绕回到 0，实现循环
- 模运算的作用：
(rear + 1) % capacity 确保索引在 [0, capacity-1] 范围内循环
- 具体例子：
- 当
rear = 4, capacity = 5 时：(4 + 1) % 5 = 5 % 5 = 0，索引从 4 绕回到 0
- 当
rear = 3, capacity = 5 时：(3 + 1) % 5 = 4 % 5 = 4，索引正常递增
- 为什么能正确回绕：
- 模运算
% 返回除法的余数
- 当
rear + 1 >= capacity 时，余数为 0，索引回到开头
- 当
rear + 1 < capacity 时，余数就是 rear + 1，索引正常递增
- 循环队列的优势：充分利用数组空间，避免普通队列的"假溢出"问题
value
)
{
enqueueStack.push(value);
cout << "Enqueue(" << value << ")" << endl;
}
// 出队操作 - 平均 O(1)，最坏 O(n)
int dequeue()
{
// 如果出队栈为空，将入队栈的所有元素转移到出队栈
if (dequeueStack.empty())
{
while (!enqueueStack.empty())
{
dequeueStack.push(enqueueStack.top());
enqueueStack.pop();
}
}
if (dequeueStack.empty())
{
throw runtime_error("队列为空，无法出队");
}
int value = dequeueStack.top();
dequeueStack.pop();
cout << "Dequeue() 返回: " << value << endl;
return value;
}
// 检查队列是否为空
bool isEmpty()
{
return enqueueStack.empty() && dequeueStack.empty();
}
};
int main()
{
QueueUsingStacks queue;
cout << "用两个栈模拟队列:" << endl;
cout << endl;
// 入队操作
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
cout << endl;
// 出队操作
queue.dequeue(); // 输出: 1
queue.dequeue(); // 输出: 2
cout << endl;
// 继续入队
queue.enqueue(4);
queue.enqueue(5);
cout << endl;
// 继续出队
queue.dequeue(); // 输出: 3
queue.dequeue(); // 输出: 4
queue.dequeue(); // 输出: 5
cout << endl;
cout << "时间复杂度分析:" << endl;
cout << "- Enqueue: O(1)，直接压入入队栈" << endl;
cout << "- Dequeue: 平均 O(1)，最坏 O(n)" << endl;
cout << " - 当出队栈为空时，需要将入队栈的所有元素转移" << endl;
cout << " - 每个元素最多被转移一次，所以平均时间复杂度是 O(1)" << endl;
return 0;
}
用两个栈模拟队列:
Enqueue(1)
Enqueue(2)
Enqueue(3)
Dequeue() 返回: 1
Dequeue() 返回: 2
Enqueue(4)
Enqueue(5)
Dequeue() 返回: 3
Dequeue() 返回: 4
Dequeue() 返回: 5
时间复杂度分析:
- Enqueue: O(1)，直接压入入队栈
- Dequeue: 平均 O(1)，最坏 O(n)
- 当出队栈为空时，需要将入队栈的所有元素转移
- 每个元素最多被转移一次，所以平均时间复杂度是 O(1)
- 设计思路：
- 使用两个栈：
enqueueStack（入队栈）和 dequeueStack（出队栈）
- 入队时，直接将元素压入
enqueueStack
- 出队时，如果
dequeueStack 为空，将 enqueueStack 的所有元素转移到 dequeueStack（反转顺序）
- 时间复杂度：
- Enqueue：O(1)，直接压入栈
- Dequeue：平均 O(1)，最坏 O(n)
- 最坏情况：出队栈为空时，需要转移 n 个元素
- 平均情况：每个元素最多被转移一次，所以平均是 O(1)
- 空间复杂度：O(n)，需要两个栈存储元素
- 关键思想：利用栈的 LIFO 特性，通过两次反转（入队栈 → 出队栈）实现队列的 FIFO 特性
Customer
(
const
string
&
name
,
CustomerType
type
,
int
ticketNumber
)
: name(name), type(type), ticketNumber(ticketNumber)
{
}
string toString() const
{
string typeStr = (type == CustomerType::VIP) ? "VIP" : "Normal";
return typeStr + "客户 " + name + " (票号: " + to_string(ticketNumber) + ")";
}
};
// 使用优先队列的银行叫号系统
class BankQueueSystem
{
private:
// 使用 vector 模拟优先队列（实际应用中应使用堆）
vector<Customer> queue;
// 比较函数：VIP 优先，同优先级按票号排序
static bool compareCustomers(const Customer& a, const Customer& b)
{
if (a.type != b.type)
{
// VIP 优先（VIP 的枚举值更大）
return a.type > b.type;
}
// 同优先级按票号排序
return a.ticketNumber < b.ticketNumber;
}
public:
BankQueueSystem()
{
// vector 会自动初始化
}
// 入队操作 - O(n)（使用 vector，实际应使用堆实现 O(log n)）
void enqueue(const Customer& customer)
{
queue.push_back(customer);
// 按优先级排序：VIP 优先，同优先级按票号排序
sort(queue.begin(), queue.end(), compareCustomers);
cout << "入队: " << customer.toString() << endl;
}
// 出队操作 - O(1)
Customer dequeue()
{
if (queue.empty())
{
throw runtime_error("队列为空");
}
Customer customer = queue[0];
queue.erase(queue.begin());
cout << "出队: " << customer.toString() << endl;
return customer;
}
// 显示当前队列状态
void printQueue()
{
cout << "\n当前队列状态:" << endl;
if (queue.empty())
{
cout << "队列为空" << endl;
}
else
{
for (const auto& customer : queue)
{
cout << " - " << customer.toString() << endl;
}
}
cout << endl;
}
// 检查队列是否为空
bool isEmpty()
{
return queue.empty();
}
};
int main()
{
BankQueueSystem system;
cout << "银行叫号系统（优先级队列）:" << endl;
cout << endl;
// 模拟客户排队
system.enqueue(Customer("张三", CustomerType::Normal, 1));
system.enqueue(Customer("李四", CustomerType::VIP, 2));
system.enqueue(Customer("王五", CustomerType::Normal, 3));
system.enqueue(Customer("赵六", CustomerType::VIP, 4));
system.enqueue(Customer("钱七", CustomerType::Normal, 5));
system.printQueue();
// 模拟叫号
cout << "开始叫号:" << endl;
while (!system.isEmpty())
{
system.dequeue();
}
cout << "\n数据结构选择分析:" << endl;
cout << "1. 单一FIFO队列：" << endl;
cout << " - 无法满足需求，VIP客户无法优先" << endl;
cout << " - 时间复杂度: Enqueue O(1), Dequeue O(1)" << endl;
cout << " - 空间复杂度: O(n)" << endl;
cout << " - 实现复杂度: 低" << endl;
cout << endl;
cout << "2. 优先队列（推荐）:" << endl;
cout << " - 满足需求，VIP客户优先服务" << endl;
cout << " - 时间复杂度: Enqueue O(log n), Dequeue O(log n)" << endl;
cout << " - 空间复杂度: O(n)" << endl;
cout << " - 实现复杂度: 中等（使用堆实现）" << endl;
cout << endl;
cout << "3. 两个队列（普通队列 + VIP队列）:" << endl;
cout << " - 满足需求，但需要额外逻辑管理" << endl;
cout << " - 时间复杂度: Enqueue O(1), Dequeue O(1)" << endl;
cout << " - 空间复杂度: O(n)" << endl;
cout << " - 实现复杂度: 中等" << endl;
return 0;
}
- 单一FIFO队列的问题：
- 无法满足需求，VIP客户无法优先服务
- 所有客户按先来后到的顺序服务
- 优先队列方案（推荐）：
- 使用堆（Heap）数据结构实现
- VIP客户优先级更高，会先于普通客户被服务
- 时间复杂度：Enqueue O(log n)，Dequeue O(log n)
- 空间复杂度：O(n)
- 实现复杂度：中等
- 两个队列方案：
- 使用普通队列和VIP队列分别存储
- 出队时优先从VIP队列取，VIP队列为空时才从普通队列取
- 时间复杂度：Enqueue O(1)，Dequeue O(1)
- 空间复杂度：O(n)
- 实现复杂度：中等
- 权衡分析：
- 如果只有两种优先级，两个队列方案更简单高效
- 如果有多种优先级，优先队列方案更灵活
- 优先队列使用堆实现，适合动态优先级场景