当前位置：首页 > news >正文

【C++笔记】STL详解： stack 和 queue 的实现

news 2026/8/6 11:45:42

前言：

C++标准模板库(STL)中的stack ( 栈 ) 和 queue ( 队列 ) 属于容器适配器类别，这意味着它们并非独立实现，而是基于其他容器构建的。

本文将深入解析容器适配器的工作原理，并逐步演示如何从零开始实现stack和queue。

一、容器适配器

"容器适配器"类比为生活中常见的"电源转换器"或"接口转接器"：

它本身并不提供数据存储功能，而是通过封装现有的基础容器（如deque、vector或list），隐藏部分功能并只暴露特定接口，从而使这些基础容器能够呈现出特定数据结构的行为特征。

stack（栈）：只允许在栈顶操作数据，遵循后进先出（LIFO）原则，其底层默认使用 deque，也可指定 vector 或 list 作为适配器容器。

queue（队列）：只允许队尾进、队头出，遵循先进先出（FIFO）原则，其底层默认同样是 deque，也可以用 list 来替代作为适配器容器。

二、stack 模拟实现

2.1 类模板定义

template<class T, class Contanier = std::deque<T>> class stack { private: Contanier _con; };

A. 模板参数：
template<class T, class Contanier = std::deque < T > >
解释：
1. T为储存的数据类型，可以指定为int、char、string、double ...
2. Container为底层容器类型，默认是deque < T >
B. 成员变量：
Container _con;
解释：
1. Container：这通常是一个模板参数，它代表了底层使用的是什么数据结构。
例如： std::deque<int>、std::vector<int> 或 std::list<int> 。
2. _con：这是实例化的成员变量名。

2.2 成员函数实现

#include <deque> // T 是数据类型，Container 是底层容器类型（默认用 deque） template <class T, class Container = std::deque<T>> class my_stack { public: // 当你调用栈的 push 时 void push(const T& val) { _con.push_back(val); // 适配器说：_con，帮我在尾部塞个数据 } // 当你调用栈的 pop 时 void pop() { _con.pop_back(); // 适配器说：_con，帮我把尾部的数据删掉 } // 当你获取栈顶元素时 T& top() { return _con.back(); // 适配器说：_con，把你尾部的数据拿给我看看 } // 检查是否为空 bool empty() const { return _con.empty(); } private: Container _con; // <--- 就是这里！实际负责装数据的底层打工仔 };

2.3 代码测试

// ========================================== // 专项测试 1: 默认栈 (底层为 std::deque) // ========================================== void test_default_stack() { std::cout << ">>> 开始测试: 默认栈 (底层: std::deque) <<<" << std::endl; my_stack<int> s; std::cout << "1. 初始状态 -> 空: " << (s.empty() ? "Yes" : "No") << ", 大小: " << s.size() << std::endl; s.push(10); s.push(20); s.push(30); std::cout << "2. 压入 10, 20, 30 后 -> 空: " << (s.empty() ? "Yes" : "No") << ", 大小: " << s.size() << std::endl; std::cout << "3. 当前栈顶元素: " << s.top() << std::endl; s.pop(); std::cout << "4. 弹出一个元素后 -> 大小: " << s.size() << ", 新栈顶: " << s.top() << std::endl; std::cout << "5. 依次弹出剩余元素: "; while (!s.empty()) { std::cout << s.top() << " "; s.pop(); } std::cout << "\n6. 最终状态 -> 空: " << (s.empty() ? "Yes" : "No") << "\n\n"; } // ========================================== // 专项测试 2: Vector栈 (底层为 std::vector) // ========================================== void test_vector_stack() { std::cout << ">>> 开始测试: Vector栈 (底层: std::vector) <<<" << std::endl; my_stack<double, std::vector<double>> s; std::cout << "1. 初始状态 -> 空: " << (s.empty() ? "Yes" : "No") << ", 大小: " << s.size() << std::endl; s.push(1.1); s.push(2.2); s.push(3.3); std::cout << "2. 压入 1.1, 2.2, 3.3 后 -> 空: " << (s.empty() ? "Yes" : "No") << ", 大小: " << s.size() << std::endl; std::cout << "3. 当前栈顶元素: " << s.top() << std::endl; s.pop(); std::cout << "4. 弹出一个元素后 -> 大小: " << s.size() << ", 新栈顶: " << s.top() << std::endl; std::cout << "5. 依次弹出剩余元素: "; while (!s.empty()) { std::cout << s.top() << " "; s.pop(); } std::cout << "\n6. 最终状态 -> 空: " << (s.empty() ? "Yes" : "No") << "\n\n"; } // ========================================== // 专项测试 3: List栈 (底层为 std::list) // ========================================== void test_list_stack() { std::cout << ">>> 开始测试: List栈 (底层: std::list) <<<" << std::endl; my_stack<std::string, std::list<std::string>> s; std::cout << "1. 初始状态 -> 空: " << (s.empty() ? "Yes" : "No") << ", 大小: " << s.size() << std::endl; s.push("C++"); s.push("Python"); s.push("Rust"); std::cout << "2. 压入 C++, Python, Rust 后 -> 空: " << (s.empty() ? "Yes" : "No") << ", 大小: " << s.size() << std::endl; std::cout << "3. 当前栈顶元素: " << s.top() << std::endl; s.pop(); std::cout << "4. 弹出一个元素后 -> 大小: " << s.size() << ", 新栈顶: " << s.top() << std::endl; std::cout << "5. 依次弹出剩余元素: "; while (!s.empty()) { std::cout << s.top() << " "; s.pop(); } std::cout << "\n6. 最终状态 -> 空: " << (s.empty() ? "Yes" : "No") << "\n\n"; } // ========================================== // 主函数 // ========================================== int main() { std::cout << "========== my_stack 专项全量测试 ==========\n\n"; test_default_stack(); test_vector_stack(); test_list_stack(); std::cout << "========== 测试圆满结束 ==========\n"; return 0; }

打印结果如下：

三、queue 模拟实现

3.1 类模板定义

template<class T, class Container = std::deque<T>> class queue { private: Container _con; };

A. 模板参数：
template<class T, class Contanier = std::deque < T > >
解释：
1. T为储存的数据类型，可以指定为int、char、string、double ...
2. Container为底层容器类型，默认是deque < T >
B. 成员变量：
Container _con;
解释：
1. Container：这通常是一个模板参数，它代表了底层使用的是什么数据结构。
例如： std::deque<int> 或 std::list<int> 。
2. _con：这是实例化的成员变量名。

3.2 成员函数实现

#include <iostream> #include <deque> #include <list> #include <string> template<class T, class Container = std::deque<T>> class my_queue { public: // 队尾入队：调用底层的 push_back void push(const T& val) { _con.push_back(val); } // 队头出队：调用底层的 pop_front (这也是为什么 vector 不能用的原因) void pop() { _con.pop_front(); } // 获取队头元素 T& front() { return _con.front(); } // 获取队尾元素 T& back() { return _con.back(); } // 判断是否为空 bool empty() const { return _con.empty(); } // 获取元素个数 size_t size() const { return _con.size(); } private: Container _con; // 底层打工仔 };

3.3 代码测试

// ========================================== // 专项测试 1: 默认队列 (底层为 std::deque) // ========================================== void test_default_queue() { std::cout << ">>> 开始测试: 默认队列 (底层: std::deque) <<<" << std::endl; my_queue<int> q; std::cout << "1. 初始状态 -> 空: " << (q.empty() ? "Yes" : "No") << ", 大小: " << q.size() << std::endl; q.push(10); q.push(20); q.push(30); std::cout << "2. 压入 10, 20, 30 后 -> 空: " << (q.empty() ? "Yes" : "No") << ", 大小: " << q.size() << std::endl; std::cout << "3. 当前队头 (front): " << q.front() << ", 队尾 (back): " << q.back() << std::endl; q.pop(); std::cout << "4. 出队一个元素后 -> 大小: " << q.size() << ", 新队头 (front): " << q.front() << std::endl; std::cout << "5. 依次出队剩余元素: "; while (!q.empty()) { std::cout << q.front() << " "; q.pop(); } std::cout << "\n6. 最终状态 -> 空: " << (q.empty() ? "Yes" : "No") << "\n\n"; } // ========================================== // 专项测试 2: List队列 (底层为 std::list) // ========================================== void test_list_queue() { std::cout << ">>> 开始测试: List队列 (底层: std::list) <<<" << std::endl; my_queue<std::string, std::list<std::string>> q; std::cout << "1. 初始状态 -> 空: " << (q.empty() ? "Yes" : "No") << ", 大小: " << q.size() << std::endl; q.push("第一名"); q.push("第二名"); q.push("第三名"); std::cout << "2. 压入数据后 -> 空: " << (q.empty() ? "Yes" : "No") << ", 大小: " << q.size() << std::endl; std::cout << "3. 当前队头: " << q.front() << ", 队尾: " << q.back() << std::endl; q.pop(); std::cout << "4. 办完业务(出队)一人后 -> 大小: " << q.size() << ", 新队头: " << q.front() << std::endl; std::cout << "5. 依次出队剩余元素: "; while (!q.empty()) { std::cout << q.front() << " "; q.pop(); } std::cout << "\n6. 最终状态 -> 空: " << (q.empty() ? "Yes" : "No") << "\n\n"; } // ========================================== // 主函数 // ========================================== int main() { std::cout << "========== my_queue 专项全量测试 ==========\n\n"; test_default_queue(); test_list_queue(); std::cout << "========== 测试圆满结束 ==========\n"; return 0; }

打印结果如下所示：

既然看到这里了，不妨关注+点赞+收藏，感谢大家，若有问题请指正。

查看全文

http://www.cnnetsun.cn/news/1730594.html