队列（queue）及优先队列（priority_queue）

基础队列的思想就是先进先出最先放进队列里的元素最先被访问和移除队列新添加的元素放置在队列的尾部。队列queue容器的C标准头文件为queue提供的基础操作及实例如下empty判断队列是否为空若空则返回true否则返回falsesize返回当前队列的大小即队列里元素的个数front返回队首元素push将元素添加到队尾pop移除队首元素。具体示例:#include iostream #include queue using namespace std; int main() { queueint q; // 1. 入队 (Push) q.push(10); q.push(20); q.push(30); // 此时队列内容[10, 20, 30] (10在队头) // 2. 查看队首 (Front) - 不移除 cout 队首元素: q.front() endl; // 输出 10 // 3. 查看队尾 (Back) cout 队尾元素: q.back() endl; // 输出 30 // 4. 出队 (Pop) - 移除队首 q.pop(); // 此时队列内容[20, 30] // 5. 判断是否为空 (Empty) if (!q.empty()) { cout 队列大小: q.size() endl; // 输出 2 } return 0; }尺取法的本质就是维护一个动态的队列使用队列的空间复杂度比双指针更高优先队列优先级驱动适用于需要按优先级处理元素的场景Dijkstra算法在最短路径算法中优先队列用于选择当前距离最小的节点进行扩展提高算法效率。Huffman编码在数据压缩中优先队列用于构建Huffman树选择频率最低的字符进行合并。任务调度按紧急程度如医院急诊系统优先处理病情更严重的病人而不是按到达顺序。实时系统在实时操作系统中高优先级的任务需要立即执行优先队列确保这些任务被优先处理。优先队列会自动排序默认是大顶堆最大的元素在队首优先队列普通操作示例代码:#include iostream #include queue #include vector using namespace std; int main(){ //默认是大顶堆最大的先出来 priority_queueint pq_max; pq_max.push(10); pq_max.push(20); pq_max.push(30); //输出顺序将是30 20 10 while(!pq_max.empty()){ coutpq_max.top() ; pq_max.pop(); } coutendl; return 0; }进阶如何变成小根堆很多时候我们需要最小的元素先出来比如 Dijkstra 算法求最短路这时需要加一个比较函数。priority_queueint,vectorint,greaterint pq_min;重点priority_queueint,vectorint,greaterint pq_min;//注意参数顺序 //小根堆小的先出来 pq_min.push(10); pq_min.push(30); pq_min.push(20); //输出顺序将是10 20 30 while(!pq_min.empty()){ coutpq_min.top() ; pq_min.pop(); }队列适用于需要按顺序处理元素的场景任务调度操作系统中的进程调度、打印机任务队列等。任务按提交顺序依次处理保证公平性。广度优先搜索BFS在图或树的遍历中队列用于存储待访问的节点确保按层级顺序访问。缓冲区管理如视频播放器的缓冲区数据按到达顺序播放避免乱序。消息队列在分布式系统中消息按发送顺序被消费者处理保证消息的有序性。队列应用场景示例代码模拟买票void demoQueue(){ queuestring people; people.push(张三); people.push(李四); people.push(王五); cout---开始叫号---endl; while(!people.empty()){ cout请people.front()办理业务endl; people.pop();//办理完离开队列 } }