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

前言C标准模板库(STL)中的stack ( 栈 ) 和 queue ( 队列 ) 属于容器适配器类别这意味着它们并非独立实现而是基于其他容器构建的。本文将深入解析容器适配器的工作原理并逐步演示如何从零开始实现stack和queue。一、容器适配器容器适配器类比为生活中常见的电源转换器或接口转接器它本身并不提供数据存储功能而是通过封装现有的基础容器如deque、vector或list隐藏部分功能并只暴露特定接口从而使这些基础容器能够呈现出特定数据结构的行为特征。stack栈 只允许在栈顶操作数据遵循后进先出LIFO 原则其底层默认使用 deque也可指定 vector 或 list 作为适配器容器。queue队列 只允许队尾进、队头出遵循先进先出FIFO 原则其底层默认同样是 deque也可以用 list 来替代作为适配器容器。二、stack 模拟实现2.1 类模板定义templateclass T, class Contanier std::dequeT class stack { private: Contanier _con; };A. 模板参数templateclass T, class Contanier std::deque T 解释1. T为储存的数据类型可以指定为int、char、string、double ...2. Container为底层容器类型默认是deque T B. 成员变量Container _con;解释1. Container这通常是一个模板参数它代表了底层使用的是什么数据结构。例如 std::dequeint、std::vectorint 或 std::listint 。2. _con这是实例化的成员变量名。2.2 成员函数实现#include deque // T 是数据类型Container 是底层容器类型默认用 deque template class T, class Container std::dequeT 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_stackint 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_stackdouble, std::vectordouble 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_stackstd::string, std::liststd::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 类模板定义templateclass T, class Container std::dequeT class queue { private: Container _con; };A. 模板参数templateclass T, class Contanier std::deque T 解释1. T为储存的数据类型可以指定为int、char、string、double ...2. Container为底层容器类型默认是deque T B. 成员变量Container _con;解释1. Container这通常是一个模板参数它代表了底层使用的是什么数据结构。例如 std::dequeint 或 std::listint 。2. _con这是实例化的成员变量名。3.2 成员函数实现#include iostream #include deque #include list #include string templateclass T, class Container std::dequeT 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_queueint 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_queuestd::string, std::liststd::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; }打印结果如下所示既然看到这里了不妨关注点赞收藏感谢大家若有问题请指正。