栈和队列（适配器模式模拟）

声明

模拟实现源代码已上传至gitee仓库：stack_queue_learn

stack的介绍

stack文档介绍

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类
4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

queue的介绍

queue的文档介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

deque双端队列简单介绍（了解）

概述

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和 删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比 较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维 数组：

如果需要尾插，就在中控数组中新开一个buffer数组，如果头插，就在中控数组前面开一个buffer数组，如果中控数组满了就扩容。

此时如何查找第i个值呢？

1. 如果第一个buffer不满，i=i-第一个buffer的数据个数
2. 如果第一个buffer满的，先找在第几个buffer中：i/N；在这个buffer中的第几个：i%N

那deque是如何借助其迭代器维护其假想连续的结构呢？ deuqe内部有两个迭代器：iterator start和iterator finish

优缺点

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。

与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

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

适配器模式

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

通过容器适配器模拟stack

#pragma once
#include<vector>
#include<list>

namespace gwj
{
	//stack<int,vector<int>> st1;
	//stack<int,list<int>> st2;

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

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

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

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

	private:
		Container _con;
	};
}

Container=std::vector<T>这意味着如果用户不显式提供容器类型，将默认使用 std::vector 作为容器类型。

template<class T,class Container=std::vector<T>>: 这是一个类模板的声明，定义了一个名为 stack 的类模板。它有两个模板参数：T 表示栈中元素的类型，Container 表示用于存储栈元素的容器类型。其中 Container=std::vector<T> 是默认模板参数，如果用户不显式指定容器类型，则默认使用 std::vector

通过容器适配器模拟queue

#pragma once
#include<deque>
#include <list>
namespace gwj
{
	template<class T, class Con =std::deque<T>>
	//template<class T, class Con = list<T>>
	class queue
	{
	public:
		queue() {}
		void push(const T& x) { _c.push_back(x); }
		void pop() { _c.pop_front(); }
		T& back() { return _c.back(); }
		const T& back()const { return _c.back(); }
		T& front() { return _c.front(); }
		const T& front()const { return _c.front(); }
		size_t size()const { return _c.size(); }
		bool empty()const { return _c.empty(); }
	private:
		Con _c;
	};
}

template<class T, class Con = std::deque<T>>: 这是一个类模板的声明，定义了一个名为 queue 的类模板。它有两个模板参数：T 表示队列中元素的类型，Con 表示用于存储队列元素的容器类型。默认情况下，容器类型为 std::deque<T>，即双端队列。

总结

前面我们学习了string、vector、list现在我们来学习stack和queue时，我们会发现轻松了很多，在学习stl时，遇到不会的函数调用接口，我们直接去查阅文档即可。