【C++修炼秘籍】Stack和Queue

【C++修炼秘籍】STL-Stack和Queue

☀️心有所向，日复一日，必有精进

☀️专栏《C++修炼秘籍》

☀️作者：早凉

☀️如果有错误，烦请指正，如有疑问可私信联系；

【C++修炼秘籍】STL-Stack和Queue

前言

一、stack和queue介绍

二、stack和queue的使用/接口介绍

stack接口

queue接口

三、容器适配器（container adapter）

四、stack和queue模拟实现

stack模拟实现

queue 模拟实现

deque了解

deque缺陷

总结

前言

stack是一个先进后出（Frist In Last Out,FILO）的数据结构。只有一个出口，允许插入，删除，取栈顶元素，但除了最顶端，不能有任何方法存取其他元素，不允许任何遍历行为，所以stack不允许有遍历行为；

queue是一个先进先出（First In First Out,FIFO）数据结构。有两个出口，queue允许插入、删除，从尾端加入元素，取得头端加入元素。但是除了尾端可以加入，最头端可以去出元素外，没有任何方法存取元素，所以queue也不允许有遍历行为。

一、stack和queue介绍

之前学习过vector和list，我们如果使用vector和list来实现stack和queue多方便，其实从官方文档中看stack和queue不归为容器，stack和queue由底层容器完成工作，所以stack和queue是容器适配器container adapter或者称容器配接器；

二、stack和queue的使用/接口介绍

stack接口

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部的元素弹出

queue接口

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

三、容器适配器（container adapter）

容器适配器实际上是一种设计模式，对adapter的样式定义如下：将一个class的接口转换为另一个class的接口，使原本因接口不兼容而不能合作的classes，可以一起运作。其实简单的来说就是将一个类的接口转换成客户希望的另外一个接口。就像我们出国一样不同的国家电源接口是不一样的，我们需要购买转接头才能正常使用；

其实迭代器模式也是设计模式，大家可以参考相关文档。

四、stack和queue模拟实现

我们知道栈可以有数组栈和链栈或者队列，

属性：

template<class T>
class stack
{
    private:
    T*_a;
    int _top;
    int _capacity;
}

通过适配器模式，我们可以用已有的元素封装转换在直接使用

template<class T,class Container=vector<T>>
class stack
{ 
    private:
    Container _con;
}

使用时我们可以使用其他容器，数组栈，链式栈均可；

stack<int,vector<int>>st1;

stack<int,list<int>>st2;

queue用vector不好，头删有问题；所以queue直接用list来当默认容器；

官方底层用的deque，还是比较简单的这里就直接给出

stack模拟实现

#pragma once
//#include<vector>
#include<deque>
namespace my{
	//template<class T, class Containor = vector<T> >
	template<class T, class Container = deque<T>>
	class stack{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();
		}
		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}
	private:
		Container  _con;
	};
}

queue 模拟实现

#pragma once
#include<deque>
namespace my{
	//template<class T, class Containor = list<T> >
	template<class T, class Container = deque<T>>
		class queue{
		public:
			void push(const T& val)
			{
				_con.push_back(val);
			}
			void pop()
			{
				_con.pop_front();
			}
			const T& front()
			{
				return _con.front();
			}

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

			size_t size()
			{
				return _con.size();
			}
		private:
			Container  _con;
		};
}

❓这里为什么用的底层容器是deque？deque是什么？

vector头部中部插入删除效率低，而且扩容效率也低；

list不支持随机访问，CPU高速缓存命中低；有没有兼具vector和list优点的容器？诶，有就是deque（Double ended queue）

说是双端队列，但不符合FIFO

支持头删，支持随机访问

功能上功能完美所以为什么要有vector和list呢？

所以说着肯定会有问题呀；接下来我们详细介绍细节。