C++ STL 容器适配器详解：玩转 Stack (后进先出) 与 Queue (先进先出)

1.stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行 元素的插入与提取操作。

2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定 的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下

操作：

empty：判空操作.
back：获取尾部元素操作.
push_back：尾部插入元素操作.
pop_back：尾部删除元素操作.

4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器,默认情况下使用deque。

1.2:stack的使用

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回 stack 中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中的尾部的元素弹出

#include <iostream>
using namespace std;
#include <stack>
int main()
{
	stack<int> st1;
	st1.push(1);
	st1.push(2);
	st1.push(3);
	st1.push(4);
	while (!st1.empty())
	{
		cout<<st1.top()<< " ";
		st1.pop();
	}
	return 0;
}

2:queue的介绍与使用

2.1:queue的介绍

队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一段插入元素,另一端提取元素.
队列作为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问元素.元素从队尾入队列,从队头出队列.
底层容器可以是标准容器类模版之一,也可以是其他专门设计的容器类.该底层容器至少支持以下操作.
标准容器类deque和list满足了这些要求.默认情况下,如果没有为deque实例化指定容器类,则使用标准容器deque.

empty:检测队列是否为空.
size:返回队列中有效元素的个数.
front:返回队头元素的引用.
back:返回队尾元素的引用.
push_back:在队列尾部入队列.
pop_front:在队列头部出队列.

2.2:queue的使用

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回 true ，否则返回 false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素 val 入队列
pop()	将队头元素出队列

#include <iostream>
using namespace std;
#include <stack>
#include <queue>
int main()
{
	queue<int> q1;
	q1.push(1);
	q1.push(2);
	q1.push(3);
	q1.push(4);
	q1.push(5);
	while (!q1.empty())
	{
		cout << q1.front()<< " ";
		cout << q1.back() << endl;
		q1.pop();
	}
	return 0;
}

3:容器适配器

3.1:容器适配器的概念

概念:适配器是一种设计模式(设计模式是一套被反复使用的、多人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另一个接口.

3.2:STL标准库中stack和queue底层结构

虽然stack和queue也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL和stack和queue默认使用deque.

3.3:deque的缺陷

deque不适合遍历,因为在遍历的时候,deque的迭代器需要频繁地去检测是否移动到某段小空间的边界,导致了其效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下考虑vector和list,deque的应用并不多,而目前能看到的一个应用是STL用其作为stack和queue的底层数据结构.

3.4:为什么选择deque作为stack和queue的底层默认容器

stack是一种先进后出的特殊线性结构,因此只要具有push_back和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以.queue是先进先出的特殊线性结构,只要具有push_back()和pop_front()操作的线性结构,都可以作为queue的底层容器,比如list.但是STL中对stack和queue默认使用deque作为其底层容器,主要是因为:

stack和queue不需要进行遍历(因为stack和queue没有迭代器),只要在固定的一端或者两端进行操作.
在stack元素增长的时候,deque比vector的效率高(扩容时不需要搬移大量数据);queue的元素增长时,deque不仅效率高,而且内存使用率高.

4:priority_queue的介绍与使用

4.1:介绍

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
优先级队列类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(位于堆顶的元素)
优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。

4.2:使用

优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中的元素构造成了堆的结构,因此priority_queue就是堆(完全二叉树),所有需要使用堆的位置,都可以考虑使用priority_queue.

PS:默认情况下priority_queue为建立大堆.

函数声明	接口说明
priority_queue/priority_queue(first,last)	构造一个空的优先级队列
empty()	检测优先级队列是否为空,是的话返回true,否则返回false
top()	返回优先级队列中最大(最小元素),即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素,即堆顶元素

#include <iostream>
using namespace std;
#include <stack>
#include <queue>
int main()
{
	//默认建立的是大堆,并且默认的适配器是vector,仿函数为less<int>
	priority_queue<int> pq;
	pq.push(1);
	pq.push(2);
	pq.push(3);
	pq.push(4);
	pq.push(5);
	cout << "pq1:>";
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
	cout << "pq2:>";
	//小堆---->greater
	priority_queue<int, vector<int>, greater<int>> pq2;
	pq2.push(6);
	pq2.push(5);
	pq2.push(4);
	pq2.push(3);
	pq2.push(2);
	pq2.push(1);
	while (!pq2.empty())
	{
		cout << pq2.top() << " ";
		pq2.pop();
	}
	return 0;
}

4.3:仿函数

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

int main()
{
	//多参数构造函数支持隐式类型转换.
	vector<int> v1 = { 5,3,1,2,8,9,7 };
	//默认排升序----->less<int>
	sort(v1.begin(), v1.end());
	for (auto element : v1)
	{
		cout << element << " ";
	}
	cout << endl;
	//排降序----->greater<int>()----->仿函数
	sort(v1.begin(), v1.end(), greater<int>());
	for (auto element : v1)
	{
		cout << element << " ";
	}
	cout << endl;
	return 0;
}

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

template <class T>
struct Less
{
	bool operator()(const T & x,const T & y)
	{
		return x < y;
	}
};

int Add(int value1,int value2)
{
	return value1 + value2;
}

int main()
{
	Less<int> lessfunc;
	cout << Add(1, 2) << endl;
	cout << lessfunc(1, 2) << endl;
	return 0;
}

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

struct Goods
{
	string _name;//名字
	double _price;//价格
	int _evaluate;//评价

	Goods(const char * str,double price,int evaluate)
		:_name(str)
		,_price(price)
		,_evaluate(evaluate)
	{}
};

struct ComparePriceLess
{
	bool operator()(const Goods & Product1,const Goods & Product2)
	{
		return Product1._price < Product2._price;
	}
};

struct CompareEvaluateLess
{
	bool operator()(const Goods& Product1, const Goods& Product2)
	{
		return Product1._evaluate < Product2._evaluate;
	}
};

int main()
{
	vector<Goods> v1 = { {"苹果",85.0,90},{"葡萄",89.0,91},{"橘子",88.0,95} ,{"西瓜",86.5,92} };
	//匿名对象
	sort(v1.begin(), v1.end(), ComparePriceLess());
	for (auto& element : v1)
	{
		cout << element._name << " " << element._price << " " << element._evaluate << endl;
	}
	return 0;
}

亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责