C++总结(8)：STL容器适配器之stack、queue、priority_queue详解

容器适配器(Container Adapters)是C++标准库中的一种数据结构，用于提供特定接口以便于将不同类型的容器以一种统一的方式使用。它们是标准库的一部分，提供了一种通用的方式来操作底层容器，无论是栈(stack)、队列(queue)、还是优先队列(priority_queue)。

1 stack

栈(Stacks)是一种容器适配器，采用后进先出(LIFO)工作方式。

常用方法

• empty():返回栈是否为空
• size():返回栈的大小
• top():返回栈顶元素的引用
• push(g):在栈顶添加元素g(接受一个已构造的元素作为参数，并将该元素的副本推入栈中)
• emplace(g):在栈顶添加元素g(接受构造元素所需的参数，并在栈内直接构造元素，而不需要进行副本构造)
• pop():删除栈中最近插入的元素

下面来看一个例子：

#include 
#include 
using namespace std;
int main() {
	stack stack;
	stack.push(21);
	stack.push(22);
	stack.push(24);
	stack.push(25);
	int num=0;
	stack.push(num);
	stack.pop();
	stack.pop();
	stack.pop();

	while (!stack.empty()) {
		cout << stack.top() <<" "; //22 21
		stack.pop();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2 queue

队列(queues)是一种容器适配器，采用先进先出(FIFO)的工作方式。直接来看一个例子：

#include 
#include 

using namespace std;


void showq(queue gq)
{
	queue g = gq;
	while (!g.empty()) {
		cout << ' ' << g.front();
		g.pop();
	}
	cout << '\n';
}

int main()
{
	queue gquiz;
	gquiz.push(10);
	gquiz.push(20);
	gquiz.push(30);

	cout << "The queue gquiz is : ";
	showq(gquiz);  //10 20 30

	cout << "\ngquiz.size() : " << gquiz.size();  //3
	cout << "\ngquiz.front() : " << gquiz.front();  //10
	cout << "\ngquiz.back() : " << gquiz.back();  //30

	cout << "\ngquiz.pop() : ";  //20 30
	gquiz.pop();
	showq(gquiz);

	return 0;
}
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

方法

3 priority_queue

优先队列(priority queue)是一种特殊设计的容器适配器，队列中的元素是按递增/递减排列的，默认情况下优先队列被实现为最大堆(递减排列)。下面来看一个例子：

#include 
#include 
using namespace std;

int main()
{
	int arr[6] = { 10, 2, 4, 8, 6, 9 };

	priority_queue pq; //默认为降序

	for (int i = 0; i < 6; i++) {
		pq.push(arr[i]);
	}

	cout << "Priority Queue: ";
	while (!pq.empty()) {
		cout << pq.top() << ' ';  //10 9 8 6 4 2
		pq.pop();
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

如何创建一个最小堆的优先队列？

默认情况下优先队列被实现为最大堆，我们也可以通过一些选项将其变为最小堆：

priority_queue , greater> gq;
1

• int：存储在优先队列中的元素类型
• vector：用于存储这些元素的内部容器的类型
• greater：自定义比较函数，这个表示最小堆(最小的元素将位于队列的顶部)，它确定了在优先队列内元素的排序方式

在最大堆的情况下，我们不需要指定它们，因为这些参数的默认值已经适用于最大堆。

#include 
#include 
using namespace std;

void showpq(priority_queue, greater > g)
{
	while (!g.empty()) {
		cout << ' ' << g.top();
		g.pop();
	}
	cout << '\n';
}

int main()
{
	int arr[6] = { 10, 2, 4, 8, 6, 9 };
	priority_queue, greater > gquiz(arr, arr + 6);

	cout << "Priority Queue : ";  //2 4 6 8 9 10
	showpq(gquiz);

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法

优先队列操作

我们可以使用使用push()将元素插入优先队列中，使用pop()从优先队列中移除元素，它会移除具有最高优先级的元素。

#include 
#include 
using namespace std;

void showpq(priority_queue gq)
{
	priority_queue g = gq;
	while (!g.empty()) {
		cout << ' ' << g.top();
		g.pop();
	}
	cout << '\n';
}

int main()
{
	priority_queue gquiz;
	gquiz.push(10);
	gquiz.push(30);
	gquiz.push(20);
	gquiz.push(5);
	gquiz.push(1);

	cout << "The priority queue gquiz is : ";
	showpq(gquiz);  //30 20 10 5 1
	cout << "\ngquiz.size() : " <<  gquiz.size();  //5
	cout << "\ngquiz.top() : " <<  gquiz.top();  //30
	cout << "\ngquiz.pop() : ";
	gquiz.pop();
	showpq(gquiz);  //20 10 5 1

	return 0;
}
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

• 我们每次只能访问优先队列的顶端元素，即调用top()

交换优先队列的内容

swap()函数用于交换一个优先队列的内容与另一个相同类型的优先队列，它们可以具有相同或不同的大小。

#include 
using namespace std;

void print(priority_queue pq)
{
	while (!pq.empty()) {
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

int main()
{
	priority_queue pq1;
	priority_queue pq2;

	pq1.push(1);
	pq1.push(2);
	pq1.push(3);
	pq1.push(4);

	pq2.push(3);
	pq2.push(5);
	pq2.push(7);
	pq2.push(9);

	pq1.swap(pq2);

	cout << "Priority Queue 1 = ";
	print(pq1);  //9 7 5 3
	cout << "Priority Queue 2 = ";
	print(pq2);  //4 3 2 1
	return 0;
}
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

优先队列中元素存储的对象类型

priority_queue::value_type 方法是C++ STL中的内置函数，它表示作为优先队列元素存储的对象类型。它充当模板参数的同义词。

#include 
using namespace std;

int main()
{
	priority_queue::value_type AnInt;
	priority_queue::value_type AString;

	priority_queue q1;
	priority_queue q2;

	AnInt = 20;
	cout << "The value_type is AnInt = " << AnInt << endl;  //20
	q1.push(AnInt);
	AnInt = 30;
	q1.push(AnInt);
	cout << "Top element of the integer priority_queue is: " << q1.top() << endl;  //30


	AString = "geek";
	cout << endl << "The value_type is AString = " << AString << endl;  //geek
	q2.push(AString);
	AString = "for";
	q2.push(AString);
	AString = "geeks";
	q2.push(AString);
	cout << "Top element of the string priority_queue is: " << q2.top() << endl;  //geeks

	return 0;
}
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