C++ --- stack和queue的使用以及简单实现

前言

栈和队列是两个比较简单的数据结构，接口较少，学习容易，首先先回顾这两个容器的特性。
栈 - - - 先进后出，并且只在栈顶出入数据。
队列 - - - 先进先出，在队尾入数据，在队头出数据。

其次对于它俩的简单实现会接触一个新的东西叫做容器适配器 / 配接器和一个新的数据结构双端队列（deque）。

最后最重要的一点，由于这两个容器有特殊的数据顺序（先进后出、先进先出），所以底层不支持迭代器遍历。 想要输出数据需要使用循环。

一、stack和queue的使用

在C++容器中这两个的接口大致是一样，主要都是由push，pop，top，empty，size这几个接口为核心。

1.stack的使用

容器栈是一个类模板，其模板参数由推演类型T和容器适配器Container构成，这个容器适配器简单来说就是第二个模板参数传递一个容器(详细介绍在简单实现板块说明)。

// 栈的使用
// 回顾栈的特性：数据先进后出，只在栈顶位置操作数据
// 重要的三个接口：push()，pop()，top()
// 模板的第二个参数就是容器适配器
stack<int, vector<int>> st;        // 创建顺序栈
//stack<int, list<int>> st;        // 创建链栈st.push(10);
st.push(20);
st.push(30);
st.push(40);
st.push(50);// 循环输出数据
while (!st.empty())
{cout << st.top() << " ";  // 打印结果：50 40 30 20 10st.pop();
}
cout << endl;

2.queue的使用

容器队列和容器栈一样也是一个类模板，其模板参数由推演类型T和容器适配器Container构成。

// 队列的使用
// 回顾队列的特性：数据先进先出，在队头和队尾位置操作数据
// 重要的四个接口：push()，pop()，front()，back()
// 同样模板的第二个参数就是容器适配器
//queue<int, vector<int>> q;        // 创建顺序队列
queue<int, list<int>> q;        // 创建链队列q.push(10);
q.push(20);
q.push(30);
q.push(40);
q.push(50);// 循环输出数据
while (!q.empty())
{cout << q.front() << " "; // 打印结果：10 20 30 40 50q.pop();
}
cout << endl;

queue没有top接口，有一个取队头元素front和取队尾元素back。

二、stack和queue的简单实现

容器适配器

stack和queue的实现和前面学习的容器完全不同，之前学习的容器我们的实现都是非常详细的，相当于住房从造房子开始，而他俩的实现好比直接买一套房子，不用从头开始造，而这个现成的房子也就是所谓的容器适配器，就是拿已有的容器类型去适配出我们所需要的容器。

1.stack

	// 容器适配器// = vector<T> 相当于缺省值，不传模板的第二个参数就使用此缺省值创建// 而stack和queue实际的容器适配器的缺省值（模板参数也是可以有缺省值的）是deque，这也是一个数据类型，叫做双端队列//template<class T, class Container = vector<T>>// Contaienr就是容器的意思template<class T, class Container = deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top() const{return _con.back();}bool empty(){return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};

这里的Container需要编译器自行推演其容器类型，就和前一个T一样，T也是需要编译器自行推演的数据类型。

假设这里的Container类型是vector，具体的实现细节就如下面所示：

	template<class T>class stack{public:void push(const T& x){v.push_back(x);}void pop(){v.pop_back();}const T& top() const{return v.back();}bool empty(){return v.empty();}private:vector<T> v;};

这里的Container就是具体的一个容器vecor。

2.queue

template<class T, class Container = deque<T>>
class queue
{
public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& top() const{return _con.front();}bool empty(){return _con.empty();}size_t size() const{return _con.size();}private:Container _con;
};

对比上述两个容器的简单实现，内容都是差不多的，只是当中的一些细节有差别。

三、双端队列deque

双端队列是栈和队列容器的默认适配器，它的结构有点像是vector和list的结合，有一个中控数组，数组内部保存的是指向每个小数组的指针，而每个小数组又去存储需要的数据，整体结构如下所示：

这里就不去细究它的底层实现逻辑了，既然是它俩的默认适配器，那么此结构在首和尾的位置上操作数据是非常方便，高效的，但是对于中间位置的数据操作就不是很优越。所以deque并不是一个完美的结构，它依旧代替不了vector和list。

和vector与list的优缺点

vector：在表尾插入删除数据效率高，表头和表中插入删除数据效率一般。
list：在表头插入删除数据效率高，表尾和表中插入删除数据效率一般。
deque：在表头和表尾插入删除数据效率高，表中插入删除数据效率一般。

正因上述优缺点，表头和表尾这些特殊的位置操作数据效率高，所以它就适合作为stack和queue的默认适配器。