1. 队列的基本概念
特性
先进先出(FIFO)：最先进入的元素最先出队
两端操作：只能在一端(队尾)添加，在另一端(队头)删除
顺序存取：元素按进入顺序存储和访问
2. C++ 中的队列实现
2.1 std::queue (标准库队列)
cpp
#include <queue>
#include <iostream>
using namespace std;
int main() {
// 创建队列
queue<int> q;
}
2.2 基于数组的循环队列
cpp
#include <iostream>
using namespace std;
class CircularQueue {
private:
int *arr;
int front, rear, capacity;
public:
CircularQueue(int size) {
capacity = size;
arr = new int[capacity];
front = rear = -1;
}
};
// 使用示例
int main() {
CircularQueue cq(5);
cq.enqueue(1);
cq.enqueue(2);
cq.enqueue(3);
cq.display(); // 输出: 1 2 3
}
2.3 基于链表的队列
cpp
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class LinkedListQueue {
private:
Node *front, *rear;
public:
LinkedListQueue() : front(nullptr), rear(nullptr) {}
};
3. 不同类型的队列
3.1 std::priority_queue (优先队列)
cpp
#include <queue>
#include <iostream>
using namespace std;
int main() {
// 最大堆（默认）
priority_queue<int> maxHeap;
}
3.2 std::deque (双端队列)
cpp
#include <deque>
#include <iostream>
using namespace std;
int main() {
deque<int> dq;
}
4. 队列的常用操作汇总
std::queue 主要成员函数
函数 说明 时间复杂度
push(value) 入队 O(1)
pop() 出队 O(1)
front() 访问队首 O(1)
back() 访问队尾 O(1)
empty() 判断空 O(1)
size() 获取大小 O(1)
5. 实际应用场景
5.1 广度优先搜索(BFS)
cpp
#include <queue>
#include <vector>
using namespace std;
void BFS(vector<vector<int>>& graph, int start) {
vector<bool> visited(graph.size(), false);
queue<int> q;
}
5.2 任务调度系统
cpp
#include <queue>
#include <string>
#include <iostream>
using namespace std;
struct Task {
string name;
int priority;
};
class TaskScheduler {
private:
queue<Task> taskQueue;
public:
void addTask(const string& name, int priority = 0) {
taskQueue.push(Task(name, priority));
}
};
6. 性能比较
队列类型 插入性能 删除性能 空间复杂度 适用场景
stdqueue O(1) O(1) O(n) 一般队列操作
循环队列 O(1) O(1) O(n) 固定大小队列
链表队列 O(1) O(1) O(n) 动态大小队列
优先队列 O(log n) O(log n) O(n) 需要优先级
7. 选择指南
普通FIFO需求：使用 stdqueue
需要两端操作：使用 std::deque
优先级处理：使用 std::priority_queue
固定大小优化：使用循环队列
动态大小：使用链表队列
