【C++】stack和queue的模拟实现

个人主页<—请点击
C++专栏<—请点击

一、stack和queue的模拟实现

1.1 容器适配器

在C++标准库（STL）中，容器适配器（Container Adaptors）是一种特殊的容器，它们基于现有的STL容器（如vector、deque、list等）进行封装，提供了一种受限的、特定用途的接口。容器适配器本身并不直接管理内存或存储元素，而是依赖底层容器来实现功能，并通过限制或扩展接口来满足特定的数据结构需求。

容器适配器的核心特点：

• 基于现有容器：适配器（如stack、queue、priority_queue）通过组合一个底层容器（如deque、vector）来实现功能。
• 接口受限：仅暴露特定操作（如stack只允许一端操作（后进先出），queue是先进先出）。
• 不提供迭代器：无法直接遍历适配器中的元素（例如不能对stack用for(auto it : s)）。
• 复用底层容器的实现：内存管理、元素存储等均由底层容器处理。

1.2 stack的模拟实现

stack容器的基本使用方法是push(尾插)、pop(尾删)、size()、empty()、top()。所以它的底层容器都必须能够使用这些方法，其中vector就是符合的，但STL库中使用了deque，这个容器也能完全符合特点，我们稍后作为了解。

模拟实现代码：

namespace ST
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_back();
		}

		bool empty() const
		{
			return _con.empty();
		}

		size_t size() const
		{
			return _con.size();
		}

		T& top()
		{
			return _con.back();
		}

		const T& top() const
		{
			return _con.back();
		}
	private:
		Container _con;
	};
}

由于stack所有的接口里面的功能实现都是使用底层容器的，所以直接调用底层容器的成员函数就好了。

测试：

void test1()
{
	ST::stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.push(5);
	while (st.size())
	{
		cout << st.top() << " ";
		st.pop();
	}
}

1.3 queue的模拟实现

queue的基本使用方法是push(尾插)、pop(头删)、front()、back()、size()、empty()。其中它所需求的这些功能list是具备的，但STL库中依旧使用了deque。

模拟实现：

namespace QUE
{
	template<class T,class Container = deque<T>>
	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();
		}

		T& front()
		{
			return _con.front();
		}

		const T& front() const
		{
			return _con.front();
		}

		T& back()
		{
			return _con.back();
		}

		const T& back() const
		{
			return _con.back();
		}

	private:
		Container _con;
	};
}

测试：

void test2()
{
	QUE::queue<int> q;
	q.push(1);
	q.push(2);
	q.pop();
	cout << q.front() << " ";
	q.push(3);
	q.push(4);
	q.push(5);
	while (q.size())
	{
		cout << q.front() << " ";
		q.pop();
	}
}

1.4 deque的了解认识

deque（双端队列，全称double-ended queue）是C++标准模板库(STL)中的一个重要容器，它结合了vector和list的优点，提供了高效的双端插入和删除操作。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，重担落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

协作关系：
1、定位元素：

• 通过node找到当前块在中央映射表中的指针，再结合first/last确定块的范围。
• cur在[first, last)范围内移动，访问具体元素。

2、跨块跳转：

• 当cur移动到last时（如++iter到块末尾），迭代器会：
• 通过node找到下一个块的指针
• 更新first/last为新块的边界
• 将cur指向新块的起始位置（first）

3、反向移动：

• 当cur移动到first之前时（如--iter到块开头），迭代器会：
• 通过node找到上一个块的指针
• 更新first/last
• 将cur指向上一块的末尾（last - 1）

1.5 deque的优缺点

与vector比较，deque的优势：头删时不需要搬移元素，在扩容时也不需要搬移大量元素，效率比vector高。
与list比较，deque的优势：其底层是连续空间，空间利用率比较高，不需要存储额外字段。

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

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

stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作；在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。可以说stack和queue完美利用了deque的优点，并且完美避开了它的缺陷。

总结：
以上就是本期博客分享的全部内容啦！如果觉得文章还不错的话可以三连支持一下，你的支持就是我前进最大的动力！
技术的探索永无止境! 道阻且长，行则将至！后续我会给大家带来更多优质博客内容，欢迎关注我的CSDN账号，我们一同成长！
(～￣▽￣)～