队列容器(queue container in STL)
一、队列容器
数据结构中队列具有先进先出(FIFO)的特点，队尾进、队头出。
STL里调用队列需要加上头文件 #include <queue>
STL为queue提供了一些成员函数如下：
| 函数名 | 功能 |
| push() | 进队，把一个元素压入队尾 |
| pop() | 出队，把队头元素弹出 |
| front() | 返回队头元素 |
| back() | 返回队尾元素 |
| size() | 无素个数，队列的大小–即队中已有元素的个数 |
| empty() | 判断队空，等价于size为0 |
例题：取扑克牌
有N(<100)张扑克牌放成一堆，每次从上面取一张牌翻开，如果是奇数次取牌，牌就翻开放成一排，如果偶数次取到的牌放到下面，直到取完。使用一个队列表示这堆牌，输出牌的翻开顺序。
例如：N=4
牌从上到下顺序是(输入)：1,2,3,4 输出：1,3,2,4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include <iostream> #include <queue> using namespace std; queue<int> pai; int main(){ int N,x; cin>>N; for (int i = 0; i < N; i++) { cin>>x; pai.push(x); } for (int i = 1; !pai.empty(); i++) { if(i%2==1)cout<<pai.front()<<" "; else{ x=pai.front(); pai.push(x); } pai.pop(); } return 0; } |
二、优先队列(priority_queue)
组别：提高组
难度：5
1、概念
优先队列是一种用于管理一组元素的容器，其中每个元素都有一个关联的优先级。优先队列确保每次访问或删除元素时，都会处理具有最高优先级的元素。
元素的优先级是根据比较函数来决定的。这意味着你可以定义任何逻辑来决定元素的优先级，只要这个逻辑可以通过比较函数来表达。默认情况下，优先队列使用std::less作为比较函数，这会导致最大的元素具有最高的优先级（即，一个最大堆）。
优先队列通常是用堆（Heap）这种数据结构实现的。堆是一种特殊的树形数据结构，它满足堆属性：对于一个最大堆（Max-Heap），任何一个非叶子节点的值都大于或等于其子节点的值；对于一个最小堆（Min-Heap），任何一个非叶子节点的值都小于或等于其子节点的值。
优先队列的常见实现方式是二叉堆（Binary Heap）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | /**************************************************************** * Description: C++ STL priority_queue * Author: Alex Li * Date: 2024-04-01 16:13:41 * LastEditTime: 2024-04-04 21:20:45 ****************************************************************/ #include <iostream> #include <queue> #include <vector> using namespace std; int main() { // 创建一个最大元素优先的优先队列 priority_queue<int> maxHeap; // 创建一个最小元素优先的优先队列 // 第二个参数 std::vector<int> 是容器类型，用于底层存储 // 第三个参数 std::greater<int> 是比较函数，确保最小元素在顶部 priority_queue<int, vector<int>, greater<int> > minHeap; // 向优先队列中添加元素 maxHeap.push(10); maxHeap.push(5); maxHeap.push(20); // 向优先队列中添加一些元素 minHeap.push(10); minHeap.push(5); minHeap.push(20); // 输出并移除优先级最高的元素 while (!maxHeap.empty()) { cout << maxHeap.top() <<' '; // 访问最高优先级元素 maxHeap.pop(); // 移除最高优先级元素 } cout<<'\n'; // 输出并移除优先级最高（值最小）的元素 while (!minHeap.empty()) { cout << minHeap.top() <<' '; // 访问优先级最高的元素 minHeap.pop(); // 移除优先级最高的元素 } return 0; } |
2. 优先队列与结构体
1、结构体内已经定义好了比较运算符，下面代码按优先级降序排列，也就是大顶堆。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | /**************************************************************** * Description: 优先队列与结构体,结构体内定义比较运算符 * Author: Alex Li * Date: 2024-08-06 16:08:11 * LastEditTime: 2024-08-06 16:15:25 ****************************************************************/ #include <iostream> #include <queue> #include <vector> using namespace std; // 定义一个结构体 struct Task { int priority; // 任务优先级 string name; // 任务名称 // 定义比较运算符，用于优先队列的排序 bool operator<(const Task& other) const { // 优先级越高，任务越早执行 return priority < other.priority; } }; int main() { // 创建一个优先队列 priority_queue<Task> pq; // 向优先队列中添加元素 pq.push(Task{3, "Task 1"}); pq.push(Task{5, "Task 2"}); pq.push(Task{1, "Task 3"}); pq.push(Task{4, "Task 4"}); // 从优先队列中取出元素 while (!pq.empty()) { Task t = pq.top(); std::cout << "Executing " << t.name << " with priority " << t.priority << std::endl; pq.pop(); } return 0; } |
2、如果优先队列元素是结构体，没有内定义比较符，可以自定义一个比较函数来实现，下面代码是优先级降序排列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | /**************************************************************** * Description: 优先队列，比较函数单独写 * Author: Alex Li * Date: 2024-08-06 16:23:17 * LastEditTime: 2024-08-06 16:28:13 ****************************************************************/ #include <iostream> #include <queue> #include <vector> // 定义一个结构体 struct Task { int priority; // 任务优先级 std::string name; // 任务名称 }; // 自定义比较器 struct CompareTask { bool operator()(const Task& t1, const Task& t2) { // 优先级越高，任务越早执行 return t1.priority < t2.priority; } }; int main() { // 创建一个优先队列，使用自定义比较器 std::priority_queue<Task, std::vector<Task>, CompareTask> pq; // 向优先队列中添加元素 pq.push(Task{3, "Task 1"}); pq.push(Task{5, "Task 2"}); pq.push(Task{1, "Task 3"}); pq.push(Task{4, "Task 4"}); // 从优先队列中取出元素 while (!pq.empty()) { Task t = pq.top(); std::cout << "Executing " << t.name << " with priority " << t.priority << std::endl; pq.pop(); } return 0; } |
2021 CSP_S 复赛第一题
3、优先队列与对组(pair)
在使用优先队列存储 pair 类型的元素时，优先级的处理取决于你对 pair 中的元素的优先级顺序的定义。标准的 C++ 优先队列（std::priority_queue）使用最大堆，即默认情况下最大的元素会在队列的顶部。对于 pair 类型的元素，默认比较规则是按字典顺序比较，即首先比较第一个元素，如果第一个元素相等，再比较第二个元素。
默认的比较规则
如果你使用的是 std::pair<int, int> 类型的元素，优先队列会按照以下规则比较 pair:
先比较第一个 int。
如果第一个 int 相等，再比较第二个 int。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <queue> #include <vector> #include <iostream> int main() { std::priority_queue<std::pair<int, int>> pq; pq.push({1, 5}); pq.push({2, 3}); pq.push({1, 7}); pq.push({2, 2}); while (!pq.empty()) { std::pair<int, int> top = pq.top(); std::cout << "(" << top.first << ", " << top.second << ")\n"; pq.pop(); } return 0; } |
上面例子输出为：
(2, 3)
(2, 2)
(1, 7)
(1, 5)
自定义比较规则
如果你想要自定义优先级规则，可以通过传递一个自定义的比较函数或者函数对象。
如果你想要按照 pair 的第二个元素从小到大的顺序来确定优先级，可以自定义一个比较函数，使得第二个元素较小的 pair 在优先队列的顶部。你可以通过定义一个比较函数对象来实现这个功能。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | /**************************************************************** * Description: 优先队列+pair自定义比较函数 * Author: Alex Li * Date: 2024-08-12 15:50:59 * LastEditTime: 2024-08-12 15:51:36 ****************************************************************/ #include <queue> #include <vector> #include <iostream> struct CompareSecondAscending { bool operator()(const std::pair<int, int>& p1, const std::pair<int, int>& p2) { return p1.second > p2.second; } }; int main() { std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, CompareSecondAscending> pq; pq.push({1, 5}); pq.push({2, 3}); pq.push({1, 7}); pq.push({2, 2}); while (!pq.empty()) { std::pair<int, int> top = pq.top(); std::cout << "(" << top.first << ", " << top.second << ")\n"; pq.pop(); } return 0; } |
代码解释
CompareSecondAscending是一个比较函数对象，它的operator()函数定义了pair的比较规则。operator()函数中，p1.second > p2.second这个条件用于比较pair中的第二个元素。如果p1.second大于p2.second，那么p1的优先级更低，因此这个函数返回true。- 因为
std::priority_queue默认是一个最大堆，比较函数返回true时，它会将p2放在p1之前，所以我们使用>来实现从小到大的顺序。
输出结果
运行上面的代码将会产生以下输出：
(2, 2)
(2, 3)
(1, 5)
(1, 7)
这表明 priority_queue 按照第二个元素从小到大的顺序来排序了 pair。
三、双端队列(deque) 详见数组结构-树
习题：廊桥分配
题目描述
当一架飞机抵达机场时，可以停靠在航站楼旁的廊桥，也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥，因为这样省去了坐摆渡车前往航站楼的周折。然而，因为廊桥的数量有限，所以这样的愿望不总是能实现。
机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只能停靠在国际区。一部分廊桥属于国内区，其余的廊桥属于国际区。
L 市新建了一座机场，一共有 n 个廊桥。该机场决定，廊桥的使用遵循“先到先得”的原则，即每架飞机抵达后，如果相应的区（国内/国际）还有空闲的廊桥，就停靠在廊桥，否则停靠在远机位（假设远机位的数量充足）。该机场只有一条跑道，因此不存在两架飞机同时抵达的情况。
现给定未来一段时间飞机的抵达、离开时刻，请你负责将 n 个廊桥分配给国内区和国际区，使停靠廊桥的飞机数量最多。
输入格式
输入的第一行，包含三个正整数 n,m1,m2，分别表示廊桥的个数、国内航班飞机的数量、国际航班飞机的数量。
接下来 m1行，是国内航班的信息，第 i行包含两个正整数 a1,i,b1,i，分别表示一架国内航班飞机的抵达、离开时刻。
接下来 m2 行，是国际航班的信息，第 i行包含两个正整数 a2,i,b2,i，分别表示一架国际航班飞机的抵达、离开时刻。
每行的多个整数由空格分隔。
输出格式
输出一个正整数，表示能够停靠廊桥的飞机数量的最大值。
输入输出样例
输入 #1
3 5 4
1 5
3 8
6 10
9 14
13 18
2 11
4 15
7 17
12 16
输出 #1
7
输入 #2
2 4 6
20 30
40 50
21 22
41 42
1 19
2 18
3 4
5 6
7 8
9 10
输出 #2
4
需要注意的是，本题中廊桥的使用遵循“先到先得”的原则，如果国际区只有 1 个廊桥，那么将被飞机 (1,19)占用，而不会被 (3,4)、(5,6)、(7,8)、(9,10) 这 4 架飞机先后使用。
P7913 [2021CSP-S-1 ] [P5941]