【C++STL】入门不迷路：容器适配器 + deque+stack/queue 使用 + 模拟实现指南！

前言：在上一篇文章中我们探讨了list的模拟实现，本篇将继续学习另外两种重要容器——栈和队列。虽然在之前学习C语言的时候中已经接触过stack(栈)和queue(队列)的概念，但今天我们将以C++的全新视角重新认识这些数据结构。

一、stack和queue的使用

1.1 stack的使用

在这里插入图片描述

栈操作接口说明表：

注：pop() 通常不返回被删除的元素，若需获取栈顶元素需先调用top()。

代码示例：

#include<stack>
#include<iostream>
using namespace std;
void test_stack()
{
	stack<int> st;
	st.push(1);//入栈
	st.push(2);
	st.push(3);
	st.push(4);
	st.push(5);
	st.top() = 50;//对栈顶做修改
	int size=st.size();//返回栈中的元素个数
	//后进先出
	while (!st.empty())//判断栈是否为空
	{
		cout << st.top() << " ";//取栈顶元素
		st.pop();//出栈
	}
	cout << endl;
	//注意代码到这里栈就已经为空了 就不能进行取栈顶，和出栈操作
	//st.top();
	//st.pop();
}

在这里插入图片描述

1.2 queue的使用

在这里插入图片描述

队列操作函数说明

注意事项：

• 使用 front() 或 back() 前应先调用 empty() 检查队列是否为空，避免未定义行为。
• 使用 pop() 前应确保队列不为空，否则可能导致程序崩溃或未定义行为。
• push(val) 操作的时间复杂度通常为 O(1)，具体取决于底层实现。

代码示例：

void test_queue()
{
	queue<int> q;
	q.push(1);//入队列
	q.push(2);
	q.push(3);
	q.push(4);
	q.front() = 10;//修改队头数据
	q.back() = 40;//修改队尾数据
	//先进先出
	while (!q.empty())//判断队列是否为空
	{
		cout << q.front() << " ";//取队头
		q.pop();//出队头
	}
	//同样到这队列为空不能出队列pop或取队列元素 front、back
}

在这里插入图片描述

二、栈和队列的模拟实现

2.1 容器适配器

在模拟实现之前我们先来了解一下什么是容器适配器？

容器适配器是C++标准库中的特殊容器类型，它们通过封装底层容器（如vector、deque或list），提供特定的功能接口。这类适配器本身不直接存储数据，而是通过改造底层容器的接口来满足特定需求。

• stack（栈） 📢 基于顺序容器（如 deque、vector 或 list）封装实现，仅允许在一端进行数据操作，遵循后进先出（LIFO） 原则。默认底层容器为 deque，但可显式指定为 vector 或 list。
• queue（队列） 📢 同样基于顺序容器（如 deque 或 list）封装，限制数据在一端插入（队尾）、另一端删除（队首），遵循 先进先出（FIFO） 原则。默认使用 deque，可替换为 list，但不可使用 vector（因缺乏高效的头部删除操作）。

总结一句话：

容器适配器（如stack和queue）通过封装底层容器（如deque、vector或list）提供特定功能接口，不直接存储数据，而是限制操作方式以实现栈（LIFO）或队列（FIFO）的行为。

2.2 stack的模拟实现

栈的模拟实现底层的容器适配器我们选择vector因为vector的功能能够很好的覆盖栈的功能，所以我们就可以通过调用vector的接口来实现stack栈的接口。

代码示例：

//增加一个模板参数Contianer 来增加容器适配器
//stack和queue默认适配容器时deque所以把Container改成deque就行
//template<class T, class Container=deque<T>>
template<class T, class Container=vector<T>>//还可以使用list去适配
class stack
{
public:
	//push入栈 往栈中入数据
	void push(const T& x)
	{
		_con.push_back(x);
	}
	//出栈 将栈顶的元素弹出
	void pop()
	{
		_con.pop_back();
	}
	//记录整个栈的数据个数 
	size_t size() const
	{
		return _con.size();
	}
	//判断栈是否为空 这个判断是出栈的前提 如果栈为空再出数据就会导致未定义的行为
	bool empty() const
	{
		return _con.empty();
	}
	//取栈顶元素 返回的是栈顶的引用 
	const T& top() const//只读引用
	{
		return _con.back();
	}

	T& top()//可修改
	{
		return _con.back();
	}

private:
	Container _con;
};

💡 注意： 这样的栈其实本质还是vector只是在外面套了一层栈的壳，实现了一个栈该有的功能，接口使用的还是vector的接口。且这样的类是不需要写构造和析构的，因为这样的类所生成的构造和析构会默认去调用底层适配器(vector)的构造和析构！

2.3 queue的模拟实现

同样队列的实现我们之前在学习数据结构的时候使用的就是链表作为它的底层，所以在这里我们也选择链表作为queue的容器适配器。

//stack和queue默认适配容器时deque所以把Container改成deque就行
//template<class T, class Container=deque<T>>
template<class T, class Container = list<T>>//使用list去适配queue
class queue
{
public:
	//尾插
	void push(const T& x)
	{
		_con.push_back(x);
	}
	//头删
	void pop()
	{
		_con.pop_front();
	}
	//记录队列的数据个数
	size_t size() const
	{
		return _con.size();
	}
	//判断队列是否为空
	bool empty() const
	{
		return _con.empty();
	}

	//取队头数据 只读
	const T& front() const//const对象调用
	{
		return _con.front();
	}
	//可修改 普通对象调用
	T& front()
	{
		return _con.front();
	}
	//返回队尾元素的引用 只读
	const T& back() const//const 对象调用
	{
		return _con.back();
	}
	//可修改 普通对象调用
	T& back()
	{
		return _con.back();
	}
private:
	Container _con;
};

以上就是我们使用两种容器适配器分别来实现了stack和queue，那么标准库中的栈和队列是否就是使用我们示范的vector和list呢？查阅官方文档就能找到答案。

在这里插入图片描述

所以deque到底是一个什么样的容器呢？为什么栈和队列的容器适配器选择的是deque呢？下面就来了解一下deque。

三、deque的简单认识(了解)

3.1 deque的原理介绍

deque(双端队列)： 是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

在这里插入图片描述

紧接着我们来看看deque实现的接口都有哪些：

在这里插入图片描述

通过上面vector🆚list发现：deque同时具备了与vector和list相同的接口，那这就意味着deque同时具备vector和list的功能，这一点是毋庸置疑的。这么强大的deque为什么没有作为我们的常用容器呢？我们再从它的底层结构来认识一下它：

3.2 deque底层结构的认识

在这里插入图片描述

通过deque的底层结构我们看到，deque由一个中控数组作为控制中心分别管理着每个buff数组，而维护这些数组的自然就是deque的迭代器(底层封装了)，迭代器有4个指针前三个指针都去维护buff数组，后面一个node指针指向中控数组的某个元素用于在中控数组间移动。

deque的相关操作：

1. 插入删除数据 👉头插往cur的前面去插入/删除(起始迭代器的cur)，尾插往结尾迭代器的cur的后面去插入/删除，这样才满足数据的连续性也满足双端队列的特征。中间位置的插入删除涉及到数据的挪动效率低下。
2. 迭代器的遍历👉通过node指针(T**)指向中控数组的元素加加可以到下一个元素(数组)，减减可以回到上一个数组，这就实现了迭代器遍历。
3. 元素访问👉deque提供的[ ]可以快速定位到某个下标的元素，具体是node指针定位到是哪个buff然后迭代器的cur指针就去找到该元素，这样的下标访问效率高。

🤔思考一下为什么deque不能替代vector和list？

• deque虽然支持双向操作，但中间插入/删除需要移动大量元素，时间复杂度为O(n)，远不如list的O(1)高效。
• deque分段存储的特性导致元素访问时可能跨内存块，缓存命中率低于vector的连续存储结构，随机访问性能弱于vector。
• deque在头部/尾部插入可能导致内存重新分配，使所有迭代器失效；而list的插入删除不会影响其他元素迭代器，vector仅在扩容时失效。

📢总结一下deque：

1、deque非常适合头尾插入删除，效率高 2、下标随机访问效率也不错，但是大量（100w级以上）访问效率略低于vector 3、中间位置插入删除效率低，要大量挪动数据相比vector和list，优点都不够极致

四、总结

容器适配器： 本质是通过封装底层容器并提供受限接口，实现特定数据结构行为（如栈、队列、优先队列）的类模板。

Stack（栈） 栈是一种 后进先出（LIFO） 的线性数据结构，操作受限，仅允许在栈顶进行插入（push）和删除（pop）。典型应用包括函数调用栈、表达式求值、括号匹配等。

Queue（队列） 队列是一种 先进先出（FIFO） 的线性数据结构，操作在两端进行：队尾插入（push），队头删除（pop）。常见场景如任务调度、缓冲区管理。

对比 顺序：栈逆序处理数据，队列保持输入顺序。 用途：栈适合回溯类问题，队列适合公平性任务调度。

MSTcheng 始终坚持用直观图解 + 实战代码，把复杂技术拆解得明明白白！ 👁️ 【关注】 看普通程序员如何用实用派思路搞定复杂需求 👍【点赞】 给 “不搞虚的” 技术分享多份认可 🔖 【收藏】 把这些 “好用又好懂” 的干货技巧存进你的知识库 💬 【评论】 来唠唠 —— 你踩过最 “离谱” 的技术坑是啥？ 🔄 【转发】把实用技术干货分享给身边有需要的程序员伙伴 技术从无唯一解，让我们一起用最接地气的方式，写出最扎实的代码！ 🚀💻