【C++】STL中stack和queue(适配器版)的模拟实现

06-20 1229阅读

前言：在此之前我们讲到了stack和queue还有deque的常见的使用方法，并且也在数据结构的时候用C语言去实现过栈和队列，今天我们将进一步的用C++去模拟实现stack和queue

💖 博主CSDN主页:卫卫卫的个人主页 💞

👉 专栏分类:高质量Ｃ++学习 👈

💯代码仓库:卫卫周大胖的学习日记💫

💪关注博主和博主一起学习!一起努力！

【C++】STL中stack和queue(适配器版)的模拟实现

目录标题

  • 什么是适配器
  • Stack的模拟实现
    • Stack的基本结构
    • 常见函数的模拟实现
      • 入栈 - push(const T& x)
      • 出栈- pop()
      • 获取栈顶元素 - const T& top()
      • 栈中的元素个数 - size_t size()
      • 判断栈是否为空
      • 整体代码:
      • Queue的模拟实现
        • Queue的基本结构
        • 常见函数的模拟实现
          • 入队列- push(const T& x)
          • 出队列- pop()
          • 获取队头元素- const T& front()
          • 获取队尾元素- const T& back()
          • 获取队列元素个数 - size_t size()
          • 判断队列是否为空 - bool empty()
          • 整体代码

            在讲stack和queue的模拟实现之前我们需要提到一个概念:适配器

            什么是适配器

            适配器是一种设计模式，也是一种编程工具，用于将一个类的接口转换成另一个类的接口。适配器模式允许不兼容的类之间能够协同工作。

            在C++中，适配器是指通过改变容器的接口使其适用于不同的需求。适配器可以封装容器，以提供一种更简单、更有限的功能接口，或者可以通过改变容器的工作方式来满足特定的需求。

            在STL（标准模板库）中，适配器包括以下几种：

            1. 迭代器适配器：用于改变迭代器的行为，如reverse_iterator适配器用于反向遍历一个容器。
            2. 容器适配器：用于改变容器的接口，如stack适配器用于实现堆栈功能。
            3. 函数适配器：用于改变函数的行为，如bind适配器用于绑定函数和参数，生成新的函数对象。

            适配器模式是一种重要的设计模式，它提供了一种解决兼容性问题的方式，并且可以使代码更加灵活和可复用。在C++中，STL的适配器提供了方便的工具和容器，使开发者能够更好地处理不同的需求和场景。

            【C++】STL中stack和queue(适配器版)的模拟实现

            Stack的模拟实现

            Stack的基本结构

            这里很多人就会说，我们在C语言实现栈的时候就是像下面这么写的呐，就和实现vector一样的方式去实现stack不就行了嘛？如果是要用这样的方式去实现，那么博主今天就不会提到适配器这个概念了。

            【C++】STL中stack和queue(适配器版)的模拟实现

            代码思路: 既然我们使用适配器来帮助我们来实现stack，那就是说你这个容器适配器的功能要满足我们stack所需要的入栈、出栈、获取栈顶元素、判断是否为空等等。

            namespace bit 
{
	//这里我们通过模板来灵活的选择底层的容器适配器，只需要适配器满足我们所需要的操作即可
	template//适配器
	class stack
	{
	private:
		Container _con;
	};

            STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

            1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
            2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。
            3. 当然了这里你也可以显示调用你想用的容器适配器例如vector和list也都是可以的。

            常见函数的模拟实现

            入栈 - push(const T& x)

            代码思路: 这里我们知道栈的基本结构就是先入栈的会后出，后进栈的先出，我们只需要在容器的尾部进行尾插，即可完成入栈，但是我们需要注意的是我们是尾插，所以再出栈的时候就直接出容器尾部的元素即可。

            void push(const T& x)//入栈
{
	_con.push_back(x);//调用适配器的push_back即可
}

            出栈- pop()

            代码思路:刚刚我们说过栈先进后出，并且我们是通过尾插来模仿入栈的操作，所以我们的最后一个元素就是最后尾插进来的元素，要想模拟出栈的操作就是对其进行尾删即可。

            void pop()//出栈
{
	_con.pop_back();//删除容器尾部的元素
}

            获取栈顶元素 - const T& top()

            代码思路: 我们是通过尾插来表示入栈，栈顶的元素就是最后一个入栈的元素，因此我们直接返回容器尾部的元素就可以模拟出获取栈顶元素的操作

            const T& top()//获取栈顶元素
{
	return _con.back();//调用适配器返回尾部的元素
}

            栈中的元素个数 - size_t size()

            代码思路: 这个就比较简单了，我们通过适配器返回当前元素个数即可

            size_t size()//栈中的元素个数
{
	return _con.size();
}

            判断栈是否为空

            代码思路: 同理直接调用适配器的函数即可

            bool empty()//判断栈是否为空
{
	return _con.empty();
}

            整体代码:

            namespace bit 
{
	//template //传统的写法
	//class stack
	//{
	//	private:
	//	T* _a;
	//	int _top;
	//	int _capacity;
	//};
	template//适配器
	class stack
	{
	public:
		void push(const T& x)//入栈
		{
			_con.push_back(x);
		}
		void pop()//出栈
		{
			_con.pop_back();//删除容器尾部的元素就是出栈
		}
		size_t size()//栈中的元素个数
		{
			return _con.size();
		}
		const T& top()//获取栈顶元素
		{
			return _con.back();//返回队尾的元素
		}
		bool empty()//判断栈是否为空
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

            Queue的模拟实现

            Queue的基本结构

            代码思路:同理我们这里依然可以使用适配器帮助我们来模拟实现queue的基本结构，但是一定记住适配器里面的操作必须满足你所需要的操作

            namespace bit
{
	template //调用适配器
	class queue
	{
	private:
		Container _con;
	};
}

            常见函数的模拟实现

            入队列- push(const T& x)

            代码思路: 这里我们依然提一下，队列是先进先出，后进的后出和栈是完全相反的，所以我们在入队列的时候尾插的时候要记住，出队列的时候就是该容器的第一个元素先出，最后一个元素就是最后进去的元素就是最后出

            void push(const T& x)//入队列
{
	_con.push_back(x);//队列先进去的先出去，入队列就直接尾插
}

            出队列- pop()

            代码思路:刚刚我们提到了因为我们是尾插来模拟的入队列，所以出队列的时候就要通过删除第一个元素来模拟出队列，但是这里需要注意的是Vector中是没有pop_front()这个函数的，所以我们的适配器只能是List和deque

            void pop()//出队列
{
	_con.pop_front();//出队列就依次头出即可,这里就不能用vector了，vector没有pop_front
}

            获取队头元素- const T& front()

            代码思路: 刚刚提到了容器的第一个元素就是队头元素，因此我们只需要获取第一个元素即可。

            const T& front()//获取队头元素
{
	return _con.front();//通过适配器获取队头元素
}

            获取队尾元素- const T& back()

            代码思路:因为我们是尾插，所以队尾元素就是最后一个进去的元素，所以通过适配器获得队尾元素即可。

            const T& back()//获取队尾元素
{
	return _con.back();//调用适配器获取队尾元素
}

            获取队列元素个数 - size_t size()

            代码思路：这个和前面的栈同理就不过多的讲解了

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

            判断队列是否为空 - bool empty()

            代码思路: 这个也是一样的直接调用适配器里面的函数即可

            bool empty()
{
	return _con.empty();//同理调用适配器判断是否为空
}

            整体代码

            namespace bit
{
	template 
	class queue
	{
	public:
		void push(const T& x)//入队列
		{
			_con.push_back(x);//队列先进去的先出去，入队列就直接尾插
		}
		void pop()//出队列
		{
			_con.pop_front();//出队列就依次头出即可,这里就不能用vector了，vector没有pop_front
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
		const T& front()//获取队头元素
		{
			return _con.front();
		}
		const T& back()//获取队尾元素
		{
			return _con.back();
		}
	private:
		Container _con;
	};
}

            好啦，今天的内容就到这里啦，下期内容预告STL中的优先级队列的使用与模拟实现.

            结语：今天的内容就到这里吧，谢谢各位的观看，如果有讲的不好的地方也请各位多多指出，作者每一条评论都会读的，谢谢各位。

            🌏🗺️ 这里祝各位接下来的每一天好运连连 💞💞
VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]