当前位置：首页 > article >正文

简述C++STL-队列

article 2024/11/24 14:52:48

单项队列queue

queue容器不支持迭代器。

构造函数

常用操作

其它操作

双向队列deque

优先队列priority_queue

结语：

单项队列queue

queue容器的逻辑结构是队列，物理结构可以是数组或链表，主要用于多线程之间的数据共享。

包含头文件： #include<queue>

queue类模板的声明：

template <class T, class _Container = deque<T>>

class queue{

……

}

第一个模板参数T：元素的数据类型。

第二个模板参数_Container：底层容器的类型，缺省是std::deque，可以用std::list，还可以用自定义的类模板。

queue容器不支持迭代器。

队列是一种遵循先进先出（FIFO）原则的数据结构，其主要操作是在队尾进行入队（push）操作以添加元素，在队首进行出队（pop）操作以移除元素，以及获取队首元素（front）和判断队列是否为空（empty）等操作。

这些操作都是围绕着队列的两端进行的，重点在于按照元素进入队列的先后顺序来处理元素，而不是对队列中的所有元素进行遍历等操作，这与迭代器通常用于遍历容器中所有元素的使用场景不太相符。

在 C++ 标准库中，std::queue是一个容器适配器，它本身并不直接管理内存存储数据，而是通过适配其他底层容器（如std::deque、std::list等）来实现队列的功能。这意味着它利用了底层容器的存储和操作特性，同时为用户提供了统一的队列操作接口。

构造函数

1）queue(); // 创建一个空的队列。

2）queue(const queue<T>& q); // 拷贝构造函数。

3）queue(queue<T>&& q); // 移动构造函数（C++11标准）。

析构函数~queue()释放内存空间。

常用操作

1）void push(const T& value); // 元素入队。

2）void emplace(…); // 元素入队，…用于构造元素。C++11

3）size_t size() const; // 返回队列中元素的个数。

4）bool empty() const; // 判断队列是否为空。

5）T &front(); // 返回队头元素。

6）const T &front(); // 返回队头元素，只读。

7）T &back(); // 返回队尾元素。

8）const T &back(); // 返回队尾元素，只读。

9）void pop(); // 出队，删除队头的元素。

其它操作

1）queue &operator=(const queue<T> &q); // 赋值。

2）void swap(queue<T> &q); // 交换。

3）bool operator == (const queue<T> & q) const; // 重载==操作符。

4）bool operator != (const queue<T> & q) const; // 重载!=操作符。

示例代码如下：

#include <iostream>
#include <queue>
#include <deque>

using  namespace std;

class girl       // 类。
{
public:
	int m_bh;             // 编号。
	string m_name;  // 姓名。
	girl(const int& bh, const string& name) : m_bh(bh), m_name(name) {}
};

int main()
{
	
	queue<girl> q;        

	q.push(girl(3, "girl A"));   // 效率不高。
	q.emplace(8, "girl B");     // 效率更高。
	q.push(girl(5, "girl V"));
	q.push(girl(2, "girl Z"));

	cout << "队列的大小为： " << q.size() << endl;

	while (q.empty() == false)
	{
		cout << "编号：" << q.front().m_bh << "，姓名：" << q.front().m_name << endl;
		q.pop();
		cout << "队列的大小为： " << q.size() << endl;
	}

	if (q.empty())
	{
		cout << "队列为空！" << endl;
	}
}

运行结果：

通过循环pop队头出队，从而队头改变，只需循环打印队头元素即可。

双向队列deque

1）物理结构

deque容器存储数据的空间是多段等长的连续空间构成，各段空间之间并不一定是连续的。

为了管理这些连续空间的分段，deque容器用一个数组存放着各分段的首地址。

通过建立数组，deque容器的分段的连续空间能实现整体连续的效果。

当deque容器在头部或尾部增加元素时，会申请一段新的连续空间，同时在数组中添加指向该空间的指针。

它和vector有很多相似的地方，都是随机迭代器，各种操作也和vector一样；

但是也有很多不同的地方：

存储结构差异：
- std::vector是单一连续的内存空间来存储所有元素，就像一个动态增长的数组。这种存储结构使得它在随机访问时性能非常好，时间复杂度为，但在插入和删除操作（特别是在中间位置）时可能会面临扩容或元素移动等问题，导致性能损耗和迭代器失效。
- std::deque采用分段连续存储的方式，由多个连续的小段内存组成。这使得它既能像数组一样在每个小段内进行快速随机访问，又能像链表一样在两端灵活地进行插入和删除操作。不过，由于其分段结构，在某些操作（如插入、删除等）时的处理相对复杂一些，比如插入操作可能会涉及到分段的重新分配等情况。
插入和删除操作性能特点：
- 在std::vector中，在末尾进行插入（push_back）操作通常性能较好，时间复杂度为（不考虑扩容情况），但在中间位置插入或删除元素时，可能会引起扩容（插入时）或元素移动（插入和删除时），导致性能下降且迭代器失效。
- std::deque在两端（头部和尾部）进行插入和删除操作都具有较好的性能，时间复杂度为，而且不会像vector那样因为扩容而导致整个容器的大规模重排。但在插入或删除操作涉及到分段的重新分配等情况时，性能也会受到一定影响。
内存管理方式不同：
- std::vector在需要扩容时，通常会重新分配一块更大的连续内存空间，将原有的元素复制到新空间中，然后释放旧的内存空间。这种方式在扩容时可能会消耗较多的内存和时间。
- std::deque的内存管理相对复杂一些，它的分段连续存储结构使得它在增加或减少元素时，主要是对各个分段进行操作，比如添加或删除分段、调整分段内的元素等，不需要像vector那样进行大规模的内存重分配。
适用场景不同：
- std::vector更适合于需要频繁进行随机访问，且插入和删除操作主要集中在末尾的场景。例如，存储一系列按顺序读取的数据，且偶尔在末尾添加新数据的情况。
- std::deque则适用于需要两端操作灵活性（如在两端频繁插入和删除元素）以及一定随机访问能力的场景。比如在实现滑动窗口算法时，新数据从一端进入，旧数据从另一端离开，同时还可能需要随机访问窗口内的元素，这种情况下std::deque就比vector更合适。

总的来说就是deque:

提高了在两端插入和删除元素的效率，扩展空间的时候，不需要拷贝以前的元素。
在中间插入和删除元素的效率比vector更糟糕。
随机访问的效率比vector容器略低。

优先队列priority_queue

优先级队列相当于一个有权值的单向队列queue，在这个队列中，所有元素是按照优先级排列的。

它也是容器适配器，底层容器可以用deque和list。也不支持迭代器。

priority_queue的默认底层容器通常基于二叉堆来实现，具体来说，对于存储基本数据类型（如整数、浮点数等），一般是采用最大堆或最小堆的形式（取决于数据类型和默认比较规则）。例如，对于整数类型，默认是最大堆，即较大的整数具有更高的优先级。

priority_queue（优先队列）相对于queue（普通队列）主要多了基于优先级的排序功能，各种操作与queue容器相同。

示例代码：

#include <iostream>
#include <queue>
#include <deque>

using  namespace std;


int main()
{
	
	priority_queue<char> q;

	q.push('A');   // 效率不高。
	q.emplace('P');     // 效率更高。
	q.push('Z');
	q.push('H');

	cout << "队列的大小为： " << q.size() << endl;

	while (q.empty() == false)
	{
		cout << q.top() << endl;
		q.pop();
		cout << "队列的大小为： " << q.size() << endl;
	}

	if (q.empty())
	{
		cout << "队列为空！" << endl;
	}
}

运行结果：