💭 写在前面
在上一章中，我们讲解了STL的栈和队列，本章我们来模拟实现一下它们。在讲解优先级队列的同时我们顺便把上一章提到的仿函数进行一个讲解，使用仿函数可以有效替换使用难以理解的函数指针的场景。我们通过仿函数 less 和 greater 去控制优先级队列的 Compare，从而能同时适配升序和降序。
Ⅰ. 模拟实现 stack
0x00 实现思路
插入数据删除数据这些逻辑其实没有必要自己实现，而是采用转换的方式。
两章前我们讲解了适配器的知识，这里采用的就是一些其它的适配的容器去实现。
至于这里转换什么，我们可以进一步思考，似乎有很多容器都适合去转换，
所以 STL 增加了一个模板参数 Container，利用 Container 来进行转换。
在上一章的末尾，我们讲述了利用 deque 去实现栈和队列是最合适不过的了：
template<class T, class Container = deque<T>>
（至于 deque 的底层我们放到后面去说，我们先学会如何用 deque 去实现栈和队列）
对于栈而言，push 插入数据就是尾插 push_back，pop 删除数据就是尾删 pop_back，
void push(const T& x) { _con.push_back(x); // 对于栈而言，入栈就是尾插 } void pop() { _con.pop_back(); // 对于栈而言，出栈就是尾删 }
返回堆顶数据我们可以用 back()，即可达到返回尾上数据的效果，本质上是一种封装。
const T& top() { return _con.back(); // 返回尾上数据 }
这里甚至都不需要考虑断言，因为那是下层需要做的事情，这里我们要做的只是 "转换" 。
💬 代码：stack
#include <iostream> #include <deque> using namespace std; namespace foxny { 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() { return _con.back(); // 返回尾上数据 } size_t size() { return _con.size(); // 返回大小 } bool empty() { return _con.empty(); // 返回是否为空 } private: Container _con; }; }
0x01 代码测试
先默认用 deque 去存储：
#include <iostream> #include <deque> using namespace std; namespace foxny { void test_stack1() { stack<int> st; st.push(1); st.push(2); st.push(3); st.push(4); while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; } }
🚩 运行结果：
默认传 deque，如果不想用 deque，你可以自由的去传。
#include <iostream> #include <deque> #include <vector> using namespace std; namespace foxny { void test_stack2() { stack<int, vector<int>> st; // 我想默认用 vector st.push(1); st.push(2); st.push(3); st.push(4); while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; } }
🚩 运行结果：
我们再试试默认用 list 可不可以：
#include <iostream> #include <deque> #include <list> using namespace std; namespace foxny { void test_stack3() { stack<int, list<int>> st; // 我想默认用 list st.push(1); st.push(2); st.push(3); st.push(4); while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; } }
🚩 运行结果：
❓ 思考：可否用 string？
勉强可以，只要你是顺序容器都可以。但是用 string 是有风险的，可能会出现溢出和截断。
#include <iostream> #include <deque> #include <string> using namespace std; namespace foxny { void test_stack4() { stack<int, string> st; // 我想默认用 string st.push(1); st.push(2); st.push(3); st.push(400); // 这里推一个400看看 while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; } }
🚩 运行结果：
🔺 总结：从上层角度来看，其默认是一个双端队列，我底层用什么存，去实现这个栈并不重要，只要其符合要求就行。它保存的是栈的性质，复用的是容器的代码。
Ⅱ. 模拟实现 queue
0x00 实现思路
一回生二回熟，其默认容器也是 deque，直接照着 stack 的基础去修改成 queue 即可。
template<class T, class Container = deque<T>>
queue 是先进先出的，queue 的 push 仍然是尾部的插入，而 pop 需要支持头部的删除。
void push(const T& x) { _con.push_back(x); // 进队 } void pop() { _con.pop_front(); // 出队 }
值得注意的是，queue 不能用 vector 去适配，因为 vector 压根就没有 pop_front 这个接口。
（我看你是在刁难我胖虎.jpg）
queue 的 front 和 back 我们直接调 front 和 back 去取队列头尾的数据即可：
const T& front() { return _con.front(); } const T& back() { return _con.back(); }
剩下的 size 和 empty 都不用变。
💬 代码实现：queue
#include <iostream> #include <deque> using namespace std; namespace foxny { 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& front() { return _con.front(); } const T& back() { return _con.back(); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: Container _con; }; }
0x01 代码测试
先测试默认用 deque 去存储：
#include <iostream> #include <deque> using namespace std; namespace foxny { void test_queue1() { queue<int> q; q.push(1); q.push(2); q.push(3); q.push(4); while (!q.empty()) { cout << q.front() << " "; q.pop(); } cout << endl; } }
🚩 运行结果：
指定用 list 去存：
#include <iostream> #include <deque> #include <list> using namespace std; namespace foxny { void test_queue2() { queue<int, list<int>> q; q.push(1); q.push(2); q.push(3); q.push(4); while (!q.empty()) { cout << q.front() << " "; q.pop(); } cout << endl; } }
🚩 运行结果：
我们来试一下指定用 vector 会怎么样：
#include <iostream> #include <deque> #include <vector> using namespace std; namespace foxny { void test_queue3() { queue<int, vector<int>> q; q.push(1); q.push(2); q.push(3); q.push(4); while (!q.empty()) { cout << q.front() << " "; q.pop(); } cout << endl; } }
🚩 运行结果：
error C2039: "pop_front": 不是 "std::vector<int,std::allocator<T>>" 的成员 1> with 1> [ 1> T=int 1> ] 1>D:\360MoveData\Users\Chaos\Desktop\code2022\2022_7_17\2022_7_17\test.cpp(62): message : 参见“std::vector<int,std::allocator<T>>”的声明 1> with 1> [ 1> T=int 1> ] 1>D:\360MoveData\Users\Chaos\Desktop\code2022\2022_7_17\2022_7_17\test.cpp(14): message : 在编译 类 模板 成员函数“void foxny::queue<int,std::vector<int,std::allocator<T>>>::pop(void)”时……
正所谓 —— 明知山有虎，别去明知山。明知 vector 无头删，队列就别用 vector！
用其他东西转换搞出来的栈和队列，只要符合要求就可以。实际上也不一定真的是直接转换。
我们下面还要学一个更复杂的
