1. 容器适配器
1.1 什么是适配器
想了解这里的 "适配器"，我们先去看看电源适配器:
【百度百科】电源适配器又叫外置电源，是小型便携式电子设备及电子电器的供电电压变换设备，常见于手机、液晶显示器和笔记本电脑等小型电子产品上。
电源适配器是进行 "转换" 的，它本质上可以理解为是一个变压器。
标准家庭用电电压为220V，我们设备用电其实并不需要这么高，
而电源适配器可以使较高的交流电压降低到合适于手机电池的直流工作电压。
也就是说，电源适配器是用来 "转换" 的。
再看看容器适配器：
一种用来修饰容器，仿函数或者迭代器的接口的东西。
配接器修改类的接口，使原来不相互匹配的两个类可以相互匹配，进行合作。
1.2 STL标准库中stack和queue的底层结构
前一篇我们提到：虽然stack和queue中也可以存放元素，
但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，
这是因为stack和队列只是对其他容器的接口进行了包装，
STL中stack和queue默认使用deque，比如：
deque（双端队列，后面讲）（可以手动换成其它的）
2. stack和queue的模拟实现
2.1 stack模拟实现
我们以前已经用C语言写过了一个数组栈：
数据结构与算法⑧(第三章_上)栈的概念和实现(力扣：20. 有效的括号)_GR C的博客-CSDN博客
数组栈和链式栈
实现栈无非就两种结构：数组结构 和 链式结构，两种结构都可以实现。
数组栈和链式栈哪种结构更好？
相对而言数组的结构实现更优，尾插尾删的效率高，缓存利用率高，它的唯一缺点只是增容，
但是增容1次扩2倍对栈来说本身就比较合理，是无伤大雅的。而链式栈虽然不会空间浪费，
用一个 malloc 申请一个，但是链式栈存在一个致命的缺点：单链表不好出数据，
必须要实现双向链表，否则尾上删除数据将会异常麻烦。
如果硬要使用链式栈：
① 如果用尾做栈顶，尾插尾删，要设计成双向链表，否则删数据效率低。
② 如果用头做栈顶，头插头删，就可以设计成单链表。
在C++我们就可以直接用vector实现数组栈了，体会一下C++的方便，直接放stack.h了：
#pragma once #include <iostream> #include <vector> using namespace std; namespace rtx { template<class T> class stack { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_back(); } T& top() { return _con.back(); } const T& top() const { return _con.pop_back(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: vector<T> _con; }; }
测试Test.c:
#include "Stack.h" void test_stack() { rtx::stack<int> st; st.push(1); st.push(2); st.push(3); st.push(4); st.push(5); cout << "st.size() = " << st.size() << endl; while (!st.empty()) { cout << st.top() << " "; // 后进先出 st.pop(); } cout << endl; } int main() { test_stack(); return 0; }
我们这里复用了vector，这是不是适配器呢？
这里并不是，因为底层已经写死了，它就是数组栈，如果我想要一个链式栈呢？
模板的方便又来了：
#pragma once #include <iostream> #include <vector> using namespace std; namespace rtx { template<class T, class Container> class stack { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_back(); } T& top() { return _con.back(); } const T& top() const { return _con.pop_back(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: //vector<T> _con; Container _con; }; }
#include "Stack.h" void test_stack() { rtx::stack<int, vector<int>> st; st.push(1); st.push(2); st.push(3); st.push(4); st.push(5); cout << "st.size() = " << st.size() << endl; while (!st.empty()) { cout << st.top() << " "; // 后进先出 st.pop(); } cout << endl; } int main() { test_stack(); return 0; }
如果我们要链式栈：把显示传的vector换成list（包一下头文件）：
前面说到，STL里面stack和queue的默认适配器是deque：
把其它头文件移到Test.c ，Stack.h的最终就是这样的：
#pragma once #include <deque> namespace rtx { template<class T, class Container = deque<T>> class stack { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_back(); } T& top() { return _con.back(); } const T& top() const { return _con.pop_back(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; }; }
2.2 queue的模拟实现
deque等下讲，这里先放queue的模拟实现，经过前面的学习，直接放了:
Queue.h:
#pragma once #include <deque> namespace rtx { template<class T, class Container = deque<T>> class queue { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_front(); } T& back() { return _con.back(); } T& front() { return _con.front(); } const T& back() const { return _con.back(); } const T& front() const { return _con.front(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; }; }
Test.c:
#include <iostream> #include <vector> #include <list> #include <string> using namespace std; #include "Stack.h" #include "Queue.h" void test_stack() { rtx::stack<int> st; st.push(1); st.push(2); st.push(3); st.push(4); st.push(5); cout << "st.size() = " << st.size() << endl; while (!st.empty()) { cout << st.top() << " "; // 后进先出 st.pop(); } cout << endl; } void test_queue() { rtx::queue<int> q; q.push(1); q.push(2); q.push(3); q.push(4); q.push(5); cout << "q.size() = " << q.size() << endl; while (!q.empty()) { cout << q.front() << " "; // 先进先出 q.pop(); } cout << endl; } int main() { test_stack(); test_queue(); return 0; }
值得注意的是这里的queue不能显示地传vector，因为vector没有头删。
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)（中）：https://developer.aliyun.com/article/1521888?spm=a2c6h.13148508.setting.25.712b4f0eDngT44
