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

C++入门自学Day14-- Stack和Queue的自实现（适配器）

news 2025/8/20 7:51:38

 往期内容回顾  

           Queue介绍和使用  

           Stack介绍和使用

           String, Vector, List 复习

           List类型的自实现

          List类型（初识）

          Vector类的自实现

         Vector类（注意事项）

          初识Vector

          String类的自实现

         String类的使用（续）  

         String类（续）

         String类（初识）

C++ 容器适配器自实现（Stack & Queue）

前言

        在掌握了 string、vector（连续内存）、list（节点容器）之后，我们再看 栈（Stack） 与 队列（Queue） 会更容易：它们在 STL 中并不是“容器”，而是 容器适配器（Container Adapter）——基于一个可用作底层的顺序容器，只暴露特定的接口与语义。

 Stack（栈）：后进先出（LIFO）

典型操作：push、pop、top

 Queue（队列）：先进先出（FIFO）

典型操作：push、pop（从头弹）、front、ba

标准库默认用 deque 作为底层，因为它的双端插删性能均衡。本文将从零实现 my_stack 与 my_queue，并解释设计取舍、异常安全、迭代器失效与可替换底层容器的约束。

主要内容

  1. 1、适配器思想与底层容器约束

  2. 2、my_stack：接口、约束、实现与测试

  3. 3、my_queue：接口、约束、实现与测试

  4. 4、复杂度、异常安全、迭代器/引用有效性

  5. 5、可替换底层容器：deque vs vector vs list

  6. 6、常见坑位与工程化建议

  7. 总结：为何“用组合而非继承”

一、适配器思想与底层容器约束

适配器的核心：不自己管理存储，只组合一个“底层容器”，并将接口受限为“栈语义/队列语义”。

这要求底层容器满足最小能力集合（接口约束）：

  • Stack 底层容器需要：

    back() / push_back() / pop_back() / empty() / size()

    （典型可用：deque<T>、vector<T>、list<T>）

  • Queue 底层容器需要：

    front() / back() / push_back() / pop_front() / empty() / size()

    （典型可用：deque<T>、list<T>；vector<T> 不可用 —— 没有 pop_front()）

标准库 std::stack/std::queue 默认 deque<T>，也允许自定义容器，只要满足上述接口。

二、my_stack 的实现

2.1 设计要点

  • 按标准库风格提供：top / push / emplace / pop / empty / size / swap

  • 不提供迭代器与遍历接口（保持“栈语义”的束缚）

  • 接口时间复杂度与异常安全以底层容器为准

  • 采用组合（一个成员 Container _con;）

2.2 代码（C++14+ 版本，适配 

deque/vector/list）

#include <deque>
#include <utility>
#include <type_traits>template<class T, class Container = std::deque<T>>
class my_stack {
public:using value_type      = T;using container_type  = Container;using size_type       = typename Container::size_type;using reference       = typename Container::reference;using const_reference = typename Container::const_reference;my_stack() = default;explicit my_stack(const Container& cont)  : c_(cont) {}explicit my_stack(Container&& cont)       : c_(std::move(cont)) {}bool empty() const noexcept { return c_.empty(); }size_type size() const noexcept { return c_.size(); }reference       top()       { return c_.back(); }const_reference top() const { return c_.back(); }void push(const value_type& v)  { c_.push_back(v); }void push(value_type&& v)       { c_.push_back(std::move(v)); }template<class... Args>decltype(auto) emplace(Args&&... args) {return c_.emplace_back(std::forward<Args>(args)...);}void pop() { c_.pop_back(); }void swap(my_stack& other)noexcept(noexcept(std::swap(c_, other.c_))) {using std::swap;swap(c_, other.c_);}private:Container c_;
};

2.3 快速测试

#include <vector>
#include <list>
#include <iostream>int main() {my_stack<int> s1;                 // 默认 deques1.push(1); s1.push(2); s1.push(3);std::cout << s1.top() << "\n";    // 3s1.pop();std::cout << s1.top() << "\n";    // 2my_stack<int, std::vector<int>> s2; // vector 也可作 Stack 底层s2.emplace(42);std::cout << s2.top() << "\n";    // 42my_stack<int, std::list<int>> s3;   // list 也可作 Stack 底层s3.push(7);std::cout << s3.top() << "\n";    // 7
}

三、my_queue的实现

3.1 设计要点

  • 按标准库风格提供：front / back / push / emplace / pop / empty / size / swap

  • 不提供迭代器与遍历接口（保持“队列语义”的束缚）

  • 底层容器必须支持 push_back / pop_front，这决定了 vector 不可用

3.2 代码（C++14+ 版本，默认 deque，也支持 list）

#include <deque>
#include <utility>template<class T, class Container = std::deque<T>>
class my_queue {
public:using value_type      = T;using container_type  = Container;using size_type       = typename Container::size_type;using reference       = typename Container::reference;using const_reference = typename Container::const_reference;my_queue() = default;explicit my_queue(const Container& cont)  : c_(cont) {}explicit my_queue(Container&& cont)       : c_(std::move(cont)) {}bool empty() const noexcept { return c_.empty(); }size_type size() const noexcept { return c_.size(); }reference       front()       { return c_.front(); }const_reference front() const { return c_.front(); }reference       back()        { return c_.back(); }const_reference back() const  { return c_.back(); }void push(const value_type& v)  { c_.push_back(v); }void push(value_type&& v)       { c_.push_back(std::move(v)); }template<class... Args>decltype(auto) emplace(Args&&... args) {return c_.emplace_back(std::forward<Args>(args)...);}void pop() { c_.pop_front(); }void swap(my_queue& other)noexcept(noexcept(std::swap(c_, other.c_))) {using std::swap;swap(c_, other.c_);}private:Container c_;
};

3.3 快速测试

#include <list>
#include <iostream>int main() {my_queue<int> q;                 // 默认 dequeq.push(10); q.push(20); q.emplace(30);std::cout << q.front() << "," << q.back() << "\n"; // 10,30q.pop();std::cout << q.front() << "\n"; // 20my_queue<int, std::list<int>> ql; // list 可用作 Queue 底层ql.push(1); ql.push(2); ql.pop();std::cout << ql.front() << "\n";  // 2
}

四、复杂度、异常安全、迭代器/引用有效性

4.1 时间复杂度（以默认 deque为参考）

  • Stack：push/pop/top/empty/size → O(1)

  • Queue：push/back/front/pop/empty/size → O(1)

极少数情况下 deque 内部重分配可能引起常数因子的波动，但外部语义仍视作常数时间。

4.2 异常安全

  • push/emplace 可能在分配或构造时抛异常；容器保持自洽，要么成功插入，要么回滚到插入前状态（依赖底层容器保障）。

  • pop 不抛异常（但对空容器调用是未定义行为，建议在 Debug 下断言/检查）。

4.3 迭代器/指针/引用的有效性（适配器本身不暴露迭代器）

  • top()/front()/back() 返回的引用在元素被 pop 后立即失效。

  • push 是否使已有引用失效取决于底层容器：

  • deque：在极少数扩容/重组时，引用/指针可能失效；

    list：节点稳定，绝大多数情况下引用有效（被删节点除外）。

结论：尽快使用 top()/front() 返回的引用，不要长期持有。

五、可替换底层容器：该怎么选？

适配器

推荐默认

备选

说明

Stack

deque<T>

vector<T>/list<T>

三者都能满足 Stack 的需求

Queue

deque<T>

list<T>

不要用 vector，缺 pop_front()

  • deque：两端操作均衡、实现成熟、整体吞吐好 → 首选

  • vector（仅 Stack）：push_back/pop_back/top 很快；但随机插入/头删不适合

  • list：指针/引用稳定、频繁中间插删友好，但节点开销大、局部性差

六、常见坑位与工程化建议

  1. 不要继承底层容器

    适配器语义是“约束接口”，用组合而非继承；继承会把不该暴露的接口也暴露出来，破坏 LIFO/FIFO 语义边界。

  2. 不提供 clear() 是否合适？

    标准 std::stack/queue 不提供 clear()；

    需要清空时可：while(!s.empty()) s.pop(); 或 my_stack<T>().swap(s);。

    自定义适配器可以“加一个 clear()”作为工程便捷，但要清楚与标准差异。

  3. 空容器上的 top()/front()/back()/pop()

    与标准一致：未定义行为。工程里可在 Debug 宏下 assert(!empty()) 防御。

  4. emplace 的价值

    复杂对象构造时，emplace 原地构造避免一次拷贝/移动，异常安全更自然。

  5. 线程安全

    适配器/底层容器都不是线程安全；并发场景须加锁或使用并发队列。

  6. C++20 Concepts（可选）

    你可以用 Concepts 对底层容器做编译期约束，让错误更早暴露（见下）。

七、（可选）用 C++20 Concepts 约束底层容器

#if __cpp_concepts
#include <concepts>template<class C, class T>
concept StackContainer = requires(C c, T v) {{ c.back() } -> std::same_as<typename C::reference>;{ c.push_back(v) };{ c.pop_back() };{ c.empty() } -> std::same_as<bool>;{ c.size() };
};template<class C, class T>
concept QueueContainer = requires(C c, T v) {{ c.front() } -> std::same_as<typename C::reference>;{ c.back()  } -> std::same_as<typename C::reference>;{ c.push_back(v) };{ c.pop_front() };{ c.empty() } -> std::same_as<bool>;{ c.size() };
};// 用法：template<class T, StackContainer<T> Container = std::deque<T>> class my_stack { ... };
#endif

这能让「把 vector 错误地拿去做 queue 底层」直接编译失败，错误更易懂。

总结

  • Stack/Queue 是“适配器”，不是容器：通过组合底层容器并收窄接口来提供 LIFO/FIFO 语义。

  • 关键在接口约束：

    • Stack 需 back/push_back/pop_back；

    • Queue 需 front/back/push_back/pop_front；

      因此 Queue 不能用 vector。

  • 复杂度与异常安全 取决于底层容器；默认 deque 综合表现最好。

  • 迭代器/引用有效性：适配器不提供迭代器；front()/top() 的引用在 pop 后失效，push 的影响以底层容器为准。

  • 工程建议：用组合而非继承；可在 Debug 下断言空栈/空队列的错误；必要时使用 Concepts 约束。

  • 学习意义：通过自实现适配器，你会更透彻地理解 STL 的“以语义约束能力”的设计思想，以及组合优于继承的工程实践。

http://www.lryc.cn/news/625584.html

相关文章：

  • 神经网络中的那些关键设计：从输入输出到参数更新
  • 面试题储备-MQ篇 3-说说你对Kafka的理解
  • 图论\dp 两题
  • 设计模式笔记_行为型_命令模式
  • 【React】事件绑定和组件基础使用
  • 从线性回归到神经网络到自注意力机制 —— 激活函数与参数的演进
  • java基础（十二）redis 日志机制以及常见问题
  • 2025年12大AI测试自动化工具
  • 多模态大模型应用落地：从图文生成到音视频交互的技术选型与实践
  • 【模块系列】STM32W25Q64
  • TDengine IDMP 运维指南（4. 使用 Docker 部署）
  • 第六天～提取Arxml中CAN物理通道信息CANChannel--Physical Channel
  • 5. Dataloader 自定义数据集制作
  • C语言基础:（十八）C语言内存函数
  • java17学习笔记-Deprecate the Applet API for Removal
  • 算法——质数筛法
  • yolov5s.onnx转rk模型以及相关使用详细教程
  • 假设检验的原理
  • python的社区互助养老系统
  • word如何转换为pdf
  • MFC中使用EXCEL的方法之一
  • ios使用saveVideoToPhotosAlbum 保存视频失败提示 invalid video
  • 基于单片机的智能声控窗帘
  • 437. 路径总和 III
  • Qt 插件开发全解析：从接口定义，插件封装，插件调用到插件间的通信
  • SWMM排水管网水力、水质建模及在海绵与水环境中的应用
  • 第5章 高级状态管理
  • 结合BI多维度异常分析（日期-＞ 商家/渠道-＞日期（商家/渠道))
  • 深入理解 CAS：无锁编程的核心基石
  • nginx安装配置教程