九、stack和queue
1. stack和queue的介绍
stack 就是我们常说的 栈 ，而 queue 就是 队列 。栈就是 后进先出 的数据结构，队列就是 先进先出 的数据结构。从严格意义上来讲，这里的栈和队列已经不属于 容器 了，而是属于 容器适配器 。什么是 容器适配器 呢，我们待会再说。
2. stack和queue的使用
stack 和 queue 的使用非常简单。
栈就这么多接口，其中绝大部分接口我们已经非常非常熟悉了。
队列也只有这么点接口，同样我们都非常熟悉了。
我们发现，栈和队列有一个共同点：他们都不支持迭代器 。为什么呢？因为栈和队列有自己的输入和输出规则，栈是 后进先出 ，队列是 先进先出 ，而迭代器可能会打破这个规则，所以他们俩都不支持迭代器。
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
int main()
{
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
return 0;
}
3. stack和queue的模拟实现
在 STL库 里，这俩其实是通过 适配器模式 实现的。适配器是什么意思呢？他就像电源转换器一样，将多少多少伏特电压转换成多少多少伏特电压。具有 转换 的功能。我们一般都是通过循序结构来实现栈和队列的，但是既然我们已经学了 vector 和 list ，所以我们就能把 vector 和 list 拿过来使用。
#pragma once
#include<vector>
#include<list>
namespace my
{
template<class T, class Container>
class stack
{
public:
private:
Container _con;
};
}
在这里，如果是数组栈，那我们第二个参数传 vector 即可，如果是链式栈，那第二个参数传 list 即可。
// 数组栈
stack<int, vector<int>>;
// 链式栈
stack<int, list<int>>;
这样实现的栈就是 适配器模式的栈 ，通过容器适配出来的栈。
所以说，我们栈所需要的函数和结果，通过调用其他容器的函数就行。我们来见证一下：首先创建一个 Stack.h 头文件。
// Stack.h
#pragma once
#include<vector>
#include<list>
namespace my
{
template<class T, class Container>
class stack
{
public:
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();
}
private:
Container _con;
};
}
是不是很震惊？没错，调用其他容器的函数就能实现栈。我们来测试一下：
// test.cpp
#include<iostream>
#include"Stack.h"
using namespace std;
void test01()
{
my::stack<int, vector<int>> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
int main()
{
test01();
return 0;
}
跟我们想的栈几乎没区别好吧。仅仅只是创建对象的时候需要两个参数而已，但是 STL库 里的栈和队列就没有第二个参数，我们需要将第二个参数给优化掉。怎么优化呢？ 缺省参数 。
// 函数模板给缺省参数就能够解决问题。
template<class T, class Container = vector<T>>
class stack
{
public:
//
private:
Container _con;
};
这下若是使用数组栈，就可以只传一个参数了。
#include<iostream>
#include"Stack.h"
#include<queue>
using namespace std;
void test01()
{
my::stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
int main()
{
test01();
return 0;
}
栈的实现这么简单，队列的实现同样非常简单，这里我直接给代码了：
#pragma once
#include<list>
namespace my2
{
template<class T, class Container = list<T>>
class queue
{
public:
void push(const T& x)
{
// 尾部入队列
_con.push_back(x);
}
void pop()
{
// 头部出队列
_con.pop_front();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
const T& back()
{
return _con.back();
}
const T& front()
{
return _con.front();
}
private:
Container _con;
};
}
测试一下：
#include<iostream>
#include"Queue.h"
using namespace std;
void test02()
{
my2::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
int main()
{
test02();
return 0;
}
4. deque的简单了解
deque 是什么？deque 是 双端队列 。但其本质不是队列，它并不要求先进先出。它集合了 vector 和 list 的优点。
vector的优缺点
优点：支持下标随机访问。
缺点：头部或者中间插入/删除效率低，扩容有消耗
list的优缺点
优点：支持任意位置插入/删除，效率都不错。
缺点：不支持下标随机访问。
那我们还需要使用 vector 和 list 吗？当然要使用，不然我们学他们干什么哈哈。deque 就像是一个链表，每个节点存的都是一个小数组，然后通过一个 中控指针数组 来指向每一个节点的地址，就像 页表 一样。可以快速访问数据。由于 deque 支持头插和尾插，所以 中控指针数组一开始只能在中间 ，头插的时候中控指针数组往左延申，尾插的时候往右延申。当中控指针数组满的时候给其扩容。
由于 deque 的逻辑难度和实现难度都比之前的难不少，这里就不再详细实现，通过看文档了解即可。
deque的优缺点
优点：头插/尾插的效率很好。
缺点：中间插入会非常麻烦，效率一般，[]访问的效率不够极致。
在 STL库 里的栈和队列当中，默认容器都是 deque ，原因就是 deque的头尾插入删除很优秀 ，而栈和队列也仅仅支持头尾插入删除。
