【C++初阶】容器适配器模拟实现栈和队列（附源码）

aosei

发布于 2024-01-23 14:43:25

1090

发布于 2024-01-23 14:43:25

文章被收录于专栏：csdn-nagiY

一.容器适配器

其实在使用模板时，我们不仅可以使用类模板，还可以使用容器模板，这就是一个容器适配器，我们可任意给模板实例化不同的容器，然后就可以使用容器里的接口。

template<class T,class Containers>

我们知道，栈可以用数组实现也可以用链表实现，以前在C语言那里，如果我们想要两个底层不同的栈，要么写两个栈，要么用typedef，但这做不到自由控制；在C++中，我们可以容器适配器解决这个问题，数组链表秒切换。注意使用的接口必须是你实例化的容器所拥有的，否则会报错。例： vector容器没有头插（push_front）和头删（pop_front）接口 list却有这两个接口，所以在使用时要特别注意。

二.模拟实现stack

库里栈的模板是这样的，这个deque是一个双端队列，它同时拥有vector和list的接口。

上图是栈的接口，都很简单，栈符合先进后出，下面就让我们用容器适配器模拟实现栈吧。

源码

template<class T,class Containers=deque<T>>  //容器适配器
	class stack   //栈
	{
	public:
		void push(const T& val)   //入栈，即尾插
		{
			_con.push_back(val);
		}

		void pop()   //出栈，即尾删
		{
			_con.pop_back();
		}

		const T& top() const  //取栈顶元素
		{
			return _con.back();
		}

		bool empty()
		{
			return _con.size() == 0;
		}

		size_t size() const
		{
			return _con.size();
		}
	private:
		Containers _con;
	};

三.模拟实现queue

队列和栈差不多，但队列是先进先出原则。

源码

template<class T,class Containers=deque<T>>
	class queue   //队列
	{
	public:
		void push(const T&val)   //入队列，即尾插
		{
			_con.push_back(val);
		}

		void pop()   //出队列，即头删
		{
			_con.pop_front();
		}

		T& front()   //取队列的第一个元素
		{
			return _con.front();
		}

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

		bool empty()
		{
			return _con.size() == 0;
		}

		size_t size() const
		{
			return _con.size();
		}
	private:
		Containers _con;
	};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-01-23，如有侵权请联系 cloudcommunity@tencent.com 删除

队列