stack的简单实现

适配器模式
stack的实现
- 代码实现
为什么没有迭代器的实现？
实际默认容器是deque（了解即可）
- deque
- deque的优缺点
谢谢观看

适配器模式

stack和我们之前学的list 和 vector 不一样采用的适配器模式
什么叫适配器呢？我们常见的电源适配器就是把220v的高电压转到电器能承受的电压，起转化的作用。
而模式就是人们之前总结的经验，模板。

stack的实现

stack的实现也是借助list，vector等实现的。

代码实现

#pragma once
#include<vector>
#include<iostream>
using namespace std;
namespace bit 
{
	template<class T, class Container = vector<T>>
	//typedef Container con;
	class stack 
	{
	public:
		void push(const T& x) {
			_con.push_back(x);
		}
		T& top() {
			return _con.back();
		}
		void pop() {
			_con.pop_back();
		}
		size_t size() {
			return _con.size();
		}
		bool empty() {
			return _con.empty();
		}

	private:
		Container _con;
	};
}

为什么没有迭代器的实现？

因为栈规定先进后出，所以不提供顺序遍历的迭代器！

实际默认容器是deque（了解即可）

deque

deque 它集合了vector 和 list的优点是一种双开口的"连续"空间的数据结构。
deque并不是真正连续的空间，而是由一段段连续的小空间（buff）拼接而成的，实际deque类似于一个动态的二维
数组，其底层结构如下图所示：
在这里插入图片描述
它的插入是中控指针数组从中间往两边开空间放值
每个数组的大小N
定位第i个数组数据：

当头部数组满时：
第几个数组：第i个buff i /N，数组中第几个： i %N
当头部没满时：
先 i -= 第一数组中元素的个数然后就和第一种情况一样了。

deque的优缺点

优点：头插和尾插效率高
缺点：中间删除会很麻烦，有两种解决方案从删除位置后所有数组的元素都先前移动一个位置，后面元素越多越麻烦。另一种方法是记录每一个数组的大小，数组的大小可以不一样了，只需要移动pos位置所在的数组即可。但是这样定位第i个元素又很麻烦了。
其次随机访问效率不高。
把数据拷贝到vector中排序都比直接用deque排序快