重庆哪里有做网络推广,杭州优化公司哪家好,网站建设设计设计,前端工程师招聘1 std::queue 概述
std::queue 是 C 标准模板库#xff08;STL#xff09;中的一种容器适配器#xff0c;它提供了队列#xff08;Queue#xff09;这种数据结构的功能。队列是一种特殊的线性表#xff0c;它只允许在表的前端#xff08;front#xff09;进行删除操作…1 std::queue 概述
std::queue 是 C 标准模板库STL中的一种容器适配器它提供了队列Queue这种数据结构的功能。队列是一种特殊的线性表它只允许在表的前端front进行删除操作而在表的后端rear进行插入操作。因此队列具有先进先出FIFO的特性。
1.1 std::queue 的内部实现
std::queue 的内部实现通常基于其他容器如 std::deque双端队列或 std::list。这种实现方式使得 std::queue 能够提供队列Queue这种数据结构的功能即只允许在表的前端front进行删除操作而在表的后端rear进行插入操作从而实现先进先出FIFO的特性。
1基于 std::deque 的实现
当 std::queue 基于 std::deque 实现时其内部存储机制利用了 deque 的双向操作特性。deque 允许在其头部和尾部都进行高效的插入和删除操作这使得它非常适合作为队列的底层容器。 在这种实现中std::queue 的 push 操作会将元素添加到 deque 的尾部而 pop 操作会从 deque 的头部删除元素。front 和 back 操作则分别返回 deque 的头部和尾部元素。 由于 deque 提供了直接访问其头部和尾部的接口因此这种实现方式通常具有较高的性能。
2基于 std::list 的实现
当 std::queue 基于 std::list 实现时其内部存储机制利用了 list 的双向链表结构。虽然 list 在任意位置进行插入和删除操作都较为高效但作为队列使用时主要的操作还是集中在头部和尾部。 在这种实现中std::queue 的 push 操作会将元素添加到 list 的尾部而 pop 操作会从 list 的头部删除元素。与基于 deque 的实现类似front 和 back 操作分别返回 list 的头部和尾部元素。 然而需要注意的是虽然 list 允许在任意位置进行插入和删除操作但在作为队列使用时其性能可能不如基于 deque 的实现因为 deque 在头部和尾部的操作通常更加高效。
注意没有明确指定 std::queue 的底层容器类型时它默认使用 std::deque
1.2 std::queue 的性能特点
std::queue 的性能特点主要源于其内部使用的容器类型通常是 std::deque 或 std::list。
1基于std::deque的性能特点
当 std::queue 基于 std::deque 实现时它通常能够展现出非常优秀的性能。这是因为 std::deque 是一个双向队列它允许在两端进行高效的插入和删除操作。因此在 std::queue 中使用 push 在尾部插入元素和使用 pop 在头部删除元素的操作通常都非常快。
此外std::deque 通常是以固定大小的块来存储元素这种存储方式减少了内存分配和释放的次数从而提高了性能。这也使得 std::queue 在处理大量元素时能够保持稳定的性能。
2基于std::list的性能特点
虽然 std::queue 也可以基于 std::list 实现但相比基于 std::deque 的实现其性能可能稍逊一筹。std::list 是一个双向链表虽然它在任意位置插入和删除元素都比较高效但相对于 std::deque它在头部和尾部进行操作的性能可能稍差。
具体来说std::list 中的元素是分散在内存中的这可能导致缓存不命中cache misses的问题从而降低性能。此外由于链表需要维护指针或迭代器来跟踪元素的位置这也可能增加一些额外的开销。
3时间复杂度
对于 std::queue 的基本操作如 push、pop、front 和 back其时间复杂度通常都是常数时间 O(1)。这意味着无论队列中有多少元素这些操作所需的时间都是固定的。
然而需要注意的是虽然这些基本操作的时间复杂度是常数但在实际应用中性能还可能受到其他因素的影响如内存分配、缓存行为以及并发访问等。
4实际应用中的考虑
在选择使用 std::queue 时通常不需要过多关心其底层实现和性能特点。因为标准库已经提供了优化过的实现并且在大多数情况下都能够满足性能需求。然而在一些对性能要求非常高的场景下可能需要考虑使用更底层的容器或自定义数据结构来替代 std::queue。
2 std::queue 的基本使用
2.1 std::queue 的声明与初始化
声明
首先需要包含queue头文件以使用 std::queue
#include queue
#include string // 声明一个整数类型的 queue
std::queueint vals;// 声明一个字符串类型 queue
std::queuestd::string strs;// 声明一个自定义类型的 queue
struct MyStruct
{int id;std::string name;
};std::queueMyStruct myStructs;初始化
可以使用多种方法来初始化 std::queue。
1默认初始化
如果不提供任何参数std::queue 会使用默认构造函数进行初始化。这意味着它会使用其底层容器默认为 std::deque的默认构造函数。
std::queueint q;2使用 std::deque 进行初始化
虽然 std::deque 不支持初始化列表但可以使用以初始化列表初始化的 std::dequeint 来进行初始化。
std::queueint q(std::dequeint{1, 2, 3, 4, 5}); // 使用 std::dequeint 初始化队列 q3复制另一个队列
可以使用另一个 std::queue 的副本来初始化一个新的队列。
std::queueint q1(std::dequeint{1, 2, 3, 4, 5});
std::queueint q2(q1); // 使用q1的内容初始化q24移动另一个队列
C11 及更高版本还支持移动语义这意味着可以转移另一个队列的内容来初始化新的队列而不需要复制元素。
std::queueint q1 {1, 2, 3, 4, 5};
std::queueint q2(std::move(q1)); // 使用 q1 的内容通过移动初始化 q2q1 现在为空5指定底层容器
虽然不常见但可以通过指定底层容器来初始化 std::queue。这要求提供一个容器对象该对象将用作队列的底层存储。
std::listint l {1, 2, 3, 4, 5};
std::queueint, std::listint q(l); // 使用 list l 作为底层容器初始化队列 q2.2 std::queue 的大小与容量
1大小size
std::queue 的大小是指队列中当前存储的元素数量。可以使用 std::queue 的 size 成员函数来获取队列的大小。例如
std::queueint q;
q.push(1);
q.push(2);
q.push(3); std::size_t size q.size(); // size 现在是 3因为队列中有 3 个元素这个例子向队列中添加了三个元素并使用 size 成员函数获取队列的大小。
2容量capacity
与 std::vector 或 std::deque 不同std::queue 没有直接提供获取其“容量”的成员函数。容量通常指的是容器在不进行内存重新分配的情况下可以容纳的元素数量。由于 std::queue 的设计是为了提供队列操作的接口并且隐藏了其底层容器的实现细节因此它并不直接暴露底层容器的容量信息。
如果需要了解底层容器的容量信息可能需要直接操作底层容器但这通常不是使用 std::queue 的推荐做法因为它违反了队列的抽象和封装原则。
2.3 std::queue 的构造函数与析构函数
1构造函数
std::queue 提供了多个构造函数以便在不同的情况下灵活地初始化队列。以下是一些主要的构造函数
默认构造函数
std::queueType q;此构造函数创建一个空的队列其底层容器使用默认构造函数进行初始化。这里的 Type 是队列中元素的类型。
拷贝构造函数
std::queueType q1(q2);此构造函数使用另一个队列 q2 的内容来初始化新的队列 q1。它复制 q2 中的所有元素到 q1 中。
移动构造函数C11 及更高版本
std::queueType q1(std::move(q2));此构造函数通过移动另一个队列 q2 的内容来初始化新的队列 q1。这意味着 q2 在移动操作后不再包含其原始元素这些元素的所有权现在属于 q1。使用移动构造函数通常比使用拷贝构造函数更高效因为它可以避免不必要的元素复制。
2析构函数
当 std::queue 对象的生命周期结束时其析构函数会被自动调用。析构函数负责清理队列所占用的资源包括释放底层容器的内存。注意不需要显式地调用析构函数因为 C 的自动存储期管理会处理这些细节。
例如
{ std::queueint q; // ... 在这里使用队列 ...
} // 在这里当 q 离开其作用域时其析构函数会自动被调用在上面的代码中当 q 离开其作用域时其析构函数会被自动调用从而释放队列所占用的资源。
3 std::queue 的元素操作
3.1 入队列操作push
入队列操作使用 push 成员函数它接受一个参数即要添加到队列顶的元素。例如
std::queueint q;
q.push(1); // 将整数 1 压入队列中
q.push(2); // 将整数 2 压入队列中这个例子创建了一个 int 类型的队列 q并使用 push 函数将两个整数依次压入队列中。
3.2 出队列操作pop
出队列操作使用 pop 成员函数它移除队列顶的元素但不返回该元素的值。例如
std::queueint q;
q.push(1);
q.push(2);
q.pop(); // 移除队列顶元素 1但不返回它这个例子创建了一个队列 q 并压入两个整数。然后使用 pop 函数移除了队列头部的元素 1。
3.3 查看队列头部元素front
查看队列头部元素使用 front 成员函数它返回队列头部元素的引用但不移除该元素。例如
std::queueint q;
q.push(1);
q.push(2);
int frontElement q.front(); // 获取队列头部元素此时 frontElement 的值为 1这个例子创建了一个队列 q 并压入两个整数。然后使用 front 函数获取了队列头部的元素并将其值存储在 frontElement 变量中。
3.4 查看队列尾部元素back
查看队列尾部元素使用 back 成员函数它返回队列尾部元素的引用但不移除该元素。例如
std::queueint q;
q.push(1);
q.push(2);
int backElement q.back(); // 获取队列尾部元素此时 backElement 的值为 2这个例子创建了一个队列 q 并压入两个整数。然后使用 back 函数获取了队列尾部的元素并将其值存储在 backElement 变量中。
3.5 检查队列是否为空empty
检查队列是否为空使用 empty 成员函数如果队列为空则返回 true否则返回 false。例如
std::queueint q;
bool isEmpty q.empty(); // isEmpty 的值为 true因为队列是空的
q.push(1);
isEmpty q.empty(); // isEmpty 的值为 false因为队列不再为空这个例子首先创建了一个空的队列 q并使用 empty 函数检查其是否为空。然后压入一个整数并再次检查队列是否为空。
3.6 队列的交换swap
可以使用 swap 成员函数来交换两个队列的内容。例如
std::queueint q1, q2;
q1.push(1);
q1.push(2);
q2.push(3);
q2.push(4); q1.swap(q2); // 交换 q1 和 q2 的内容在这个例子中q1 原本包含元素 1 和 2q2 包含元素 3 和 4。调用 swap 后q1 将包含元素 3 和 4而 q2 将包含元素 1 和 2。
3.6 底层容器的访问
虽然直接访问 std::queue 的底层容器通常是不推荐的因为它破坏了队列的封装性但 STL 仍然提供了某种程度的访问能力。可以使用 _Get_container 成员函数来获取底层容器的引用。注意应该非常小心地使用这个功能并只在确实需要时才使用它。
std::queueint q;
auto underlyingDeque q._Get_container(); // 获取底层 deque 的引用注意这通常不是好的做法4 std::queue 的删除操作
std::queue 是一个后进先出FIFO的数据结构其设计初衷是提供基本的队列操作如 push压入元素、pop弹出元素、top查看队列顶元素等。然而std::queue 并没有直接提供删除队列中特定元素的操作这是因为它保持了队列的简单性和一致性。
如果需要删除队列中的特定元素那么可能需要考虑其他的数据结构如 std::deque 或 std::list它们提供了更多的元素操作功能。但如果仍然想要使用 std::queue 并删除其中的元素那么可以通过以下方式间接实现
1弹出元素直到找到并删除目标元素
可以通过连续调用 pop 函数直到找到并删除目标元素。但是这种方法会破坏队列的结构因为它会移除队列顶的所有元素直到找到目标元素为止。这通常不是推荐的做法因为它违反了队列的 FIFO 原则。
std::queueint q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);std::queueint qTmp;int target 3;
bool found false;
while (!q.empty()) {int front q.front();q.pop();if (front ! target) {qTmp.push(front); // 将非目标元素重新压入队列中 }
}q.swap(qTmp);这个例子试图删除值为 3 的元素。通过循环不断地从队列顶弹出元素检查它是否是想要删除的目标如果不是则将其重新压入备用队列中。这种方法效率很低特别是当队列很大且目标元素靠近队列底时。
2使用其他数据结构辅助
另一种方法是使用一个辅助的数据结构如 std::vector 或 std::deque来存储队列中的元素然后在这个辅助数据结构中删除目标元素最后再将辅助数据结构中的元素重新压入队列中。这种方法同样会破坏队列的结构并且效率也不高。
3避免需要删除操作
最好的方法是避免在 std::queue 中进行删除操作。在设计程序时尽量确保你不需要从队列中删除特定的元素。如果确实需要这种功能那么可能需要考虑使用其他更适合的数据结构。
