队列与C++中的queue详解
队列（queue）什么是队列队列就是一种线性的数据结构，它与日常生活中排队的队列相似，即先进先出（lifo, first in first out)，这点也是它与栈stack的最大不同之处。它的结构类似于下面的容器：
如上图所示，队列的结构就像一个两端都是开口的容器，一端只负责小球（对应队列中的元素）进入，一个端只负责小球弹出，容器内部的小球无法跳过前面的小球提前弹出。我们将队列的出口端（即队列的头部）叫做队头（front），入口端（即队列的末尾）称为队尾（rear）。
与栈类似，队列的底层数据结构也可以使用数组和链表来实现，具体如下图所示：
队列的基本操作和应用队列的基本操作与栈类似，主要是分为入队（enqueue）和出队（dequeue），我们以数组为例，简单描述一下具体过程。
1. 入队入队就是把新元素放入队列中去，由于队列的数据结构的限制，只允许将新入队元素放入队尾的位置，然后更新队尾的位置，具体过程如下图所示。
2. 出队出队就是把队列中的元素移出来，同样的，队列只允许在队列的队头这一侧移出元素，即每次移出的元素就是队头对应的元素，元素移出后，原对头元素的后面一个元素变为新的队头，具体过程如下所示：
3. 入队出队的复杂度和应用与栈类似，队列的入队与出队只与队头和队尾的元素相关，不涉及其他元素的移动，因此队列的入队和出队的时间复杂度都是。
队列先进先出的特性使得其常用于一下场景中：
消息队列：在分布式系统或异步任务处理场景中，消息队列可以用于解耦任务的发布与消费，确保任务能够稳定地进行下去。程序调度：操作系统、多线程程序、并发网络程序等需要协调多个任务的程序中，通常会使用队列来维护任务的执行顺序，以保证每个任务都能够得到执行。广度优先搜索：在图论、路径查找等问题中，广度优先搜索算法通常会使用队列来存储待搜索的节点，以确保每一层的所有节点都可以被访问到。缓存：在许多应用中，缓存通常使用队列来管理缓存项的过期时间和更替策略，使得缓存可以高效地使用有限的内存资源。类模板std::queuestd::queue类是c++提供的容器适配器，它提供了特定的函数集合，实现了队列的基本功能：fifo的数据结构，即在容器的尾端推入元素，在首段弹出元素。std::queue类在头文件中定义，其函数声明如下：
template class queue;形参t和containert ：存储的元素类型。container ：用于存储元素的底层容器。容器类型必须是序列容器，同时，该容器类型需提供通常语义下的back()、front()、push_back()和pop_front()函数，满足该要求的标准容器有std::deque和std::list，其中默认使用的容器是std::deque。成员函数1. 元素访问front ：访问队列第一个元素。其函数声明如下：reference front();const_reference front() const;该函数返回队列中首个元素的引用，实际上该函数等效的调用的就是存储元素的底层容器（container）的front()函数。
back ：访问队列最后一个元素。其函数声明如下：reference back();const_reference back() const;该函数返回的是队列末尾元素的引用，实际上该函数等效的调用的就是container的back()函数。
2. 容量empty ：检查队列是否为空。其函数声明如下：bool empty() const; // c++20 前[[nodiscard]] bool empty() const; //c++20 起其本质上就是检查container是否为空，即container的empty()。如果为空返回true，否则为false。
size ：返回队列中的元素个数。其函数声明如如下：size_type size() const;同样的，其本质还是返回的是container的元素个数，即container的size()。
3. 队列的修改push ：向队列的尾部插入元素，对应的就是入队操作。其函数声明如下：void push( const value_type& value );void push( value_type&& value ); //c++11 起emplace ：在队列的尾部构造元素，对应的也是入队的操作。其函数声明如下：templatevoid emplace( args&&... args );// c++11 起 c++17 前templatedecltype(auto) emplace( args&&... args );// c++17 起该函数就是将新元素推到队列的尾部，其与push不同的是：该函数是原地构造元素，即不进行移动或复制操作，使用参数直接原地调用元素的构造函数，使得其效率高于push。
pop ：删除队列首个元素，对应的就是出队操作。其函数声明如下：void pop();该函数移除队列前端的元素，等效的调用了container的pop_front()函数。
swap ：交换两个容器的内容。其函数声明如下：void swap( queue& other ) noexcept(); //c++11 起其本质上是交换两个container中的内容。
用法示例#include #include using namespace std;void showqueue(string queuename, queue& q) { cout < < 队列 < < queuename < < 中元素的数量, 即size() = < < q.size() < < endl; if (!q.empty()) { cout < < 此时, 队列 < < queuename < < 不为空,即empty() = false < < endl; cout < < 队列首位元素，即front() = < < q.front() < < endl; cout < < 队列首位元素，即back() = < < q.back() < < endl; } else { cout < < 此时, 队列 < < queuename < < 为空,即empty() = true < < endl; }}int main() { queue q; // push() q.push(1); q.push(2); q.push(3); cout < < ---按顺push元素1、2、3后:n < < endl; showqueue(q, q); q.pop(); // 弹出队头元素 cout < < n---弹出队头元素3, 即pop()后:n < < endl; showqueue(q, q); q.pop(); cout < < n---弹出队头元素2, 即pop()后:n < < endl; showqueue(q, q); q.pop(); cout < < n---弹出队头元素1, 即pop()后:n < < endl; showqueue(q, q); queue q1; q1.emplace(1); q1.emplace(2); q1.emplace(3); cout < < n-----------队列q和q1交换前---------- < < endl; cout < < nq的状态: < < endl; showqueue(q, q); cout < < nq1的状态: < < endl; showqueue(q1, q1); q1.swap(q); // s和s1进行交换 cout < < n-----------队列q和q1交换后----------n < < endl; showqueue(q, q); cout < < nq1的状态: < < endl; showqueue(q1, q1); return 0;}输出结果：
---按顺push元素1、2、3后:队列q中元素的数量, 即size() = 3此时, 队列q不为空,即empty() = false队列首位元素，即front() = 1队列首位元素，即back() = 3---弹出队头元素3, 即pop()后:队列q中元素的数量, 即size() = 2此时, 队列q不为空,即empty() = false队列首位元素，即front() = 2队列首位元素，即back() = 3---弹出队头元素2, 即pop()后:队列q中元素的数量, 即size() = 1此时, 队列q不为空,即empty() = false队列首位元素，即front() = 3队列首位元素，即back() = 3---弹出队头元素1, 即pop()后:队列q中元素的数量, 即size() = 0此时, 队列q为空,即empty() = true-----------队列q和q1交换前----------q的状态: 队列q中元素的数量, 即size() = 0此时, 队列q为空,即empty() = trueq1的状态: 队列q1中元素的数量, 即size() = 3此时, 队列q1不为空,即empty() = false队列首位元素，即front() = 1队列首位元素，即back() = 3-----------队列q和q1交换后----------队列q中元素的数量, 即size() = 3此时, 队列q不为空,即empty() = false队列首位元素，即front() = 1队列首位元素，即back() = 3q1的状态: 队列q1中元素的数量, 即size() = 0此时, 队列q1为空,即empty() = true
如何对嵌入式最小系统的软硬件架构进行改进？
锂离子电池纳米硅碳负极材料研究进展、制备方法在电池中的应用及展望
全球手术机器人领域重要融资事件汇总
往复式压缩机主要部件_往复式压缩机优缺点
电视信号传输系统及优劣选择
队列与C++中的queue详解
ATOS比例控制阀放大器QVHMZO-A介绍
Vishay推出新型第三代650 V SiC肖特基二极管，提升开关电源设计能效和可靠性
NI PXI缩短射频功率放大器的特征化时间
自动驾驶中的激光雷达目标检测的原理和数据特点
LED驱动芯片WT0031概述及功能特点
火花塞型号对照表_汽车火花塞型号一览表如何保养火花塞？
2018财年英飞凌营收达75.99亿欧元，营业利润13.53亿欧元
威联通科技宣布推出新型大容量机架式QuTS hero NAS
发光二极管的主要参数
轻流第三届无代码探索者大会落幕
数据平台正在成为一种新模式为企业开辟了一条崭新的发展之路
苹果最强最贵Mac Pro诞生 iPadOS和iOS分家
PCB自动光学检测的自动选取定位核满足实时性
TDK | 家电解决方案：主要家电
如上图所示，队列的结构就像一个两端都是开口的容器，一端只负责小球（对应队列中的元素）进入，一个端只负责小球弹出，容器内部的小球无法跳过前面的小球提前弹出。我们将队列的出口端（即队列的头部）叫做队头（front），入口端（即队列的末尾）称为队尾（rear）。
与栈类似，队列的底层数据结构也可以使用数组和链表来实现，具体如下图所示：
队列的基本操作和应用队列的基本操作与栈类似，主要是分为入队（enqueue）和出队（dequeue），我们以数组为例，简单描述一下具体过程。
1. 入队入队就是把新元素放入队列中去，由于队列的数据结构的限制，只允许将新入队元素放入队尾的位置，然后更新队尾的位置，具体过程如下图所示。
2. 出队出队就是把队列中的元素移出来，同样的，队列只允许在队列的队头这一侧移出元素，即每次移出的元素就是队头对应的元素，元素移出后，原对头元素的后面一个元素变为新的队头，具体过程如下所示：
3. 入队出队的复杂度和应用与栈类似，队列的入队与出队只与队头和队尾的元素相关，不涉及其他元素的移动，因此队列的入队和出队的时间复杂度都是。
队列先进先出的特性使得其常用于一下场景中：
消息队列：在分布式系统或异步任务处理场景中，消息队列可以用于解耦任务的发布与消费，确保任务能够稳定地进行下去。程序调度：操作系统、多线程程序、并发网络程序等需要协调多个任务的程序中，通常会使用队列来维护任务的执行顺序，以保证每个任务都能够得到执行。广度优先搜索：在图论、路径查找等问题中，广度优先搜索算法通常会使用队列来存储待搜索的节点，以确保每一层的所有节点都可以被访问到。缓存：在许多应用中，缓存通常使用队列来管理缓存项的过期时间和更替策略，使得缓存可以高效地使用有限的内存资源。类模板std::queuestd::queue类是c++提供的容器适配器，它提供了特定的函数集合，实现了队列的基本功能：fifo的数据结构，即在容器的尾端推入元素，在首段弹出元素。std::queue类在头文件中定义，其函数声明如下：
template class queue;形参t和containert ：存储的元素类型。container ：用于存储元素的底层容器。容器类型必须是序列容器，同时，该容器类型需提供通常语义下的back()、front()、push_back()和pop_front()函数，满足该要求的标准容器有std::deque和std::list，其中默认使用的容器是std::deque。成员函数1. 元素访问front ：访问队列第一个元素。其函数声明如下：reference front();const_reference front() const;该函数返回队列中首个元素的引用，实际上该函数等效的调用的就是存储元素的底层容器（container）的front()函数。
back ：访问队列最后一个元素。其函数声明如下：reference back();const_reference back() const;该函数返回的是队列末尾元素的引用，实际上该函数等效的调用的就是container的back()函数。
2. 容量empty ：检查队列是否为空。其函数声明如下：bool empty() const; // c++20 前[[nodiscard]] bool empty() const; //c++20 起其本质上就是检查container是否为空，即container的empty()。如果为空返回true，否则为false。
size ：返回队列中的元素个数。其函数声明如如下：size_type size() const;同样的，其本质还是返回的是container的元素个数，即container的size()。
3. 队列的修改push ：向队列的尾部插入元素，对应的就是入队操作。其函数声明如下：void push( const value_type& value );void push( value_type&& value ); //c++11 起emplace ：在队列的尾部构造元素，对应的也是入队的操作。其函数声明如下：templatevoid emplace( args&&... args );// c++11 起 c++17 前templatedecltype(auto) emplace( args&&... args );// c++17 起该函数就是将新元素推到队列的尾部，其与push不同的是：该函数是原地构造元素，即不进行移动或复制操作，使用参数直接原地调用元素的构造函数，使得其效率高于push。
pop ：删除队列首个元素，对应的就是出队操作。其函数声明如下：void pop();该函数移除队列前端的元素，等效的调用了container的pop_front()函数。
swap ：交换两个容器的内容。其函数声明如下：void swap( queue& other ) noexcept(); //c++11 起其本质上是交换两个container中的内容。
用法示例#include #include using namespace std;void showqueue(string queuename, queue& q) { cout < < 队列 < < queuename < < 中元素的数量, 即size() = < < q.size() < < endl; if (!q.empty()) { cout < < 此时, 队列 < < queuename < < 不为空,即empty() = false < < endl; cout < < 队列首位元素，即front() = < < q.front() < < endl; cout < < 队列首位元素，即back() = < < q.back() < < endl; } else { cout < < 此时, 队列 < < queuename < < 为空,即empty() = true < < endl; }}int main() { queue q; // push() q.push(1); q.push(2); q.push(3); cout < < ---按顺push元素1、2、3后:n < < endl; showqueue(q, q); q.pop(); // 弹出队头元素 cout < < n---弹出队头元素3, 即pop()后:n < < endl; showqueue(q, q); q.pop(); cout < < n---弹出队头元素2, 即pop()后:n < < endl; showqueue(q, q); q.pop(); cout < < n---弹出队头元素1, 即pop()后:n < < endl; showqueue(q, q); queue q1; q1.emplace(1); q1.emplace(2); q1.emplace(3); cout < < n-----------队列q和q1交换前---------- < < endl; cout < < nq的状态: < < endl; showqueue(q, q); cout < < nq1的状态: < < endl; showqueue(q1, q1); q1.swap(q); // s和s1进行交换 cout < < n-----------队列q和q1交换后----------n < < endl; showqueue(q, q); cout < < nq1的状态: < < endl; showqueue(q1, q1); return 0;}输出结果：
---按顺push元素1、2、3后:队列q中元素的数量, 即size() = 3此时, 队列q不为空,即empty() = false队列首位元素，即front() = 1队列首位元素，即back() = 3---弹出队头元素3, 即pop()后:队列q中元素的数量, 即size() = 2此时, 队列q不为空,即empty() = false队列首位元素，即front() = 2队列首位元素，即back() = 3---弹出队头元素2, 即pop()后:队列q中元素的数量, 即size() = 1此时, 队列q不为空,即empty() = false队列首位元素，即front() = 3队列首位元素，即back() = 3---弹出队头元素1, 即pop()后:队列q中元素的数量, 即size() = 0此时, 队列q为空,即empty() = true-----------队列q和q1交换前----------q的状态: 队列q中元素的数量, 即size() = 0此时, 队列q为空,即empty() = trueq1的状态: 队列q1中元素的数量, 即size() = 3此时, 队列q1不为空,即empty() = false队列首位元素，即front() = 1队列首位元素，即back() = 3-----------队列q和q1交换后----------队列q中元素的数量, 即size() = 3此时, 队列q不为空,即empty() = false队列首位元素，即front() = 1队列首位元素，即back() = 3q1的状态: 队列q1中元素的数量, 即size() = 0此时, 队列q1为空,即empty() = true
如何对嵌入式最小系统的软硬件架构进行改进？
锂离子电池纳米硅碳负极材料研究进展、制备方法在电池中的应用及展望
全球手术机器人领域重要融资事件汇总
往复式压缩机主要部件_往复式压缩机优缺点
电视信号传输系统及优劣选择
队列与C++中的queue详解
ATOS比例控制阀放大器QVHMZO-A介绍
Vishay推出新型第三代650 V SiC肖特基二极管，提升开关电源设计能效和可靠性
NI PXI缩短射频功率放大器的特征化时间
自动驾驶中的激光雷达目标检测的原理和数据特点
LED驱动芯片WT0031概述及功能特点
火花塞型号对照表_汽车火花塞型号一览表如何保养火花塞？
2018财年英飞凌营收达75.99亿欧元，营业利润13.53亿欧元
威联通科技宣布推出新型大容量机架式QuTS hero NAS
发光二极管的主要参数
轻流第三届无代码探索者大会落幕
数据平台正在成为一种新模式为企业开辟了一条崭新的发展之路
苹果最强最贵Mac Pro诞生 iPadOS和iOS分家
PCB自动光学检测的自动选取定位核满足实时性
TDK | 家电解决方案：主要家电