【c++】stack和queue模拟实现

> 作者简介：დ旧言~，目前大二，现在学习Java，c，c++，Python等
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：能手撕stack和queue模拟

> 毒鸡汤：过错是暂时的遗憾，而错过则是永远的遗憾！

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言

手撕stack和queue对比在数据结构中的模拟要比较简单，为什么呢？因为我们学习了参数模板这块，我们可以调用，所以模拟起来比较简单，具体是如何简单法呢，我们进入正文：

⭐主体

这里我们创建三个文件：stack.h，queue.h，test.cpp。

第一个：迭代器模式
迭代器模式就是在不暴露底层的细节的前提下，通过封装给用户提供统一的接口让用户访问容器里面的数据，我们使用的每个容器都可以通过创建迭代器变量的方式来访问容器里面的内容，并且访问的方式都是一样的，（*迭代器变量）可以得到并修改指定位置的数据，（迭代器++）可以让迭代器变量指向容器的下一个元素，通过上面的两个操作，不管是vector容器还是string容器还是后面要学的更加复杂的容器，我们都可以很简单的访问容器里面的内容，但是这些迭代器底层实现的原理是一样的吗？vector和string迭代器是通过创建一个指针变量来实现的，而list迭代器是创建一个类，通过这个类对list的数据进行封装来实现的，不同的容器的迭代器实现的方法也各不相同，但是作为使用者来说我们根本就不用了解这些迭代器的底层实现我们会用就行，并且迭代器的出现很大程度上降低了我们学习的成本，并且迭代器的出现还有助于维护数据的安全，如果我们认为的操作容器里面的数据的话，搞不好就将哪个重要的数据删除了，将另外一个地方的数据覆盖了，所以迭代器模式就对容器里面的数据进行了一下封装，我们要访问这些数据就只能通过迭代器的方式来进行访问，这样即降低了学习成本又保护了数据的安全，我们把这样的设计模式成为迭代器模式。
第二个：适配器模式
在之前的学习中我们知道stack对数据管理的方式是先入栈的数据后出栈，后入栈的数据先出栈，我们还知道queue对数据管理的方式是：先入队列的数据先出队列，后入队列的数据后出队列，这是两个容器对数据处理的方式，虽然这种处理数据的方式属于这些容器的，但是其他的容器也可以实现这样的功能，比如说vector和list都可以在容器的头部或者尾部插入或删除数据，如果我们只让vector或者list在容器的头部尾部插入删除数据的话，那是不是就相当于是stack了呢？如果我们只让vector或者list在头部删除数据在尾部插入数据的话，那这是不是就相当于queue了呢？所以在实现一个容器或者功能的时候，我们可以用现有东西进行一些简单的修改或者封装从而实现你想要的东西，那么这就是适配器模式：用已有的东西通过封装转换出来你想要的东西，那么我们这里的stack和queue就可以通过适配器模式来实现。

🌙stack模拟实现

模拟实现C++的栈时，应该要考虑用什么作为它的底层，目前来看，貌似动态数组vector是个不错的选择，因为栈只需要在栈顶插入和删除元素。

第二个模板参数的默认值给成vector<T>，这样就不需要用户自己传递第二个参数了。实现stack中的函数也很容易，只需要在函数内部调用vector的函数即可。

框架如下：

#include<iostream>
#include<vector>
#include<list>

using namespace std;
namespace lyk
{
	template<class T, class continer = vector<int>>
	class stack
	{
	public:
	private:
		continer con;
	};
}

💫元素入栈

首先来实现一下stack的push函数因为stack在插入数据的时候只能在尾部插入数据，所以在stack的push函数里面就可以直接调用容器con的push_back函数来尾插数据，那么该函数的实现如下：

// 元素入栈
void push(const T& val)
{
	con.push_back(val);
}

💫元素出栈

stack中删除数据也只能删除尾部数组，所以实现pop函数的时候就可以直接调用容器con的pop_back函数来删除数据，那这里的代码就如下：

// 元素出栈
void pop()
{
	con.pop_back();
}

💫获取元素有效个数

复用vector类的函数即可获得有效元素的个数，代码如下：

// 返回栈中元素个数
size_t size()
{
	return con.size();
}

💫判断栈是否为空

复用vector类的判空函数，代码如下：

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

💫返回栈顶元素

代码如下：

// 返回栈顶元素
const T& top()
{
	return con.back();
}

💫stack整体代码

#include<iostream>
#include<vector>
#include<list>

using namespace std;
namespace lyk
{
	template<class T, class continer = vector<int>>
	class stack
	{
	public:
		// 元素入栈
		void push(const T& val)
		{
			con.push_back(val);
		}
		// 元素出栈
		void pop()
		{
			con.pop_back();
		}
		// 返回栈中元素个数
		size_t size()
		{
			return con.size();
		}
		// 判断栈是否为空
		bool empty()
		{
			return con.empty();
		}
		// 返回栈顶元素
		const T& top()
		{
			return con.back();
		}
	private:
		continer con;
	};
	// 测试
	void test_stack()
	{
		lyk::stack<int> s1;
		s1.push(1);
		s1.push(2);
		s1.push(3);
		s1.push(4);
		while (!s1.empty())
		{
			cout << s1.top() << " ";
			s1.pop();
		}
		cout << endl;
		lyk::stack<int, list<int>> s2;
		s2.push(4);
		s2.push(3);
		s2.push(2);
		s2.push(1);
		while (!s2.empty())
		{
			cout << s2.top() << " ";
			s2.pop();
		}
	}
}

运行结果：

🌙queue模拟实现

同样的道理queue也要容纳各种数据，也可以由各种容器作为底层来容纳数据，所以queue也得创建一个模板，并且模板里面也得有两个参数，因为queue是在容器的头部删除数据，在容器的尾部插入数据，所以给第二个参数的缺省值最好是deque，那么这里的代码就如下：

#include<iostream>
#include<vector>
#include<list>
#include<deque>

namespace lyk
{
	template<class T, class continer = deque<T>>
	class queue
	{
	public:
	private:
		continer con;
	};

}

💫元素入队列

因为queue插入数据是在容器的尾部插入数据，所以在实现queue的push函数时可以通过调用con的push_back函数来实现，那这里的代码如下：

// 元素入队列
void push(const T& val)
{
	con.push_back(val);
}

💫元素出队列

queue的pop函数是在容器的头部删除数据所以这里可以调用容器的pop_front函数来实现，那么这里的代码如下：

// 元素出队列
void pop()
{
	con.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();
}

💫queue整体代码

#include<iostream>
#include<vector>
#include<list>
#include<deque>

namespace lyk
{
	template<class T, class continer = 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();
		}
		// 判断队列是否为空
		bool empty()
		{
			return con.empty();
		}
		// 返回队头元素的引用
		const T& front()
		{
			return con.front();
		}
		// 返回队头元素的引用
		const T& back()
		{
			return con.back();
		}
	private:
		continer con;
	};

	void test_queue()
	{
		//bit::queue<int> q;
		// 
		// vector不能适配
		//bit::queue<int, vector<int>> q;
		lyk::queue<int, list<int>> q;

		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);

		while (!q.empty())
		{
			cout << q.front() << " ";
			q.pop();
		}
		cout << endl;
	}

}

运行结果：