创作初心：在加深个人对知识系统理解的同时希望可以帮助到更多需要的同学  

😄柯一梦的专栏系列

🚀柯一梦的gitee主页  

🛠️柯一梦的github主页

座右铭：功不唐捐，玉汝于成  

容器适配器

我们之前学习了很多的容器，如vector,list,string……但今天我们要学的stack&queue则是两个容器适配器，也就是限制了数据的进出顺序。我们可以打一个比方：容器适配器相当于手机充电器的数据线，将USB的接口变成Type-C的接口，它不存储数据，只是管理了数据的流入流出顺序。
==注意==：既然容器适配器规定了数据进出容器的顺序，所以容器适配器就没有迭代器。因为迭代器的作用就是遍历。容器适配器不支持随便访问容器内的数据

stack的实现

stack的成员函数：

我们的模拟实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#pragma once
#include<vector>
#include<list>
using namespace std;
namespace rxj//1 后面没有冒号
{
	template<class T,class Container = vector<T>>//2. 这里我们传入T的目的是为了push的时候知道容器内存放的数据是什么类型
	class stack
	{
	public:
		void push(const T& val)//在这里我们要传数据的引用，既然是引用，我们就要防止数据被修改
		{
			_con.push_back(val);//栈是后进先出，我们要往队尾插入数据
		}
		void pop()
		{
			_con.pop_back();//后进先出，我们要先出后面的元素
		}
		size_t size()const//避免数据在这个函数内被修改
		{
			return _con.size();
		}
		bool empty()const
		{
			return _con.empty();
		}
		const T& top()const
		{
			return _con.back();
		}
		void swap(stack<T, Container>& st)//这里的参数，我们在构造一个st的时候，会自动生成一个类，
		//T和container会自动给上值，所以我们如果想传入一个和原本对象相同类型的对象，就要这样传
		{
			_con.swap(st._con);
		}
	private:
		Container _con;//3. 成员变量要使用_命名法  4.stack并不管数据的存储，所以里面没有_data这个成员
	};
}

==注意==

1.对于构造函数，我们没有写，编译器会自动生成，成员变量会走一遍初始化成员列表，vector是自定义类型，编译器会调用它的构造函数
2.对于模版参数，我们可以给一个缺省值，stack用vector是更合适的

queue的实现

queue的成员函数：

要结合stack、queue的接口和list，vector的接口
queue的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#pragma once
#include<vector>
#include<list>
using namespace std;
namespace rxj
{
	template<class T,class Container = list<T>>//队列经常头删，所以我们默认使用list
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_front();//vector没有pop_front，所以容器不能传vector
		}
		bool empty()const
		{
			return _con.empty();
		}
		const T& front()const
		{
			return _con.front();
		}
		const T& back()const
		{
			return _con.back();
		}
		size_t size()const
		{
			return _con.size();
		}
		void swap(queue<T,Container>& q)
		{
			_con.swap(q._con);
		}
	private:
		Container _con;
	};
}

关于deque的引入:

为什么容器里面的queue和stack为什么不直接用vector实现还要单独写一个deque？

  • deque就是专门为queue和stack实现的，因为deque在头插头删，尾插尾删上面挺快的，而且是数组，所以CPU高速缓存命中率高，它的缺点就是中间插入删除效率低，但是stack和queue并不要求这些，这就很符合stack和queue的要求！但是为什么我们不直接使用vector呢？因为vector内存开辟空间会浪费，而且list不会，所以设计了deque，博采众长。但是deque只能当satck和queue的底层容器。
    这里就牵扯到vector和list各自的特点：

    1. vector的优缺点

      优点：==1==下标的快速访问 ==2==尾插尾删效率很高 ==3==cpu高速缓存命中率很高
      缺点：==1==头部或者中间插入删除效率低下 ==2==插入空间不够要扩容，扩容有 一定的（因为拷贝数据速度特别快，所以可以忽略不计） 性能消耗，倍数级扩容会存在空间浪费
      ==对于deque==来说：vector 1、扩容成本高 2、空间资源浪费

    2. list的优缺点

      优点：==1==任意位置O(1)的插入删除 ==2==按需申请释放内存
      缺点：==1==CPU高速缓存命中率地，还存在缓存污染 ==2==不支持按需申请释放
      ==对于deque来说：==list申请空间效率低

deque的优缺点：

1、deque非常适合头部的插入删除，效率高
2、下比哦啊随机访问效率也还行，但是大量访问效率上低于vector
3、中间插入删除效率很低，要大量挪动数据

因为我们是不会对stack和queue进行中间的插入删除的，所以我们就使用deque