目录
前言
前面我们已经在数据结构中已经了解到有关栈和队列的相关知识，想必都不陌生，核心操作就只有几个，C++库里也不例外！内容不多，一起来看stack和queue（建议PC端打开）
一、stack
Ⅰ.介绍
stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
stack容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层元素，特定容器的尾部(即栈顶)被压入和弹出。
stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
- empty：判空操作
- back：获取尾部元素操作
- push_back：尾部插入元素操作
- pop_back：尾部删除元素操作
比如前面我们提到的vector、list等容器都支持以上操作，就可以作为stack的底层容器！
Ⅱ.使用
1、定义方式
//方式一，不写就用默认的底层容器
stack<int> ss1;
//方式二，利用特定的容器
stack<int,vector<int>> s2;
stack<int,list<int>> s3;
注意：不写默认的底层容器是deque！
2、常用接口：
| empty（） | 判断栈是否为空 |
| size（） | 返回栈的元素个数 |
| top（） | 返回栈顶元素的引用 |
| push（） | 将元素压入栈 |
| pop（） | 栈顶元素出栈 |
3、使用示例
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main()
{
stack<int> s;//默认底层容器是deque
stack<int, vector<int>> s1;
//压栈
for (int i = 1; i <= 10; i++)
{
s.push(i);
}
cout << s.size() << endl;
//出栈
while (!s.empty())
{
cout << s.top()<<" ";
s.pop();
}
cout << endl;
for (int i = 0; i <= 10; i++)
{
s1.push(i);
}
cout << s1.size() << endl;
while (!s1.empty())
{
cout << s1.top() << " ";
s1.pop();
}
return 0;
}二、queue
Ⅰ、介绍
队列同样也是一种容器适配器 ，专门用于在 FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
- empty：检测队列是否为空
- size：返回队列中有效元素的个数
- front：返回队头元素的引用
- back：返回队尾元素的引用
- push_back：在队列尾部入队列
- pop_front：在队列头部出队列
很显然vector就不能作为其底层容器，因为没有pop_front()！deque和list依然可以作为底层容器！
Ⅱ、使用
1、定义方式
//方式一，默认底层容器是deque
queue<int> q1;
//方式二，利用特定的容器
queue<int,list<int>> s2;2、常用接口
| empty() | 判断队列是否为空，bool类型 |
| size(） | 返回有效数据个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 入队列 |
| pop() | 出队列 |
3、使用示例
#include <iostream>
#include <queue>
#include <list>
using namespace std;
int main()
{
queue<int> q;//默认deque
queue<int, list<int>> q1;
//入队
for (int i = 1; i <= 10; i++)
{
q.push(i);
}
cout << q.size() << endl;
//出队
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
for (int i = 0; i <= 10; i++)
{
q1.push(i);
}
cout << q1.size() << endl;
while (!q1.empty())
{
cout <<q1.front() << " ";
q1.pop();
}
return 0;
}
三、deque(了解)
这里说一下简单了解一下deque，它实际上是被称为双端队列，是一种双开口的"连续"空间的数据结构！说白了就是可以在两端进行元素的插入和删除，可以这么认为它实际就是vector和list的结合体！
deque缺陷
- 相比于vector，头插头删不需要移动大量数据，扩容也不需要搬移大量元素！效率更高
- 相比于list，其底层是连续空间（并不是真正连续），空间利用率比较高，不需要存储额外字段。
- 致命缺陷：不合适遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下！因此实际应用到它的机会不多，目前可见的是作为stack和queue的默认底层容器
为什么是它作为默认底层容器？
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长 时，deque 不仅效率高，而且内存使用率高。
结合了deque的优点，避开了其缺陷，所以作为默认底层容器！
四、容器适配器
适配器是一种设计模式 ( 设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结) ， 该种模式是将一个类的接口转换成客户希望的另外一个接口 。本质就是一种转化！在通俗一点来说就好像插排的转接器，让不合适的插座转化成你想要的插座！
今天的分享就到这里，大家不难发现，这里的stack和queue实际都是对底层容器的接口进行封装而已！同时特别注意一点stack和queue没有迭代器！
