C++——栈和队列容器
前言：这篇文章我们将栈和队列两个容器放在一起进行分享，因为这两个要分享的知识较少，而且两者在结构上有很多相似之处，比如栈只能在栈顶操作，队列只能在队头和队尾操作。
不同于前边所分享的三种容器，这篇文章要介绍的两个容器，不再是单纯的空间创建存储，而是以vector、list等容器为底层来实现的容器。
目录
一.栈
1.栈的框架
2.功能实现
二.队列
1.队列框架
2.功能实现
三.扩展
总结
一.栈
栈的关键在于只能从栈顶进行入栈和出栈，那么我们就可以将vector或者list的头作为栈底，在尾进行操作。
1.栈的框架
在数据结构的学习中我们已经知道，栈有顺序栈和链式栈两种，所以容器栈就可以按照需求，通过模板来选择是创建顺序栈还是链式栈：
#include
#include
namespace Mystack
{
//stack 顺序栈
//stack 链式栈
template
class stack
{
public:
private:
Container _con;
};
}
想要这样创建栈，就必须包含vector和list两个容器的头文件。
通过使用两个模板参数，一个代表数据类型，一个代表栈的类型。Container即英文"容器"。
因为通常情况下所使用的栈都是顺序栈，所以我们为了方便栈的创建，可以将模板也写成缺省模板。缺省模板和缺省函数类似。
2.功能实现
我们直接来看：
//入栈
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();
}
因为栈的底层是另外两种容器之一，所以我们可以直接去调用它们的成员函数来实现我们的成员函数，入栈就是尾插，出栈即是尾删、依次类推。
测试如下：
二.队列
队列不同于栈，队列是在队尾插入元素，在队头删除元素。但是我们知道，vector并不支持头部的插入删除操作，因为这样的效率很低，所以我们只推荐使用list来作为队列的底层。
1.队列框架
template
class queue
{
public:
private:
Container _con;
};
2.功能实现
//入队
void push(const T& x)
{
_con.push_back(x);
}
//出队
void pop()
{
_con.pop_front();
}
//队尾元素
T& back()
{
return _con.back();
}
const T& back()const
{
return _con.back();
}
//队头元素
T& front()
{
return _con.front();
}
const T& front()const
{
return _con.front();
}
//数据个数
size_t size()const
{
return _con.size();
}
//判空
bool empty()const
{
return _con.empty();
}
仍然是调用list的成员函数来实现queue的成员函数，测试如下：
三.扩展
除了vector、list之外，还有一种容器可以作为队列的底层——deque。
deque的底层是由多个长度相同的数组组成，而这些数组则由一个指针数组来管理。
deque能够同时支持下标随机访问和头尾的插入删除，所以除了队列之外，在C++的底层，栈和队列实际上都是由deque来实现的。
这里我们不对deque进行展开讲解，仅供小伙伴们了解。
总结
stack和queue的使用和模拟实现都非常简单，也算是为前边学习的复杂模拟的一点小放松。
喜欢本篇文章的小伙伴记得一键三连，我们下期再见！
