尧图网站建设 
1. 项目概述为什么要从零手写stack和queue先把话说清楚大多数C学习者对STL的认知停留在“会用”层面——知道std::stack有push、pop、topstd::queue有front、back、push、pop写OJ题时无脑调接口就行。但一旦面试官问“栈的底层默认用的是哪种容器”“queue的pop为什么不返回元素”“适配器模式在这两个容器上是怎么体现的”——很多人就卡壳了。这恰恰说明一个问题只调用STL接口不等于理解STL。从零实现stack和queue不是为了造轮子而是要把“封装”“复用”“适配”这三件事彻底啃透。这个项目的价值非常直接它逼着你去思考底层容器的选择、接口语义的设计、元素生命周期的管理以及如何用你手头已经有的数据结构比如动态数组、链表去拼出两个看起来“很简单”的容器。等你亲手写完你会突然发现std::stack和std::queue本身并没有存储数据的能力它们只是站在别的容器肩膀上做了个“门面”。这个认知比背十遍接口列表都值钱。适合谁来做三类人一是C刚入门、想搞清楚STL容器之间关系的初学者二是准备面试、需要手写数据结构的求职者三是已经会用STL但总感觉底层模糊、想补课的人。接下来的内容不会跳过任何细节从数据结构选型讲到接口实现再讲到测试与坑点全部按实操路径展开你跟着敲一遍就能跑。2. 底层数据结构选型栈和队列“本身”不存数据2.1 先理解适配器模式std::stack在C标准里的定位是“容器适配器”container adapter。什么意思它自己不管理内存、自己不存储元素而是封装另一个容器把那个容器的接口“翻译”成栈的语义。比如你让deque做底层那么push进去实际上调的是deque的push_backpop调的是deque的pop_back。底层的deque怎么扩容、怎么分段存储栈完全不关心。这个设计思路放到工程里就是典型的“依赖倒置”上层只依赖抽象接口不依赖具体实现。你在写代码的时候栈只需要知道“我能在尾部放元素、能在尾部取元素”至于是数组还是链表那是另外一回事。所以从零实现的第一步不是急着写push而是先确定底层用哪种结构。不同结构决定了后续所有代码的写法。2.2 数组 vs 链表从实现成本角度对比对于栈来说底层结构可以是动态数组也可以是单向链表。数组的优势是缓存友好、随机访问O(1)、不需要为每个元素单独分配节点内存缺点是需要扩容扩容时会拷贝/移动元素。链表则反过来每个元素一个节点插入删除不需要移动已有元素但每个节点多存一个指针内存碎片化更严重而且频繁new节点有额外开销。对于队列情况稍微复杂一点。如果用数组做底层直接往尾部push_back、头部pop_front这个操作在普通动态数组上是O(n)的——因为头部弹出后所有元素要往前挪。所以工程上经典的方案是“循环数组”用两个下标front和rear维护头尾数组满了再扩容。链表实现队列则非常自然头部指向队首节点尾部指向队尾节点push在尾节点后面追加pop删头节点全都是O(1)。我在实际写这个项目时选了“双轨方案”栈用动态数组实现队列用链表实现。这样两个容器恰好覆盖了“连续内存”和“节点内存”两种典型场景比两个都用同一种底层更有教学价值。3. 手写动态数组版Stack接口、扩容与内存管理3.1 类骨架与核心成员设计先定义栈的对外接口我这里的版本只保留最关键的操作push入栈、pop出栈、top取栈顶、empty判空、size取大小。模板参数保留一个T表示元素类型。底层我用一个T*指针指向动态数组加上capacity容量和size_当前元素个数两个整形成员。template typename T class MyStack { private: T* data; size_t capacity; size_t size_; void resize(); // 扩容函数 public: MyStack(); ~MyStack(); MyStack(const MyStack other); // 拷贝构造 MyStack operator(const MyStack other); // 拷贝赋值 void push(const T value); void pop(); T top(); const T top() const; bool empty() const; size_t size() const; };这里有几个地方容易忽略。第一top()必须提供const和非const两个版本否则const MyStack对象没法取栈顶。第二size_t用于容量和大小避免负数比较的坑。第三一旦类内部有裸指针就必须遵循“三五法则”把拷贝构造、拷贝赋值、析构函数全部写全否则默认的浅拷贝会让两个栈对象指向同一块内存析构时双重释放直接崩。3.2 push扩容的完整逻辑push的核心不只是把元素放进去还要在数组满的时候扩容。每次扩容我选择翻倍策略——容量从1开始满了就乘2。为什么不用“每次加固定大小”因为动态数组的均摊复杂度分析告诉我们翻倍扩容能让push的均摊代价保持在O(1)每次加固定值均摊代价会变成O(n)。这在《算法导论》的摊还分析里有严格证明实操上也能明显感觉到——数据量一大固定步长扩容反复memcpy卡顿感很强。扩容步骤分四步申请新内存、拷贝旧元素、释放旧内存、更新指针和容量。这里要特别强调一个版本差异在C11之前扩容时应该用copy语义逐个拷贝构造新数组C11之后如果元素是可移动的最好用std::move搬家避免深拷贝的开销。我写的示例用拷贝构造简单清晰你在工程代码里可以参考std::vector的做法用std::move_if_noexcept做优化。void resize() { size_t newCapacity capacity * 2; T* newData new T[newCapacity]; for (size_t i 0; i size_; i) { newData[i] data[i]; } delete[] data; data newData; capacity newCapacity; }注意一个细节如果T的拷贝构造函数可能抛异常上面的写法是“强异常安全”的——先在新内存上完成所有拷贝再释放旧内存。万一拷贝到一半抛异常旧数组的原始数据还在对象处于未修改状态这是一条很好的工程习惯。3.3 top和pop的边界处理及返回值设计top()就是返回data[size_ - 1]但必须记住一个原则调用top之前必须先判空否则就是访问越界。我在实现里没有做内部断言因为这属于“用户错误”而不是“库内部错误”STL也是这么处理的——未定义行为由调用者负责。但是在教学版本里我加了一个assert(!empty())调试阶段能快速暴露问题发布版本可以用NDEBUG关掉。pop()只需要执行--size_真正的难点在于“要不要析构被弹出的元素”。如果元素类型是int、double这种普通类型少做一步无所谓。但如果T是std::string或者持有资源的对象直接减size_会让那个对象“活”在数组末尾但外部已经无法访问——这就成了资源泄漏窗口。严谨做法是调用data[size_ - 1].~T()手动析构被逻辑上移除的元素然后把size_减一。我在实现里采用了手动析构的方式宁可多写一行也不留隐患。void pop() { if (empty()) return; // 这里也可以选择assert data[size_ - 1].~T(); --size_; }3.4 拷贝控制让栈能安全复制因为底层是裸指针默认拷贝构造会执行“逐成员拷贝”结果是两个栈的data指向同一块堆内存。任何一个先析构另一个就悬空。所以必须写深拷贝。MyStack(const MyStack other) : capacity(other.capacity), size_(other.size_), data(new T[other.capacity]) { for (size_t i 0; i size_; i) { data[i] other.data[i]; } } MyStack operator(const MyStack other) { if (this ! other) { MyStack tmp(other); // 拷贝并交换异常安全 std::swap(data, tmp.data); std::swap(capacity, tmp.capacity); std::swap(size_, tmp.size_); } return *this; }赋值这里用的是经典的“copy-and-swap”惯用法先构造临时对象tmp再把临时对象的数据和当前对象交换tmp离开作用域时自动释放旧内存。这个写法有三个好处不需要判断self-assignment的特殊情况虽然我还是加了不会产生内存泄漏且全程是强异常安全保证。写这个项目之前我对拷贝赋值的理解一直停留在“先delete再new”写完才体会到copy-and-swap的优雅。4. 手写链表版Queue节点设计、入队出队与遍历4.1 队列的链表节点与类布局队列的底层如果用链表最核心的是维护两个指针front指向队首节点rear指向队尾节点。有了rear入队操作才能做到O(1)——否则每次都从头遍历到尾巴复杂度退化成O(n)。节点本身用一个结构体里面存数据和一个指向下一个节点的指针。template typename T struct QueueNode { T data; QueueNode* next; QueueNode(const T val) : data(val), next(nullptr) {} }; template typename T class MyQueue { private: QueueNodeT* front; QueueNodeT* rear; size_t size_; public: MyQueue(); ~MyQueue(); MyQueue(const MyQueue other); MyQueue operator(const MyQueue other); void push(const T value); void pop(); T front(); T back(); bool empty() const; size_t size() const; };4.2 push与pop的指针流转细节入队操作用一句话概括先把新节点挂在rear后面再让rear指向新节点。这个顺序不能写反。如果先移动rear再挂指针原来的尾节点就找不到新节点了。特殊情况下队列为空时front和rear都是nullptr此时新节点既是队首又是队尾两个指针都要指向它。void push(const T value) { QueueNodeT* newNode new QueueNodeT(value); if (empty()) { front newNode; rear newNode; } else { rear-next newNode; rear newNode; } size_; }出队操作则相反核心是保存下一个节点的地址删除当前节点更新front。这里的顺序陷阱在于如果你先delete front再尝试访问front-next程序直接崩——因为内存已经释放了。正确写法是先用临时指针保存后继节点。void pop() { if (empty()) return; QueueNodeT* temp front; front front-next; if (front nullptr) { rear nullptr; // 队列已空rear也要置空 } delete temp; --size_; }上面这个if (front nullptr) rear nullptr非常关键。很多人写链表队列只更新front一旦最后一个元素被弹出rear还指向那个已经被释放的节点——下次push时rear-next newNode就是对悬空指针解引用直接收获segfault。这类“尾巴指针忘记置空”的问题是链表队列最容易踩的坑没有之一。4.3 front和back的陷阱返回引用还是值front()返回的是队首元素的引用可以直接q.front() 42修改元素。这是STL的标准行为。但很多人初写时习惯返回一个拷贝导致修改不生效。大家记住一个原则读取用值、修改用引用。所以front()和back()都要写成返回T的版本再额外加一个const T版本供只读场景使用。还有一个很容易忽略的点链表的back()操作依赖rear指针。只要你的push正确维护了rearback()就是O(1)。但如果漏维护你只能从front遍历到尾队列的所有操作就全变形了。我在测试阶段专门验证过这一点——写一个循环入队10000个元素随机调用back()比较值能迅速发现rear是否掉链子。4.4 队列的析构与内存释放链表队列的析构必须逐个删除节点不能用delete front一刀切——那只会删除第一个节点后面的节点全部泄漏。标准做法是循环遍历用一个cur指针从front出发每次都先保存next再删除当前节点。~MyQueue() { while (front) { QueueNodeT* next front-next; delete front; front next; } rear nullptr; size_ 0; }你可能会想为什么不直接用delete[]因为链表节点不是连续内存它们由new逐个分配散布在堆的不同位置。delete[]只能作用于连续数组用在这里是未定义行为。这点和栈的动态数组底层完全不同写的时候一定要区分清楚。5. 栈和队列的统一封装STL风格的跨容器复用5.1 双容器对比总结两个容器写完之后放在一起对比一下很多概念会更清楚。我用表格把关键差异列出来方便你复习对比维度动态数组版Stack链表版Queue底层结构连续存储的动态数组非连续的链表节点入栈/入队操作数组尾部追加可能触发扩容在rear节点后追加每次分配新节点出栈/出队操作仅修改size_并手动析构删除头节点并更新front内存碎片低连续分配高频繁小块分配拷贝成本深拷贝整个数组深拷贝所有节点首尾访问O(1)O(1)靠front和rear指针5.2 从模板参数到容器适配器写到这里你可能已经发现一个规律不管是栈还是队列核心操作的实现逻辑和底层数据结构是解耦的。STL的std::stack实际上就是做了这样的设计——它接受两个模板参数第二个参数是底层容器类型默认用std::deque。如果你愿意完全可以把你自己实现的MyStack改造成一个接受容器模板参数的适配器让它既能用动态数组也能用链表做底层。这个改造的思路是这样的先把栈的操作映射成底层容器的操作——push对应底层容器的尾部插入pop对应尾部删除top对应尾部元素。再把底层容器类型做成模板参数只要它提供了这些接口就能被栈复用。这就是“容器适配器”的本质。你不用真的改造完但一定要在脑子里想通这一层它对理解STL的架构非常关键。5.3 我为什么建议两个版本都保留写这个项目时我也纠结过栈用动态数组、队列用链表两个底层都不一样是不是风格不统一后来想明白了这种不统一恰恰是教学价值所在。栈的数组实现让你看到“扩容”和“元素生命周期管理”队列的链表实现让你看到“指针维护”和“内存释放”。如果你两个都用数组循环队列的判空判满逻辑会引入额外复杂度两个都用链表则看不到连续内存的均摊扩容过程。这种交叉对比的写法能让两种数据结构的特点都被放大、被看到。6. 完整代码整合与测试用例设计6.1 栈的完整代码与运行示例下面是完整的栈实现包含所有关键方法。我建议你直接抄一遍不要复制粘贴亲手敲一遍才能记住那些容易出错的细节。#include iostream #include cassert template typename T class MyStack { private: T* data; size_t capacity; size_t size_; void resize() { size_t newCapacity capacity * 2; T* newData new T[newCapacity]; for (size_t i 0; i size_; i) { newData[i] data[i]; } delete[] data; data newData; capacity newCapacity; } public: MyStack() : data(new T[1]), capacity(1), size_(0) {} ~MyStack() { delete[] data; } 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(const MyStack other) { if (this ! other) { MyStack tmp(other); std::swap(data, tmp.data); std::swap(capacity, tmp.capacity); std::swap(size_, tmp.size_); } return *this; } void push(const T value) { if (size_ capacity) { resize(); } data[size_] value; size_; } void pop() { assert(!empty()); data[size_ - 1].~T(); --size_; } T top() { assert(!empty()); return data[size_ - 1]; } const T top() const { assert(!empty()); return data[size_ - 1]; } bool empty() const { return size_ 0; } size_t size() const { return size_; } };6.2 队列的完整代码与运行示例template typename T struct QueueNode { T data; QueueNode* next; QueueNode(const T val) : data(val), next(nullptr) {} }; template typename T class MyQueue { private: QueueNodeT* front; QueueNodeT* rear; size_t size_; public: MyQueue() : front(nullptr), rear(nullptr), size_(0) {} ~MyQueue() { while (front) { QueueNodeT* next front-next; delete front; front next; } } MyQueue(const MyQueue other) : front(nullptr), rear(nullptr), size_(0) { QueueNodeT* cur other.front; while (cur) { push(cur-data); cur cur-next; } } MyQueue operator(const MyQueue other) { if (this ! other) { MyQueue tmp(other); std::swap(front, tmp.front); std::swap(rear, tmp.rear); std::swap(size_, tmp.size_); } return *this; } void push(const T value) { QueueNodeT* newNode new QueueNodeT(value); if (empty()) { front newNode; } else { rear-next newNode; } rear newNode; size_; } void pop() { assert(!empty()); QueueNodeT* temp front; front front-next; if (front nullptr) { rear nullptr; } delete temp; --size_; } T front() { assert(!empty()); return front-data; } T back() { assert(!empty()); return rear-data; } const T front() const { assert(!empty()); return front-data; } const T back() const { assert(!empty()); return rear-data; } bool empty() const { return size_ 0; } size_t size() const { return size_; } };6.3 测试用例的设计思路写完代码不是终点测试才是验证正确性的关键。针对栈我设计了三个维度边界测试空栈调用top和pop是否触发断言、扩容测试压入10000个元素中途随机暂停检查size和top是否一致、拷贝测试拷贝一个栈、修改原栈确认副本不受影响。针对队列我设计了一个“猴子测试”随机执行100万次push和pop同时用一个标准库std::queue作为对照组每次操作后对比两个容器的size、front、back是否完全一致。这个对比测试非常有效跑一遍就能发现rear没置空、pop顺序错误之类的问题。int main() { MyStackint s; for (int i 0; i 1000; i) s.push(i); std::cout Stack size: s.size() std::endl; while (!s.empty()) { std::cout s.top() ; s.pop(); } std::cout std::endl; MyQueueint q; for (int i 0; i 10; i) q.push(i); std::cout Queue front: q.front() , back: q.back() std::endl; while (!q.empty()) { std::cout q.front() ; q.pop(); } std::cout std::endl; return 0; }7. 常见问题与排查技巧实录7.1 空栈调用top导致的随机崩溃我最开始写的栈没有assert空栈时top()会直接访问data[-1]——等一下size_是size_t无符号类型size_ - 1在size_为0时不是-1而是18446744073709551615。这个数作为数组下标轻则垃圾值重则段错误。这个坑特别隐蔽因为只在特定情况下触发。我建议在top()和pop()中保留assert并且在调试时故意调一次空栈的top确认断言能触发。这个习惯能帮你在一开始就拦截大量越界问题。7.2 队列pop后rear指针悬挂前面重点提过pop删掉最后一个节点后如果不把rear置为nullptr下一次push就会通过悬空指针访问已释放内存。我在测试时遇到的表现是第一次崩溃发生在删除最后一个元素后的下一次push但报错位置不在push里面而是在rear-next newNode这一行附近。排查方法其实很简单——在pop函数里、删除节点之后检查front nullptr时是否同步处理rear。多花几分钟把这个分支想清楚后面能省好几个小时的调试时间。7.3 扩容时元素拷贝的异常安全动态数组扩容时如果直接delete[] data再new新数组然后逐个拷贝那么拷贝过程中一旦抛异常旧数据已经没了对象处于半毁状态。这就是为什么我在扩容函数里坚持“先新后旧”先分配新内存、完成拷贝、再释放旧数组。同时拷贝构造函数的new T[newCapacity]如果失败抛出bad_alloc对象自身不会受影响因为旧指针还没被覆盖。这套逻辑写起来不复杂但对异常安全的理解非常关键。7.4 push引用类型元素时的临时对象陷阱如果栈的元素类型是std::stringpush(hello)这种写法会隐式构造一个临时std::string然后拷贝放入栈中。这个操作本身没问题但如果你写的push版本只有T而没有const T重载编译器会报错。更隐蔽的是如果你在push里写的是data[size_] value;而value是个临时对象理论上更应该用移动语义而非拷贝语义。C11之后push可以考虑提供T重载或者用std::forward做完美转发减少不必要的拷贝。这个话题可以展开很多但在这个入门项目里至少先保证const T版本能正确处理不泄漏即可。7.5 测试标准库对照组的价值做队列测试时用std::queue做对照是我觉得最实用的技巧。因为标准库经过了千锤百炼行为可以作为参照物。具体操作方法是在每次push或pop之后都说一句if (q.front() ! stdq.front())检查是否一致。这个对照设计不需要肉眼盯输出程序自己会告诉你哪里有偏差。我建议你写任何数据结构练手项目时都用这个思路它比打印日志高效得多。8. 基于STL接口的扩展思考从实现到理解做完这个项目之后我最大的感受是写出能跑的stack和queue只是及格能讲清楚每一个接口为什么这么设计才是真正的收获。比如stack::pop为什么不返回被弹出的元素因为返回值和修改容器状态这两件事放在同一个函数里要么先返回值再修改状态导致返回值拷贝成本高要么先修改状态再返回值导致返回值已经无效。STL选择让pop只负责删除top负责读取把两件事拆开让使用者自己组合。这个设计初看不起眼细想才发现它兼顾了效率、安全性和语义清晰度。再比如队列的emplace、栈的swap这些接口我这次没有全部实现但接口留了一部分。如果你学有余力可以继续往下补emplace是原地构造元素避免临时对象拷贝swap是交换两个容器的内部指针复杂度O(1)。把这些接口一条条补完你对STL容器适配器的理解会又上一个台阶。从零实现stack和queue难的不是语法而是“用工程思维去设计一个简单的东西”。数组扩容时怎么保证异常安全链表删除时怎么避免指针悬挂拷贝赋值时怎么做到强异常保证——这些问题的答案靠调库是永远学不到的。我强烈建议你把这份代码完整跑通、把测试用例改一改、多压几个边界场景比如空容器操作、大量元素反复入出队、拷贝后修改原容器。每改一个场景你都会对STL多一分敬畏也会对自己的代码多一分掌控力。最后分享一个我在实操中一直用的习惯写手写容器时永远准备一个标准库版本在旁边做对照。不是为了抄而是为了“对答案”。哪一天你发现自己的输出和标准库不一致那恭喜你你找到了一个值得研究的细节——这往往是理解最深、进步最大的时刻。 从零手写C++ stack和queue：容器适配器底层实现与工程实践
1. 项目概述为什么要从零手写stack和queue先把话说清楚大多数C学习者对STL的认知停留在“会用”层面——知道std::stack有push、pop、topstd::queue有front、back、push、pop写OJ题时无脑调接口就行。但一旦面试官问“栈的底层默认用的是哪种容器”“queue的pop为什么不返回元素”“适配器模式在这两个容器上是怎么体现的”——很多人就卡壳了。这恰恰说明一个问题只调用STL接口不等于理解STL。从零实现stack和queue不是为了造轮子而是要把“封装”“复用”“适配”这三件事彻底啃透。这个项目的价值非常直接它逼着你去思考底层容器的选择、接口语义的设计、元素生命周期的管理以及如何用你手头已经有的数据结构比如动态数组、链表去拼出两个看起来“很简单”的容器。等你亲手写完你会突然发现std::stack和std::queue本身并没有存储数据的能力它们只是站在别的容器肩膀上做了个“门面”。这个认知比背十遍接口列表都值钱。适合谁来做三类人一是C刚入门、想搞清楚STL容器之间关系的初学者二是准备面试、需要手写数据结构的求职者三是已经会用STL但总感觉底层模糊、想补课的人。接下来的内容不会跳过任何细节从数据结构选型讲到接口实现再讲到测试与坑点全部按实操路径展开你跟着敲一遍就能跑。2. 底层数据结构选型栈和队列“本身”不存数据2.1 先理解适配器模式std::stack在C标准里的定位是“容器适配器”container adapter。什么意思它自己不管理内存、自己不存储元素而是封装另一个容器把那个容器的接口“翻译”成栈的语义。比如你让deque做底层那么push进去实际上调的是deque的push_backpop调的是deque的pop_back。底层的deque怎么扩容、怎么分段存储栈完全不关心。这个设计思路放到工程里就是典型的“依赖倒置”上层只依赖抽象接口不依赖具体实现。你在写代码的时候栈只需要知道“我能在尾部放元素、能在尾部取元素”至于是数组还是链表那是另外一回事。所以从零实现的第一步不是急着写push而是先确定底层用哪种结构。不同结构决定了后续所有代码的写法。2.2 数组 vs 链表从实现成本角度对比对于栈来说底层结构可以是动态数组也可以是单向链表。数组的优势是缓存友好、随机访问O(1)、不需要为每个元素单独分配节点内存缺点是需要扩容扩容时会拷贝/移动元素。链表则反过来每个元素一个节点插入删除不需要移动已有元素但每个节点多存一个指针内存碎片化更严重而且频繁new节点有额外开销。对于队列情况稍微复杂一点。如果用数组做底层直接往尾部push_back、头部pop_front这个操作在普通动态数组上是O(n)的——因为头部弹出后所有元素要往前挪。所以工程上经典的方案是“循环数组”用两个下标front和rear维护头尾数组满了再扩容。链表实现队列则非常自然头部指向队首节点尾部指向队尾节点push在尾节点后面追加pop删头节点全都是O(1)。我在实际写这个项目时选了“双轨方案”栈用动态数组实现队列用链表实现。这样两个容器恰好覆盖了“连续内存”和“节点内存”两种典型场景比两个都用同一种底层更有教学价值。3. 手写动态数组版Stack接口、扩容与内存管理3.1 类骨架与核心成员设计先定义栈的对外接口我这里的版本只保留最关键的操作push入栈、pop出栈、top取栈顶、empty判空、size取大小。模板参数保留一个T表示元素类型。底层我用一个T*指针指向动态数组加上capacity容量和size_当前元素个数两个整形成员。template typename T class MyStack { private: T* data; size_t capacity; size_t size_; void resize(); // 扩容函数 public: MyStack(); ~MyStack(); MyStack(const MyStack other); // 拷贝构造 MyStack operator(const MyStack other); // 拷贝赋值 void push(const T value); void pop(); T top(); const T top() const; bool empty() const; size_t size() const; };这里有几个地方容易忽略。第一top()必须提供const和非const两个版本否则const MyStack对象没法取栈顶。第二size_t用于容量和大小避免负数比较的坑。第三一旦类内部有裸指针就必须遵循“三五法则”把拷贝构造、拷贝赋值、析构函数全部写全否则默认的浅拷贝会让两个栈对象指向同一块内存析构时双重释放直接崩。3.2 push扩容的完整逻辑push的核心不只是把元素放进去还要在数组满的时候扩容。每次扩容我选择翻倍策略——容量从1开始满了就乘2。为什么不用“每次加固定大小”因为动态数组的均摊复杂度分析告诉我们翻倍扩容能让push的均摊代价保持在O(1)每次加固定值均摊代价会变成O(n)。这在《算法导论》的摊还分析里有严格证明实操上也能明显感觉到——数据量一大固定步长扩容反复memcpy卡顿感很强。扩容步骤分四步申请新内存、拷贝旧元素、释放旧内存、更新指针和容量。这里要特别强调一个版本差异在C11之前扩容时应该用copy语义逐个拷贝构造新数组C11之后如果元素是可移动的最好用std::move搬家避免深拷贝的开销。我写的示例用拷贝构造简单清晰你在工程代码里可以参考std::vector的做法用std::move_if_noexcept做优化。void resize() { size_t newCapacity capacity * 2; T* newData new T[newCapacity]; for (size_t i 0; i size_; i) { newData[i] data[i]; } delete[] data; data newData; capacity newCapacity; }注意一个细节如果T的拷贝构造函数可能抛异常上面的写法是“强异常安全”的——先在新内存上完成所有拷贝再释放旧内存。万一拷贝到一半抛异常旧数组的原始数据还在对象处于未修改状态这是一条很好的工程习惯。3.3 top和pop的边界处理及返回值设计top()就是返回data[size_ - 1]但必须记住一个原则调用top之前必须先判空否则就是访问越界。我在实现里没有做内部断言因为这属于“用户错误”而不是“库内部错误”STL也是这么处理的——未定义行为由调用者负责。但是在教学版本里我加了一个assert(!empty())调试阶段能快速暴露问题发布版本可以用NDEBUG关掉。pop()只需要执行--size_真正的难点在于“要不要析构被弹出的元素”。如果元素类型是int、double这种普通类型少做一步无所谓。但如果T是std::string或者持有资源的对象直接减size_会让那个对象“活”在数组末尾但外部已经无法访问——这就成了资源泄漏窗口。严谨做法是调用data[size_ - 1].~T()手动析构被逻辑上移除的元素然后把size_减一。我在实现里采用了手动析构的方式宁可多写一行也不留隐患。void pop() { if (empty()) return; // 这里也可以选择assert data[size_ - 1].~T(); --size_; }3.4 拷贝控制让栈能安全复制因为底层是裸指针默认拷贝构造会执行“逐成员拷贝”结果是两个栈的data指向同一块堆内存。任何一个先析构另一个就悬空。所以必须写深拷贝。MyStack(const MyStack other) : capacity(other.capacity), size_(other.size_), data(new T[other.capacity]) { for (size_t i 0; i size_; i) { data[i] other.data[i]; } } MyStack operator(const MyStack other) { if (this ! other) { MyStack tmp(other); // 拷贝并交换异常安全 std::swap(data, tmp.data); std::swap(capacity, tmp.capacity); std::swap(size_, tmp.size_); } return *this; }赋值这里用的是经典的“copy-and-swap”惯用法先构造临时对象tmp再把临时对象的数据和当前对象交换tmp离开作用域时自动释放旧内存。这个写法有三个好处不需要判断self-assignment的特殊情况虽然我还是加了不会产生内存泄漏且全程是强异常安全保证。写这个项目之前我对拷贝赋值的理解一直停留在“先delete再new”写完才体会到copy-and-swap的优雅。4. 手写链表版Queue节点设计、入队出队与遍历4.1 队列的链表节点与类布局队列的底层如果用链表最核心的是维护两个指针front指向队首节点rear指向队尾节点。有了rear入队操作才能做到O(1)——否则每次都从头遍历到尾巴复杂度退化成O(n)。节点本身用一个结构体里面存数据和一个指向下一个节点的指针。template typename T struct QueueNode { T data; QueueNode* next; QueueNode(const T val) : data(val), next(nullptr) {} }; template typename T class MyQueue { private: QueueNodeT* front; QueueNodeT* rear; size_t size_; public: MyQueue(); ~MyQueue(); MyQueue(const MyQueue other); MyQueue operator(const MyQueue other); void push(const T value); void pop(); T front(); T back(); bool empty() const; size_t size() const; };4.2 push与pop的指针流转细节入队操作用一句话概括先把新节点挂在rear后面再让rear指向新节点。这个顺序不能写反。如果先移动rear再挂指针原来的尾节点就找不到新节点了。特殊情况下队列为空时front和rear都是nullptr此时新节点既是队首又是队尾两个指针都要指向它。void push(const T value) { QueueNodeT* newNode new QueueNodeT(value); if (empty()) { front newNode; rear newNode; } else { rear-next newNode; rear newNode; } size_; }出队操作则相反核心是保存下一个节点的地址删除当前节点更新front。这里的顺序陷阱在于如果你先delete front再尝试访问front-next程序直接崩——因为内存已经释放了。正确写法是先用临时指针保存后继节点。void pop() { if (empty()) return; QueueNodeT* temp front; front front-next; if (front nullptr) { rear nullptr; // 队列已空rear也要置空 } delete temp; --size_; }上面这个if (front nullptr) rear nullptr非常关键。很多人写链表队列只更新front一旦最后一个元素被弹出rear还指向那个已经被释放的节点——下次push时rear-next newNode就是对悬空指针解引用直接收获segfault。这类“尾巴指针忘记置空”的问题是链表队列最容易踩的坑没有之一。4.3 front和back的陷阱返回引用还是值front()返回的是队首元素的引用可以直接q.front() 42修改元素。这是STL的标准行为。但很多人初写时习惯返回一个拷贝导致修改不生效。大家记住一个原则读取用值、修改用引用。所以front()和back()都要写成返回T的版本再额外加一个const T版本供只读场景使用。还有一个很容易忽略的点链表的back()操作依赖rear指针。只要你的push正确维护了rearback()就是O(1)。但如果漏维护你只能从front遍历到尾队列的所有操作就全变形了。我在测试阶段专门验证过这一点——写一个循环入队10000个元素随机调用back()比较值能迅速发现rear是否掉链子。4.4 队列的析构与内存释放链表队列的析构必须逐个删除节点不能用delete front一刀切——那只会删除第一个节点后面的节点全部泄漏。标准做法是循环遍历用一个cur指针从front出发每次都先保存next再删除当前节点。~MyQueue() { while (front) { QueueNodeT* next front-next; delete front; front next; } rear nullptr; size_ 0; }你可能会想为什么不直接用delete[]因为链表节点不是连续内存它们由new逐个分配散布在堆的不同位置。delete[]只能作用于连续数组用在这里是未定义行为。这点和栈的动态数组底层完全不同写的时候一定要区分清楚。5. 栈和队列的统一封装STL风格的跨容器复用5.1 双容器对比总结两个容器写完之后放在一起对比一下很多概念会更清楚。我用表格把关键差异列出来方便你复习对比维度动态数组版Stack链表版Queue底层结构连续存储的动态数组非连续的链表节点入栈/入队操作数组尾部追加可能触发扩容在rear节点后追加每次分配新节点出栈/出队操作仅修改size_并手动析构删除头节点并更新front内存碎片低连续分配高频繁小块分配拷贝成本深拷贝整个数组深拷贝所有节点首尾访问O(1)O(1)靠front和rear指针5.2 从模板参数到容器适配器写到这里你可能已经发现一个规律不管是栈还是队列核心操作的实现逻辑和底层数据结构是解耦的。STL的std::stack实际上就是做了这样的设计——它接受两个模板参数第二个参数是底层容器类型默认用std::deque。如果你愿意完全可以把你自己实现的MyStack改造成一个接受容器模板参数的适配器让它既能用动态数组也能用链表做底层。这个改造的思路是这样的先把栈的操作映射成底层容器的操作——push对应底层容器的尾部插入pop对应尾部删除top对应尾部元素。再把底层容器类型做成模板参数只要它提供了这些接口就能被栈复用。这就是“容器适配器”的本质。你不用真的改造完但一定要在脑子里想通这一层它对理解STL的架构非常关键。5.3 我为什么建议两个版本都保留写这个项目时我也纠结过栈用动态数组、队列用链表两个底层都不一样是不是风格不统一后来想明白了这种不统一恰恰是教学价值所在。栈的数组实现让你看到“扩容”和“元素生命周期管理”队列的链表实现让你看到“指针维护”和“内存释放”。如果你两个都用数组循环队列的判空判满逻辑会引入额外复杂度两个都用链表则看不到连续内存的均摊扩容过程。这种交叉对比的写法能让两种数据结构的特点都被放大、被看到。6. 完整代码整合与测试用例设计6.1 栈的完整代码与运行示例下面是完整的栈实现包含所有关键方法。我建议你直接抄一遍不要复制粘贴亲手敲一遍才能记住那些容易出错的细节。#include iostream #include cassert template typename T class MyStack { private: T* data; size_t capacity; size_t size_; void resize() { size_t newCapacity capacity * 2; T* newData new T[newCapacity]; for (size_t i 0; i size_; i) { newData[i] data[i]; } delete[] data; data newData; capacity newCapacity; } public: MyStack() : data(new T[1]), capacity(1), size_(0) {} ~MyStack() { delete[] data; } 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(const MyStack other) { if (this ! other) { MyStack tmp(other); std::swap(data, tmp.data); std::swap(capacity, tmp.capacity); std::swap(size_, tmp.size_); } return *this; } void push(const T value) { if (size_ capacity) { resize(); } data[size_] value; size_; } void pop() { assert(!empty()); data[size_ - 1].~T(); --size_; } T top() { assert(!empty()); return data[size_ - 1]; } const T top() const { assert(!empty()); return data[size_ - 1]; } bool empty() const { return size_ 0; } size_t size() const { return size_; } };6.2 队列的完整代码与运行示例template typename T struct QueueNode { T data; QueueNode* next; QueueNode(const T val) : data(val), next(nullptr) {} }; template typename T class MyQueue { private: QueueNodeT* front; QueueNodeT* rear; size_t size_; public: MyQueue() : front(nullptr), rear(nullptr), size_(0) {} ~MyQueue() { while (front) { QueueNodeT* next front-next; delete front; front next; } } MyQueue(const MyQueue other) : front(nullptr), rear(nullptr), size_(0) { QueueNodeT* cur other.front; while (cur) { push(cur-data); cur cur-next; } } MyQueue operator(const MyQueue other) { if (this ! other) { MyQueue tmp(other); std::swap(front, tmp.front); std::swap(rear, tmp.rear); std::swap(size_, tmp.size_); } return *this; } void push(const T value) { QueueNodeT* newNode new QueueNodeT(value); if (empty()) { front newNode; } else { rear-next newNode; } rear newNode; size_; } void pop() { assert(!empty()); QueueNodeT* temp front; front front-next; if (front nullptr) { rear nullptr; } delete temp; --size_; } T front() { assert(!empty()); return front-data; } T back() { assert(!empty()); return rear-data; } const T front() const { assert(!empty()); return front-data; } const T back() const { assert(!empty()); return rear-data; } bool empty() const { return size_ 0; } size_t size() const { return size_; } };6.3 测试用例的设计思路写完代码不是终点测试才是验证正确性的关键。针对栈我设计了三个维度边界测试空栈调用top和pop是否触发断言、扩容测试压入10000个元素中途随机暂停检查size和top是否一致、拷贝测试拷贝一个栈、修改原栈确认副本不受影响。针对队列我设计了一个“猴子测试”随机执行100万次push和pop同时用一个标准库std::queue作为对照组每次操作后对比两个容器的size、front、back是否完全一致。这个对比测试非常有效跑一遍就能发现rear没置空、pop顺序错误之类的问题。int main() { MyStackint s; for (int i 0; i 1000; i) s.push(i); std::cout Stack size: s.size() std::endl; while (!s.empty()) { std::cout s.top() ; s.pop(); } std::cout std::endl; MyQueueint q; for (int i 0; i 10; i) q.push(i); std::cout Queue front: q.front() , back: q.back() std::endl; while (!q.empty()) { std::cout q.front() ; q.pop(); } std::cout std::endl; return 0; }7. 常见问题与排查技巧实录7.1 空栈调用top导致的随机崩溃我最开始写的栈没有assert空栈时top()会直接访问data[-1]——等一下size_是size_t无符号类型size_ - 1在size_为0时不是-1而是18446744073709551615。这个数作为数组下标轻则垃圾值重则段错误。这个坑特别隐蔽因为只在特定情况下触发。我建议在top()和pop()中保留assert并且在调试时故意调一次空栈的top确认断言能触发。这个习惯能帮你在一开始就拦截大量越界问题。7.2 队列pop后rear指针悬挂前面重点提过pop删掉最后一个节点后如果不把rear置为nullptr下一次push就会通过悬空指针访问已释放内存。我在测试时遇到的表现是第一次崩溃发生在删除最后一个元素后的下一次push但报错位置不在push里面而是在rear-next newNode这一行附近。排查方法其实很简单——在pop函数里、删除节点之后检查front nullptr时是否同步处理rear。多花几分钟把这个分支想清楚后面能省好几个小时的调试时间。7.3 扩容时元素拷贝的异常安全动态数组扩容时如果直接delete[] data再new新数组然后逐个拷贝那么拷贝过程中一旦抛异常旧数据已经没了对象处于半毁状态。这就是为什么我在扩容函数里坚持“先新后旧”先分配新内存、完成拷贝、再释放旧数组。同时拷贝构造函数的new T[newCapacity]如果失败抛出bad_alloc对象自身不会受影响因为旧指针还没被覆盖。这套逻辑写起来不复杂但对异常安全的理解非常关键。7.4 push引用类型元素时的临时对象陷阱如果栈的元素类型是std::stringpush(hello)这种写法会隐式构造一个临时std::string然后拷贝放入栈中。这个操作本身没问题但如果你写的push版本只有T而没有const T重载编译器会报错。更隐蔽的是如果你在push里写的是data[size_] value;而value是个临时对象理论上更应该用移动语义而非拷贝语义。C11之后push可以考虑提供T重载或者用std::forward做完美转发减少不必要的拷贝。这个话题可以展开很多但在这个入门项目里至少先保证const T版本能正确处理不泄漏即可。7.5 测试标准库对照组的价值做队列测试时用std::queue做对照是我觉得最实用的技巧。因为标准库经过了千锤百炼行为可以作为参照物。具体操作方法是在每次push或pop之后都说一句if (q.front() ! stdq.front())检查是否一致。这个对照设计不需要肉眼盯输出程序自己会告诉你哪里有偏差。我建议你写任何数据结构练手项目时都用这个思路它比打印日志高效得多。8. 基于STL接口的扩展思考从实现到理解做完这个项目之后我最大的感受是写出能跑的stack和queue只是及格能讲清楚每一个接口为什么这么设计才是真正的收获。比如stack::pop为什么不返回被弹出的元素因为返回值和修改容器状态这两件事放在同一个函数里要么先返回值再修改状态导致返回值拷贝成本高要么先修改状态再返回值导致返回值已经无效。STL选择让pop只负责删除top负责读取把两件事拆开让使用者自己组合。这个设计初看不起眼细想才发现它兼顾了效率、安全性和语义清晰度。再比如队列的emplace、栈的swap这些接口我这次没有全部实现但接口留了一部分。如果你学有余力可以继续往下补emplace是原地构造元素避免临时对象拷贝swap是交换两个容器的内部指针复杂度O(1)。把这些接口一条条补完你对STL容器适配器的理解会又上一个台阶。从零实现stack和queue难的不是语法而是“用工程思维去设计一个简单的东西”。数组扩容时怎么保证异常安全链表删除时怎么避免指针悬挂拷贝赋值时怎么做到强异常保证——这些问题的答案靠调库是永远学不到的。我强烈建议你把这份代码完整跑通、把测试用例改一改、多压几个边界场景比如空容器操作、大量元素反复入出队、拷贝后修改原容器。每改一个场景你都会对STL多一分敬畏也会对自己的代码多一分掌控力。最后分享一个我在实操中一直用的习惯写手写容器时永远准备一个标准库版本在旁边做对照。不是为了抄而是为了“对答案”。哪一天你发现自己的输出和标准库不一致那恭喜你你找到了一个值得研究的细节——这往往是理解最深、进步最大的时刻。