C++stack,queue底层实现以及deque的详细介绍

---

前言

在本篇文章中，我们将会学到stack,queue的底层实现，我们通过本篇的学习，我们会发现，栈和队列的实现和vector,list等容器的实现会有很大差异。我们实现栈和队列是通过一种叫容器适配器的东西实现的。我们还将会学到deque,这是一种将list和vector结合的一种容器。我们来详细看一看吧！！！🌟🌟🌟

一、容器适配器

在介绍容器适配器之前，我们来想一下stack应该如何实现呢？？

我们很清楚，栈是一种后进先出的结构，只能在一端进行数据的插入删除。
在c语言我们学习过，stack既可以用顺序表来实现，又可以用链表实现。
那么我们在C++中依然可以采用相同的方式来实现链式栈和顺序栈。

但是，我们发现在实现stack的接口中，很多都与顺序表的实现结构相似。
那麽我们把vector的一些接口进行封装，修改修改不就是我们stack的结构吗？？

在C++官方库中，确实就是采用这种方法进行实现的。我们把这个叫做容器适配器

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

队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

容器适配器是C++标准库中的一种数据结构，它可以将不同类型的容器（如vector、list、deque等）转换为另一种类型的容器。本质上，容器适配器是一种机制，能使某种容器的行为看起来像另外一种容器。这种转换提供了一种简单的方式来重新组织和访问数据，同时隐藏了底层容器的实现细节。容器适配器通常用于解决特定的问题或满足特定的需求。

二、stack的实现

我们现在已经知道实现stack采用容器适配器来实现，我们想实现一个链式栈，就采用list进行适配，我们想实现一个顺序栈，就采用vector进行适配。

vector适配缺点：容易造成空间浪费
list适配缺点：内存命中率较低

有没有一种两者兼有的结构呢？？
我们来看一下stack库里的是如何实现的！！！

我们发现在进行适配时，默认采用了deque这个容器。

这其实是一个双端队列。尾插尾删效率很高，对于空间的浪费也没有那麽大，内存命中率也可以。我们先用这个实现一下，在后面我们再来详细看一下

template<class T,class con=deque<T>>
class stack
{
public:
	void push(const T&val)
	{
		_con.push_back(val);
	}
	void pop()
	{
		_con.pop_back();
	}
	size_t size()
	{
		return _con.size();
	}
	T& top()
	{
		return _con.back();
	}
	bool empty()
	{
		return _con.empty();
	}
private:
	con _con;
};

三、queue的实现

对于queue的实现我们想一下是否可以用vector和list实现

queue是先进先出，尾插头删，对于vector我们在库里面并没有头删的操作。
我们也可以用自己模拟实现的vector实现一个头删，但是我们知道对于头删，效率太低了

⭐️⭐️注意一下：适配器并不是一定要适配库里的，也可以适配自己模拟实现的，只要可以实现对应的需求就可以
对于list我们就可以了，但是list也有对应的缺陷，我们看一下库里的实现

我们发现依然默认采用deque的方式，我们同样的先用这个实现以下

	template<class T, class con = deque<T>>
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_front();
		}
		size_t size()
		{
			return _con.size();
		}
		T& back()
		{
			return _con.back();
		}
		T& front()
		{
			return _con.front();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		con _con;
	};

四、deque的介绍

stack和queue都是默认采用deque实现的，我们接下来看一下这个容器为什么比vector和list更适合适配。

deque是一个双端队列：两端开口，都可以进行插入删除，时间复杂度为O（1）。

我们来看一下它的底层

deque整个的物理空间并不是连续的，而是由一段段连续的物理空间结合而成，类似于一个二维数组。
我么给这一段段空间编号，方便接下来叙述。

我们来看一下头部插入和尾部插入

🔱🔱头插
✨ ✨ ✨ ✨ 如果一号空间不满，我们就直接在前面进行插入，假设我们插入1

✨ ✨ ✨ ✨ 如果一号空间已经满了，我们需要再开一块空间，把这块空间起始位置放在中控位置，再在新开的这块空间进行插入。
如果中控的位置也满了，就扩大中控位置，拷贝指针。

🔱🔱尾插
✨ ✨ ✨ ✨ 尾插也是同样的道理，尾部元素不满，继续插入。满了就再开一块空间继续插入

双端队列底层是一段假想的连续空间，实际是分段连续的，为了维护整体连续以及随机访问的假象，落在了deque迭代器上，迭代器设计就很复杂了

其中对于每段空间来说：
💗💗cur指向buff的某个位置
💗💗first指向buff的开始位置
💗💗last指向buff的结束位置
💗💗node指向存储buff中控位置

对于中控：
💗💗start指向第一个buff，cur指向这个buff第一个位置元素
💗💗finish指向最后一个buff，cur指向这个buff最后一个位置元素的下一个位置

我们可以看到deque有很多优势，头部插入删除，不需要挪动数据，弥补了vector的缺陷。同时底层空间是连续的，弥补了list的缺点，缓存利用率高。

那我们是不是可以考虑废除vector和list,z之后的学习都采用deque的结构呢？？
显然是不行的，我们在数据结构已经学过了，就说明有存在的道理

deque有没有什么缺点呢？？

🎁🎁下标的随机访问
既然deque兼备vector和list的特性，肯定具有下标的随机访问。
我们如果想要在deque中进行下标的随机访问，怎末做呢？？
例如：deque中一共有100个元素，假设每个空间大小固定，都是10。我们想要访问第55个元素的位置。我们可以先用55/10，得到结果5，我们就知道我们要找的在第5块空间中，再用55%10，得到结果5，我们就可以找到这个位置进行访问了。
🎁🎁任意位置的插入删除
我们来看一这种场景，deque中有100个元素，我们想要在地55个元素的位置进行插入操作，我们如果每个空间大小固定，移动起来数据就相当麻烦。
那如果我们在这个空间的基础上进行扩大，不固定空间大小不就行了，这样确实可以实现，但是我们的下标随机访问就会收到影响。

我们只能空间时间选择一个，这就像鱼和熊掌不可兼得。
因此在实践中，deque的应用场景并不多，目前我们能看到的一个应用就是，STL用它作为stack和queue的底层数据结构。

既然deque有这麽大的缺点，我们为什么还要让它当作stack和queue的默认容器呢？

stack是一种后进先出的特殊线性数据结构，我们只要保证有尾插和尾删的相关操作就可以，比如vector，list都可以实现。queue是一种先进先出的特殊线性数据结构，只要保证有头删，尾插的相关操作就可以，比如list.

但是我们选择deque作为默认的容器：因为stack和queue完美的避开了这两大缺陷
🌝🌝stack和queue不需要随机访问，只能访问固定位置的数据。

🌝🌝stack在扩容时，deque比vector效率高，不需要挪动大量数据。queue元素增长时，deque效率高，内存使用率高。

总结

以上就是今天要讲的内容，本文仅仅详细介绍了C++stack和queue的模拟实现,以及deque的相关实现。希望对大家的学习有所帮助，仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘