我见过太多人把 STL 里的stack和queue当成“装数据的盒子”push 一下、pop 一下用起来比谁都熟。可一旦被问到“这俩的底层到底是什么”“让你自己实现一个能不能写出来”不少人就卡住了。原因其实很统一我们习惯了站在使用者的角度去看容器却很少站到实现者的角度去思考它的内存布局、边界条件、生命周期管理。这个项目不复杂但很值得认真做一遍——从一个空类开始手写 stack 和 queue 的全部关键操作把模板、动态内存、拷贝语义、边界判断这些东西一次性捋清楚。这篇文章就围绕“从零实现”展开。我会先从两个容器的设计本质上拆解思路再分别给出 stack 和 queue 的完整实现代码配合测试和避坑经验。不论你是准备面试还是想把 STL 底层搞得更透这篇都适合你慢慢读。1. 为什么要从零实现 stack 和 queue1.1 先看清 STL 里的 stack/queue 到底是什么很多人对std::stack和std::queue有一个误解认为它们是独立的数据结构。实际上它们都是容器适配器container adapter。也就是说它们本身不管理内存也不存储数据而是通过包装另一个容器默认是std::deque来提供受限的接口。std::stack只让你操作栈顶push 从顶入、pop 从顶出、top 看栈顶。std::queue只让你操作两端push 从队尾入、pop 从队头出、front 看队头、back 看队尾。你看它们把底层容器的“自由度”砍掉了——deque 能提供随机访问但 stack/queue 把这些能力锁了起来只暴露出符合语义的那几个操作。这是接口约束上的典型设计用最少的方法表达最清晰的数据结构语义。从零实现的意义就在这里当你自己动手的时候你才会意识到实现一个 stack 根本不需要从头发明什么新东西——你只需要一个“能存东西、能按顺序访问”的底层结构然后把外部接口限制起来。这个“把底层容器封装成语义明确的适配器”的思路比单纯背几个函数名重要得多。1.2 从零实现能换来什么收获我之所以推荐你亲手写一遍而不是直接打印源码看是因为写的过程中你会被迫回答这几类问题内存管理问题栈的容量不够了怎么办是每次 push 都扩容还是提前预留扩容系数取多少生命周期问题pop 之后被移除的元素它的析构函数是否被调用了对象持有的资源有没有真正释放拷贝语义问题容器被拷贝时是浅拷贝还是深拷贝如果直接复制指针两份“独立”的容器会不会在析构时争抢同一块内存边界条件问题空栈上调用 top 会发生什么队列只有一个元素时 pop会不会把队尾指针弄丢只调用现成 API 的人是永远不会思考这些的。但如果你要写自己的容器这些问题一个个都会冒出来。正因如此“从零实现 stack/queue”才是一个性价比极高的练习项目——它不大但足够的细节密度让你把 C 的内存和对象模型真正串起来。2. 整体设计思路适配器语义与底层容器的取舍2.1 第一步不是写代码是列清楚操作清单动手之前先明确目标。一个合格的 stack 起码要有这些操作操作含义复杂度push(const T)入栈在栈顶插入元素O(1) 摊还pop()出栈移除栈顶元素O(1)top()返回栈顶元素的引用O(1)empty()判断栈是否为空O(1)size()返回栈中元素个数O(1)拷贝构造/赋值深拷贝保证容器独立O(n)析构释放所有资源O(n)queue 的操作类似但把 top 拆成了 front 和 back操作含义复杂度push(const T)入队在队尾插入元素O(1)pop()出队移除队头元素O(1)front()返回队头元素的引用O(1)back()返回队尾元素的引用O(1)empty()/size()判断空、查数量O(1)把这些接口列出来再动手后面写代码时会省力很多。因为你知道自己在实现什么而不是“写一步看一步”。2.2 底层容器选型数组、链表还是分段连续stack 和 queue 的语义其实对底层结构没有硬性要求只要满足两端插入删除的复杂度需求即可。常见的底层方案有四种底层方案入栈/入队出栈/出队内存局部性扩容代价实现复杂度动态数组vector 式O(1) 摊还O(1)很好拷贝旧数据中等双向链表list 式O(1)O(1)差无扩容但每节点有指针开销较高环形缓冲区O(1) 摊还O(1)很好需重新排列数据高分段连续deque 式O(1) 摊还O(1)好不需要整体搬移非常高STL 默认选择deque核心原因是它能在两端高效插入删除同时内存局部性又比链表好——扩容时它不用像 vector 那样搬移所有元素只需要新分配一段 buffer 并连接起来。这个设计精妙但实现起来非常复杂。从零实现的角度我建议分两条路线stack 用动态数组实现和 vector 的内存管理方式一致逻辑直观扩容时拷贝元素的机制也容易讲清楚。queue 用链表实现同时我会在后面的章节额外讲一下环形缓冲区的思路让你看到第二种方案的优缺点。这样安排你既能看到“连续内存”路径的实现细节也能对比“节点式”结构带来的内存管理差异。两种结构都过一遍手比只盯着一种强太多。2.3 模板设计从一开始就支持泛型既然是模仿 STL模板是必须的。用模板的好处很直接一份代码能承载 int、string、自定义对象等任意类型。类定义写成template typename T class MyStack { // ... };但这也带来一些代价。比如某些类型没有默认构造函数或者拷贝成本很高这些都会影响底层内存管理策略的选择。所以我会在实现时重点考虑“如何避免对 T 的额外要求”。换句话说只要 T 支持拷贝构造和拷贝赋值我的容器就应该能正常工作。另外一个细节成员命名。我习惯在成员变量后面加_后缀例如capacity_、size_用来区分形参和成员。这是很多 C 工程里的约定让代码一眼就能看出哪些是成员、哪些是局部变量。3. 从零实现 stack完整代码与关键操作拆解3.1 动态数组版 MyStack 的整体框架我用动态数组来实现 stack。整体结构是这样的data_指向堆上数组的指针真正存储元素的地方。capacity_当前已经分配的内存能容纳多少元素。size_栈里当前有多少个元素。这三个成员构成一个完整的动态数组容器。size_永远小于等于capacity_当两者相等时下一次 push 必须扩容。基础版本如下#include iostream #include stdexcept template typename T class MyStack { private: T* data_; size_t capacity_; size_t size_; public: explicit MyStack(size_t cap 16) : data_(new T[cap]), capacity_(cap), size_(0) {} ~MyStack() { delete[] data_; } // 禁用拷贝先不后面会给出正确做法 MyStack(const MyStack) delete; MyStack operator(const MyStack) delete; void push(const T value) { if (size_ capacity_) { grow(); } data_[size_] value; } void pop() { if (empty()) { throw std::runtime_error(stack underflow: pop from empty stack); } --size_; } T top() { if (empty()) { throw std::runtime_error(stack empty: no top element); } return data_[size_ - 1]; } const T top() const { if (empty()) { throw std::runtime_error(stack empty: no top element); } return data_[size_ - 1]; } bool empty() const { return size_ 0; } size_t size() const { return size_; } private: void grow() { size_t new_capacity capacity_ * 2; T* new_data new T[new_capacity]; for (size_t i 0; i size_; i) { new_data[i] data_[i]; } delete[] data_; data_ new_data; capacity_ new_capacity; } };这段代码把核心操作都实现了。注意几个关键细节构造函数里的explicit是为了避免隐式转换。比如MyStackint s 100;这种写法可能会误导读者加上explicit之后必须写成MyStackint s(100);意图更清晰。pop()只做了--size_没有真正销毁栈顶对象。原因很简单我们用new T[]分配数组时所有元素从一开始就构造好了数组不销毁它们的生命周期就不会结束。减少size_只是把它们“遮蔽”起来后续 push 时会用赋值运算符覆盖旧值。这种写法对常规类型完全没问题但严格意义上对象占用的资源没有被提前释放。我后面会给出更严格的实现。top()有 const 版本和非 const 版本。非 const 版本允许调用方修改栈顶元素const 版本用于只读场景。这是 STL 中非常常见的双版本模式。3.2 扩容机制与拷贝语义的坑grow()里我选择了capacity_ * 2也就是每次翻倍。为什么是 2 而不是别的数这里有一个摊还复杂度的经典论证假设从 1 开始按 2 倍扩容到 n总共会拷贝1 2 4 ... n/2 n ≈ 2n次也就是说push n 个元素的总拷贝量是 O(n)平均到每次 push 是 O(1)。如果按固定大小扩容比如每次加 16那总拷贝量会变成 O(n²)平均成本就不是 O(1) 了。但拷贝构造和赋值运算符被我禁用 delete这意味着栈可以被创建、使用、销毁但不能被拷贝。这在功能上是不完整的。为什么我要先禁用因为如果直接使用默认的拷贝行为data_指针会被逐字节复制两个 MyStack 对象会指向同一块内存析构时就会发生double free——同一块内存被释放两次程序直接崩溃。正确的做法是深拷贝。拷贝构造需要分配新内存逐一复制元素赋值运算符需要先处理“自赋值”和“异常安全”的问题。一个常见的写法是copy-and-swap 惯用法#include algorithm template typename T class MyStack { private: T* data_; size_t capacity_; size_t size_; void swap(MyStack other) noexcept { std::swap(data_, other.data_); std::swap(capacity_, other.capacity_); std::swap(size_, other.size_); } public: MyStack(const MyStack other) : data_(new T[other.capacity_]), capacity_(other.capacity_), size_(other.size_) { for (size_t i 0; i size_; i) { data_[i] other.data_[i]; } } MyStack operator(MyStack other) { swap(other); return *this; } // 其余方法同上 };这里赋值运算符的形参不是const MyStack而是直接按值传MyStack other。这样other是从实参拷贝出来的临时对象swap 之后旧数据被装进了这个临时对象函数结束时自动析构完成资源清理。如果实参拷贝过程中抛异常赋值操作就整体失败原对象状态不受影响。这就是 copy-and-swap 的优雅之处用拷贝构造来保证异常安全。3.3 进阶用 placement new 让容器更严谨前面的实现虽然很好理解但有一个明显的局限new T[cap]要求 T 必须支持默认构造。如果 T 没有默认构造函数代码就无法编译。而且用赋值运算符覆盖旧值本质上是对“活着的对象”进行赋值而不是构造新对象。更严谨的做法是只分配内存不构造对象push 时用 placement new 构造pop 时手动调用析构。关键代码如下template typename T class MyStack { private: T* data_; size_t capacity_; size_t size_; void grow() { size_t new_capacity capacity_ * 2; T* new_data static_castT*(::operator new(sizeof(T) * new_capacity)); size_t i 0; try { for (; i size_; i) { new (new_data[i]) T(data_[i]); // 拷贝构造而不是赋值 } } catch (...) { for (size_t j 0; j i; j) { new_data[j].~T(); } ::operator delete(new_data); throw; } for (size_t j 0; j size_; j) { data_[j].~T(); } ::operator delete(data_); data_ new_data; capacity_ new_capacity; } public: explicit MyStack(size_t cap 16) : data_(static_castT*(::operator new(sizeof(T) * cap))), capacity_(cap), size_(0) {} ~MyStack() { for (size_t i 0; i size_; i) { data_[i].~T(); } ::operator delete(data_); } void push(const T value) { if (size_ capacity_) { grow(); } new (data_[size_]) T(value); // placement new size_; } void pop() { if (empty()) { throw std::runtime_error(stack underflow); } --size_; data_[size_].~T(); // 手动析构 } // top/empty/size 同前 };::operator new(sizeof(T) * n)只分配裸内存不调用构造函数new (data_[size_]) T(value)在指定位置上构造对象data_[size_].~T()显式调用析构函数。这一套组合拳让容器可以存放没有默认构造函数的类型也让 pop 真正释放了对象持有的资源。代价是代码复杂度明显提高。我的建议是先把第一版搞懂、跑通再升级到这一版。学习路径本身比直接抄一个“最强版本”更重要。3.4 测试 MyStack不只测功能更要测边界写测试时不要只验证“能 push 能 pop”。真正的边界测试长这样int main() { MyStackint stack; // 空栈状态检查 std::cout empty: stack.empty() std::endl; // 1 std::cout size: stack.size() std::endl; // 0 // 连续压入触发多次扩容 for (int i 1; i 100; i) { stack.push(i); } std::cout after push 100: size stack.size() // 100 top stack.top() std::endl; // 100 // 边 pop 边看 top while (!stack.empty()) { int topVal stack.top(); stack.pop(); std::cout pop topVal std::endl; } // 空栈 top/pop 应该抛异常 try { stack.pop(); } catch (const std::exception e) { std::cout caught: e.what() std::endl; } // 拷贝独立性测试 MyStackint copy stack; // 空栈拷贝 for (int i 0; i 5; i) { copy.push(i); } MyStackint assigned; assigned copy; assigned.top() 100; // 修改副本不影响原对象 std::cout copy top copy.top() assigned top assigned.top() std::endl; return 0; }跑起来之后重点观察几件事扩容是否正常、pop 后 size 是否正确递减、空栈异常是否被抛出、拷贝出来的栈是否和原栈完全独立。这些测试点覆盖了大部分实现里容易出 bug 的地方。4. 从零实现 queue链表核心操作与环形缓冲区对比4.1 用链表实现 queue两个指针撑起全部操作queue 和 stack 最大的不同在于queue 需要两端操作。stack 只需要操作栈顶一端但 queue 的 push 在队尾、pop 在队头、front 要看队头、back 要看队尾。如果我用动态数组实现 queue队头出队时就会面临“前面空出来但后面满了”的尴尬局面必须引入环形缓冲或者移动数据。而用链表实现情况会变得很简单每个节点包含数据和下一个节点的指针front_指向队头节点back_指向队尾节点。push 时在链表尾部挂新节点pop 时摘掉头节点。完整实现如下#include iostream #include stdexcept template typename T class MyQueue { private: struct Node { T data_; Node* next_; Node(const T data, Node* next nullptr) : data_(data), next_(next) {} }; Node* front_; Node* back_; size_t size_; public: MyQueue() : front_(nullptr), back_(nullptr), size_(0) {} ~MyQueue() { while (front_ ! nullptr) { Node* temp front_; front_ front_-next_; delete temp; } } MyQueue(const MyQueue other) : front_(nullptr), back_(nullptr), size_(0) { Node* cur other.front_; while (cur ! nullptr) { push(cur-data_); cur cur-next_; } } MyQueue operator(MyQueue other) { std::swap(front_, other.front_); std::swap(back_, other.back_); std::swap(size_, other.size_); return *this; } void push(const T value) { Node* new_node new Node(value); if (back_ nullptr) { front_ back_ new_node; } else { back_-next_ new_node; back_ new_node; } size_; } void pop() { if (empty()) { throw std::runtime_error(queue underflow: pop from empty queue); } Node* old_front front_; front_ front_-next_; if (front_ nullptr) { back_ nullptr; } delete old_front; --size_; } T front() { if (empty()) { throw std::runtime_error(queue empty: no front element); } return front_-data_; } const T front() const { if (empty()) { throw std::runtime_error(queue empty: no front element); } return front_-data_; } T back() { if (empty()) { throw std::runtime_error(queue empty: no back element); } return back_-data_; } const T back() const { if (empty()) { throw std::runtime_error(queue empty: no back element); } return back_-data_; } bool empty() const { return size_ 0; } size_t size() const { return size_; } };这个实现里最需要留意的地方是pop()中的这个细节front_ front_-next_; if (front_ nullptr) { back_ nullptr; }当队列只有一个元素时pop 之后front_变成nullptr但此时back_还指着那个已被删除的节点。如果不把back_也置空下一次push时就会访问悬空指针程序崩溃。这个 bug 非常经典我见过不少人在手写队列时翻车在这个地方。另外operator用了 copy-and-swap。MyQueue other按值传入相当于自动完成了深拷贝三个 swap 交换成员之后旧数据被临时对象带走了函数结束时自动析构。这样写异常安全和自赋值问题一次全解决。4.2 链表 vs 环形缓冲区两种 queue 方案的深度对比链表方案最大的优势是实现直观、节点生命周期清晰。每个节点独立分配push 时创建新节点pop 时删除旧节点不需要担心扩容和元素搬移。但它的缺点也很明显每个节点都要通过new单独分配内存这些零散的堆分配导致内存碎片化而且访问节点时的缓存局部性很差。当队列频繁 push/pop 时每次都要 malloc/free性能会明显下降。相比之下环形缓冲区用一个连续数组模拟队列head_和tail_两个索引在数组里“转圈”。核心思路是push 时把元素写到tail_然后tail_ (tail_ 1) % capacity_pop 时读取head_然后head_ (head_ 1) % capacity_。这个取模操作让索引到数组末尾时自动回到开头形成“环”。环形缓冲区最头疼的地方是扩容。数组满了之后你不能直接把数组翻倍复制就完事——因为当前队列的头可能在任意位置元素在逻辑上是“绕圈”排列的。扩容时必须把旧元素重新排列到新数组的前面逻辑上仍然保持队头在前、队尾在后。结合上一章提到的 placement new 知识你可以写出一个能支持任意类型的 RingQueue但代码量会比链表方案多不少。从实际取舍来看如果是教学、面试或快速原型链表方案优先逻辑清晰、不容易出错。如果是性能敏感的高频入队出队场景环形缓冲区更合适。在 C 里STL 的std::queue默认用std::deque其实就相当于“分段连续”的环形缓冲区优化版这才是它性能好的真正原因。4.3 扩展思考用两个栈实现队列既然手写了 stack你还可以玩一个经典题目用两个栈实现队列。思路是这样的栈 A 负责入队push 直接压入 A。栈 B 负责出队当 B 为空时把 A 的所有元素依次 pop 并 push 进 B然后从 B 的栈顶弹出就等价于从队头出队。这个技巧很有意思因为两个 LIFO 结构叠起来竟然能模拟出 FIFO 的行为。实测下来平均时间复杂度依然是 O(1)只有 A 往 B 倒数据的那一瞬间是 O(n) 的摊还下来完全可接受。理解了这篇实现的 stack再去做这道题会非常轻松这里先留给你自己试一试。5. 常见问题与排查技巧实录5.1 浅拷贝导致的双重释放这是手写容器时最容易踩的坑。现象是程序运行到析构时直接报double free or corruption。原因就是我前面说的默认的拷贝构造是逐字节复制两个对象的data_指针指向同一块内存析构时两次delete[]同一地址。排查技巧很简单在类里临时禁用拷贝构造和赋值运算符如果崩溃消失基本可以断定是浅拷贝问题。修复方案也很唯一实现深拷贝。要么手动写拷贝构造和赋值运算符要么用 copy-and-swap 一劳永逸。5.2 空容器上的 undefined behaviorSTL 的std::stack::top()在栈为空时是未定义行为不会帮你做检查。但自己实现的容器如果也这样照搬测试时很容易出现莫名其妙的崩溃。我推荐的做法是显式抛异常比如throw std::runtime_error(stack empty)。虽然现场会多一次分支判断但它能帮你快速暴露逻辑错误。这个取舍在实际工程中很值得宁可慢一点也不能让未定义行为蛰伏在代码里。5.3 模板编译报错的定位思路手写模板类时最常见的编译错误是“no default constructor exists for class X”或者“cannot assign”。原因往往不是你的逻辑错了而是你底层用的new T[]对类型提出了额外要求。当 T 没有默认构造函数时new T[cap]无法编译。遇到这种情况先别慌检查两个方向你是不是用了new T[]如果是换成::operator new placement new 方案参考 3.3 节。你的自定义类型是否缺少拷贝构造或拷贝赋值模板实例化时所有用到的方法都会被编译即使你没调用编译器也会检查其合法性。这类报错信息往往很长但真正的有效信息在第一个error位置往那儿找效率最高。5.4 性能对比自实现 vs STL我用一个简单的程序压了十万次 push/pop得出了几个参考数据不同机器会有差异但趋势一致容器10万次 push/pop 耗时内存分配次数自实现动态数组 stack较低扩容仅十几次STL stack (deque)略高但极稳分批分配自实现链表 queue较高10万次 new/deleteSTL queue (deque)中等分批分配结论很明显链表的单次操作虽然也是 O(1)但常数很大因为每次 push 都涉及一次堆分配。这就是为什么 STL 的 stack/queue 默认都用 deque 而不是 list——连续内存的访问效率远高于零散的链表节点。自己做性能测试时记得把编译器的优化选项打开比如-O2否则测出来的是调试模式的数据参考价值不大。一些实在的心得把这两个容器从头实现一遍之后我最大的感受是STL 看似简单的接口背后藏着相当多的设计决策。比如为什么 queue 不用 vector因为 vector 在头部删除是 O(n)。为什么不用 list因为 list 每个节点单独分配内存缓存不友好。而 deque 通过分段连续存储兼顾了两端的操作效率和访问局部性。这些结论如果你只看教科书是记不牢的但亲手写一遍代码、压一次性能就全通了。如果你想把练习再往上推一步我建议你试试这几个方向给 stack 增加emplace接口用变参模板直接构造元素给 queue 增加移动构造和移动赋值减少拷贝开销或者把底层容器策略做成模板参数模拟 STL 容器适配器的设计方式。每做一个你都会对 C 的泛型和对象模型有更深一层理解。最后说一点实在的这篇里的代码是为了教学清晰而精简过的用来面试和自学完全够。如果你要在正式生产项目里用直接用std::stack和std::queue就好了不要重复造轮子。造轮子的意义在于弄懂轮子而不在于替换轮子。