前言
本篇文章，博主将介绍STL中两个比较重要的容器适配器：stack（栈）和queue（队列）以及它们的使用方法，并且尝试模拟实现它们。如果你不是很了解栈和队列这两种数据结构，可以参阅这篇文章：
https://developer.aliyun.com/article/1634734?spm=a2c6h.24874632.expert-profile.39.673529be6NOC4o
正文开始
一、什么是容器适配器
与vector、list这些容器不同，stack和queue被称作容器适配器。所谓容器适配器，就是指在一种已有的容器基础上，为其添加了一些新的特性或者功能，目的是使一事物的行为类似于另一类事物。
例如栈这一数据结构，它的本质其实就是对顺序表或者链表的功能进行了一些限制，例如无法遍历、只能在一端进出数据等，但其底层仍然是顺序结构或是链式结构。STL在设计stack和queue时，并没有从零开始构建它们的底层结构，而是采用了这种设计思想，对现有容器进行了封装，从而实现了它们。
接下来，我们看看SGI版本的STL源码的stack实现：
可以看到，源码使用了一个叫做deque的容器创建对象，然后调用该对象的一些接口来实现stack的接口。之后模拟实现stack和queue的过程中，我们也将遵循源码的设计思路，对其他容器（例如vector和list）进行封装。
二、stack的使用及模拟实现
接下来，我们正式开始学习stack的使用方法，并尝试模拟实现。
1. stack的使用
stack的成员函数如下：
注意：容器适配器是不支持遍历的，所以它们没有迭代器接口。
empty
empty的作用是判断栈是否为空，若为空则返回true，否则返回false。
代码示例：
using namespace std; int main() { stack<int> s1; stack<int> s2; s2.push(1);//压入一个元素 cout << s1.empty() << endl; cout << s2.empty() << endl; return 0; }
size
size用于获取栈中元素个数。
代码示例：
using namespace std; int main() { stack<int> s; s.push(1); s.push(1); s.push(1); cout << s.size() << endl; return 0; }
top
top用于获取栈顶元素。 代码示例：
using namespace std; int main() { stack<int> s; s.push(10); cout << s.top() << endl; return 0; }
push和pop
push的功能是将数据压入栈顶，而pop可以将栈顶元素弹出。
使用举例：
using namespace std; int main() { stack<int> s; for (int i = 1; i <= 10; i++)//循环压入十个元素 { s.push(i); } while (!s.empty())//栈非空则循环出栈 { cout << s.top() << ' '; s.pop();//出栈 } return 0; }
swap
swap用于交换两个栈的内容。
2. stack的模拟实现
stack的模拟实现也比较简单，由于我们之前使用顺序结构来实现栈，那么我们就将vector作为封装容器。代码如下：
using namespace std; template<class T, class Container = vector<T>>//模板参数默认为vector class Stack { public: //压栈 void push(const T& x) { _con.push_back(x);//调用vector的尾插 } //出栈 void pop() { _con.pop_back();//调用vector的尾删 } //取栈顶元素 const T& top() const { return _con.back();//调用vector的获取尾元素 } //判空 bool empty() const { return _con.empty();//调用vector的empty } //获取元素个数 size_t size() const { return _con.size();//调用vector的size } //交换 void swap(Stack<T>& s) { _con.swap(s._con);//调用vector的交换函数 } private: Container _con;//成员容器 };
三、queue的使用及模拟实现
在掌握了stack的使用与模拟实现之后，我们为大家介绍queue的使用及模拟实现。
1. queue的使用
queue的成员函数如下：
empty
empty用于判断队列是否为空。若为空则返回true，否则返回flase。
代码示例：
using namespace std; int main() { queue<int> q1; queue<int> q2; q1.push(1); cout << q1.empty() << endl; cout << q2.empty() << endl; return 0; }
size
size用于获取队列中的元素个数。代码示例：
using namespace std; int main() { queue<int> q; q.push(1); q.push(1); q.push(1); q.push(1); q.push(1); cout << q.size() << endl; return 0; }
front和back
front和back分别用于获取对头/队尾元素。代码示例：
using namespace std; int main() { queue<int> q; q.push(1); q.push(2); q.push(3); q.push(4); q.push(5); cout << q.front() << endl; cout << q.back() << endl; return 0; }
push和pop
push和pop分别用于进行入队/出队操作。注意对头出队，队尾入队。
代码示例：
using namespace std; int main() { queue<int> q; for (int i = 1; i <= 10; i++) { q.push(i); } while (!q.empty()) { cout << q.front() << ' '; q.pop(); } return 0; }
swap
swap用于交换两个队列的内容。
2. queue的模拟实现
接下来，我们尝试模拟实现queue。由于list具有头删和尾插的接口，我们就将list作为封装容器。代码实现如下：
using namespace std; template<class T, class Container = list<T>>//模板参数默认为list class Queue { public: //入队 void push(const T& x) { _con.push_back(x);//调用list的尾插 } //出队 void pop() { _con.pop_front();//调用list的头删 } //取队头元素 const T& front() const { return _con.front();//调用list的front } //取队尾元素 const T& back() const { return _con.back();//调用list的back } //获取元素个数 size_t size() const { return _con.size();//调用list的size } //判空 bool empty() const { return _con.empty();//调用list的empty } //交换 void swap(Queue<T>& q) { _con.swap(q._con);//交换两个成员容器的内容 } private: Container _con;//成员容器 };
总结
今天我们学习了STL两个适配器：stack和queue的使用及模拟实现。不难发现，容器适配器的实现思路显著提高了正确率和代码复用率。 如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤
