1. 项目概述为什么需要手动实现栈和队列在C的日常开发中std::stack和std::queue几乎是信手拈来的工具STL标准模板库已经为我们封装好了稳定高效的实现。那么为什么我们还要“多此一举”地手动去实现它们呢这个问题在我带过的实习生和面试过的候选人中出现的频率相当高。答案远不止于“为了面试”这么简单。手动实现这些基础数据结构是深入理解计算机科学核心思想、锻炼底层编码能力、以及应对特定性能或资源约束场景的必经之路。当你亲手用数组或链表搭建起一个栈处理完边界溢出和空栈访问的每一个细节后你才能真正理解“后进先出”LIFO和“先进先出”FIFO不仅仅是两个抽象概念而是内存操作、函数调用、任务调度等无数场景背后的坚实支柱。对于初学者这是一个绝佳的、从“会用库”到“懂原理”的跨越。你会直面指针操作、内存管理、模板编程和异常安全这些C的核心议题。对于有经验的开发者这更像是一次“返璞归真”的练习能帮你写出更高效、更健壮的代码尤其是在嵌入式、游戏、高频交易等对性能和可控性要求极高的领域自定义的数据结构往往是优化性能的关键。接下来我将结合我十多年的C工程经验带你从零开始一步步构建出工业级强度的栈和队列并深入探讨其中的设计抉择、陷阱规避和性能考量。2. 核心数据结构设计思路与选型在动手写代码之前我们必须做出两个关键的设计决策底层存储容器用什么以及如何管理这个容器的生命周期和容量。这两个选择直接决定了我们实现的栈和队列的性能特性、内存占用和接口易用性。2.1 底层容器选型数组 vs. 链表这是最经典的数据结构选择题。对于栈和队列两者各有优劣。基于数组顺序存储的实现核心思路在堆上分配一块连续的内存空间。对于栈我们维护一个指向栈顶的索引或指针对于队列我们维护队头front和队尾rear两个索引可能还会配合“循环队列”的技巧来复用空间。优势极高的缓存友好性数据在内存中连续存放CPU预取效率高访问速度极快。这是数组最大的优势。内存开销小除了存储元素本身只需要额外的几个整型变量如容量、栈顶索引、队头队尾索引没有链表节点中next指针带来的额外开销。实现简单直观索引操作比指针操作更不容易出错。劣势固定容量创建时需要指定最大容量存在空间浪费或溢出的风险。虽然可以实现动态扩容如std::vector但扩容涉及数据拷贝有性能开销。队列的“假溢出”对于简单数组实现的队列即使数组尾部还有空间但队头移出后空出的位置无法被新元素使用这就是“假溢出”。必须引入“循环队列”的概念来解决。基于链表链式存储的实现核心思路每个元素封装在一个节点Node中节点包含数据域和指向下一个节点的指针。对于栈我们只需维护一个指向链表头即栈顶的指针对于队列则需要维护头指针队头和尾指针队尾。优势动态容量理论上可以无限添加元素直到内存耗尽没有预分配和溢出的烦恼空间利用率高。插入删除高效在已知位置如链表头插入删除节点是O(1)操作非常适合栈和队列的语义。劣势缓存不友好节点在内存中分散存储访问时容易引起缓存缺失遍历性能不如数组。内存开销大每个节点都需要额外的指针开销。对于存储小对象如int这个开销比例会很高。实现稍复杂涉及更多的指针操作容易引入内存泄漏、悬空指针等问题。实操心得在绝大多数通用场景下基于数组的动态扩容实现模拟std::vector是栈的最佳选择因为它平衡了性能和易用性。而对于队列如果对性能有极致要求且能预估最大容量循环数组是最佳选择如果元素数量波动很大或难以预估基于链表的实现则更省心。本次实现为了全面覆盖知识点我将分别展示数组栈、链表栈、循环数组队列和链表队列。2.2 类模板设计与接口定义我们要实现的是通用数据结构必须能够存储任意类型的数据。因此必须使用C的类模板。 接口设计应尽可能向STL看齐这样我们的实现既可以作为学习工具也可以在必要时作为STL的替代品。核心接口包括栈 (Stack)push(入栈),pop(出栈),top(查看栈顶),empty(判空),size(获取大小)。队列 (Queue)push(入队),pop(出队),front(查看队首),back(查看队尾),empty(判空),size(获取大小)。此外我们还需要构造函数、析构函数、拷贝控制成员拷贝构造、拷贝赋值、移动构造、移动赋值来完善资源管理这是体现C功力的地方。3. 基于数组的栈ArrayStack实现详解我们先从相对简单的数组栈开始。这里我们实现一个动态扩容的版本。3.1 类模板声明与成员变量template typename T class ArrayStack { private: T* _data; // 指向堆上数组的指针 size_t _capacity; // 数组的总容量 size_t _top; // 栈顶索引指向下一个可插入的位置 // _top 为 0 表示栈空 _top 为 _capacity 表示栈满需扩容 public: // 构造函数、析构函数及接口声明... };3.2 核心操作push 与动态扩容push操作的核心是检查容量并在必要时扩容。扩容策略直接影响性能。一个常见的策略是容量翻倍类似std::vector这样均摊下来的插入时间复杂度仍是O(1)。template typename T void ArrayStackT::push(const T value) { // 检查是否需要扩容 if (_top _capacity) { // 计算新容量初始容量为0时设为1否则翻倍 size_t newCapacity (_capacity 0) ? 1 : _capacity * 2; // 申请新内存 T* newData new T[newCapacity]; // 注意这里要求T有默认构造函数 // 将旧数据拷贝到新内存 for (size_t i 0; i _top; i) { newData[i] _data[i]; // 调用T的拷贝赋值运算符 } // 释放旧内存 delete[] _data; // 更新指针和容量 _data newData; _capacity newCapacity; } // 在栈顶位置放入新元素 _data[_top] value; // 调用T的拷贝赋值运算符 _top; // 栈顶指针上移 }注意事项这里使用的new T[newCapacity]要求类型T必须具有默认构造函数。对于没有默认构造的类型这种实现会编译失败。更鲁棒的做法是使用operator new分配原始内存然后使用placement new构造对象但这会大大增加实现的复杂性。作为教学实现我们暂且做此约定。此外异常安全也是问题如果在拷贝元素过程中抛出异常会导致内存泄漏。生产级代码需要考虑这些。3.3 核心操作pop 与 toptemplate typename T void ArrayStackT::pop() { if (empty()) { // 处理错误抛出异常或终止程序。这里简单处理。 // throw std::out_of_range(Stack is empty, cannot pop.); return; // 或者不做任何操作 } --_top; // 栈顶指针下移。注意这里并没有销毁对象。 // 对于非平凡类型可能需要显式调用析构函数_data[_top].~T(); } template typename T T ArrayStackT::top() { if (empty()) { throw std::out_of_range(Stack is empty, no top element.); } return _data[_top - 1]; // 返回栈顶元素的引用 } template typename T const T ArrayStackT::top() const { // const 版本用于const对象 if (empty()) { throw std::out_of_range(Stack is empty, no top element.); } return _data[_top - 1]; }实操心得pop操作通常只移动指针并不销毁内存中的对象。这是因为对于内置类型如int或可平凡析构的类型这样做没问题对象占用的内存会在整个数组被释放时回收。但严格来说对于需要管理资源的类型如持有动态内存的类我们应该在pop时显式调用其析构函数以避免资源泄漏。STL的std::stack的pop函数返回void而通过top获取元素部分原因就是为了提供“强异常安全”保证。3.4 构造、析构与拷贝控制Rule of Five这是手动管理资源类的重中之重必须正确处理否则极易导致内存泄漏、重复释放或浅拷贝等问题。template typename T class ArrayStack { public: // 1. 默认构造函数 ArrayStack() : _data(nullptr), _capacity(0), _top(0) {} // 2. 带初始容量的构造函数 explicit ArrayStack(size_t initialCapacity) : _data(new T[initialCapacity]), _capacity(initialCapacity), _top(0) {} // 3. 析构函数 ~ArrayStack() { delete[] _data; // 释放整个数组 } // 4. 拷贝构造函数深拷贝 ArrayStack(const ArrayStack other) : _data(other._capacity 0 ? new T[other._capacity] : nullptr) , _capacity(other._capacity) , _top(other._top) { for (size_t i 0; i _top; i) { _data[i] other._data[i]; // 深拷贝每个元素 } } // 5. 拷贝赋值运算符深拷贝提供强异常安全保证 ArrayStack operator(const ArrayStack other) { if (this ! other) { // 防止自赋值 // 先分配新内存如果失败原对象状态不变 T* newData nullptr; if (other._capacity 0) { newData new T[other._capacity]; for (size_t i 0; i other._top; i) { newData[i] other._data[i]; // 拷贝元素 } } // 成功后再替换和释放旧资源 (copy-and-swap 思想) delete[] _data; _data newData; _capacity other._capacity; _top other._top; } return *this; } // 6. 移动构造函数C11 ArrayStack(ArrayStack other) noexcept : _data(other._data), _capacity(other._capacity), _top(other._top) { other._data nullptr; // 将源对象置于有效但可析构状态 other._capacity 0; other._top 0; } // 7. 移动赋值运算符C11 ArrayStack operator(ArrayStack other) noexcept { if (this ! other) { delete[] _data; // 释放自身资源 _data other._data; _capacity other._capacity; _top other._top; other._data nullptr; other._capacity 0; other._top 0; } return *this; } // ... 其他接口 };实现拷贝控制成员是C资源管理的基本功。遵循“Rule of Three/Five/Zero”原则能有效避免绝大多数内存相关错误。移动语义的加入C11以后可以避免不必要的深拷贝提升性能。4. 基于链表的栈LinkedListStack实现详解链表栈的实现更关注节点的生命期管理。4.1 节点结构与类定义template typename T class LinkedListStack { private: // 内部节点类 struct Node { T data; Node* next; // 节点构造函数方便创建 Node(const T val, Node* nxt nullptr) : data(val), next(nxt) {} // 移动构造版本可选优化性能 Node(T val, Node* nxt nullptr) : data(std::move(val)), next(nxt) {} }; Node* _topNode; // 指向栈顶节点的指针 size_t _size; // 记录元素个数使size()操作为O(1) public: // 接口声明... };4.2 核心操作push 与 pop链表栈的push和pop都是在链表头部进行效率是O(1)。template typename T void LinkedListStackT::push(const T value) { // 创建新节点其next指向当前栈顶 Node* newNode new Node(value, _topNode); // 更新栈顶指针 _topNode newNode; _size; } template typename T void LinkedListStackT::pop() { if (empty()) { throw std::out_of_range(Stack is empty, cannot pop.); } Node* nodeToDelete _topNode; _topNode _topNode-next; // 栈顶指针下移 delete nodeToDelete; // 释放原栈顶节点内存 --_size; } template typename T T LinkedListStackT::top() { if (empty()) { throw std::out_of_range(Stack is empty, no top element.); } return _topNode-data; }链表实现的pop需要显式delete节点这是与数组实现最大的不同也更容易出现内存泄漏。4.3 析构函数与资源释放由于每个节点都是独立new出来的析构函数必须遍历整个链表并释放所有节点。template typename T LinkedListStackT::~LinkedListStack() { // 循环释放所有节点 while (_topNode ! nullptr) { Node* temp _topNode; _topNode _topNode-next; delete temp; } }拷贝构造函数和拷贝赋值运算符也需要深拷贝整个链表这里不再赘述其逻辑是遍历源链表为每个节点创建副本并链接起来。5. 队列的实现循环数组 vs. 链表队列的关键在于高效地在两端进行操作尾插、头删。我们分别用循环数组和链表来实现。5.1 循环数组队列CircularArrayQueue循环数组是解决数组队列“假溢出”问题的经典方案。我们使用两个索引_front和_rear并利用取模运算让它们在数组范围内“循环”。template typename T class CircularArrayQueue { private: T* _data; size_t _capacity; size_t _front; // 指向队首元素 size_t _rear; // 指向队尾的下一个位置即将插入的位置 size_t _size; // 当前元素个数用于区分队满和队空 public: CircularArrayQueue(size_t cap 8) // 默认容量 : _data(new T[cap]), _capacity(cap), _front(0), _rear(0), _size(0) {} ~CircularArrayQueue() { delete[] _data; } bool empty() const { return _size 0; } bool full() const { return _size _capacity; } size_t size() const { return _size; } void push(const T value) { if (full()) { // 队列已满需要扩容。扩容策略更复杂需要搬移元素。 resize(_capacity * 2); } _data[_rear] value; _rear (_rear 1) % _capacity; // 循环 _size; } void pop() { if (empty()) { throw std::out_of_range(Queue is empty, cannot pop.); } _front (_front 1) % _capacity; // 循环 --_size; } T front() { if (empty()) throw std::out_of_range(Queue is empty.); return _data[_front]; } T back() { if (empty()) throw std::out_of_range(Queue is empty.); // rear指向的是下一个空位队尾元素在它的前一个位置 return _data[(_rear - 1 _capacity) % _capacity]; } private: void resize(size_t newCapacity) { T* newData new T[newCapacity]; // 将旧队列中的元素按顺序拷贝到新数组的开头 for (size_t i 0; i _size; i) { newData[i] _data[(_front i) % _capacity]; } delete[] _data; _data newData; _capacity newCapacity; _front 0; // 搬移后队头重置为0 _rear _size; // 队尾指向最后一个元素的下一个位置 } };注意事项循环队列判断“队满”和“队空”是个经典问题。上面我们使用了一个额外的_size变量来记录元素个数这是最简单清晰的方法。另一种常见但不推荐的方法是牺牲一个存储单元约定_rear下一个位置是_front时表示队满_rear _front表示队空。使用_size变量避免了这种混淆代码更易读。5.2 链表队列LinkedListQueue链表队列需要维护头尾两个指针。入队push在尾部进行出队pop在头部进行。template typename T class LinkedListQueue { private: struct Node { T data; Node* next; Node(const T val) : data(val), next(nullptr) {} }; Node* _head; // 指向队首节点 Node* _tail; // 指向队尾节点 size_t _size; public: LinkedListQueue() : _head(nullptr), _tail(nullptr), _size(0) {} ~LinkedListQueue() { while (_head ! nullptr) { Node* temp _head; _head _head-next; delete temp; } } void push(const T value) { Node* newNode new Node(value); if (empty()) { // 队列为空新节点既是头也是尾 _head _tail newNode; } else { // 队列不为空链接到尾部并更新尾指针 _tail-next newNode; _tail newNode; } _size; } void pop() { if (empty()) throw std::out_of_range(Queue is empty.); Node* temp _head; _head _head-next; delete temp; --_size; // 如果弹出后队列为空需要将_tail也置为nullptr防止成为野指针 if (_head nullptr) { _tail nullptr; } } T front() { if (empty()) throw std::out_of_range(Queue is empty.); return _head-data; } T back() { if (empty()) throw std::out_range(Queue is empty.); return _tail-data; } // ... empty(), size() 等方法 };链表队列的实现需要注意边界条件特别是当队列为空或变为空时对_head和_tail指针的维护。6. 性能对比、适用场景与常见问题排查实现完成后我们有必要从工程角度进行复盘和对比。6.1 四种实现的性能与特性对比特性动态数组栈 (ArrayStack)链表栈 (LinkedListStack)循环数组队列 (CircularArrayQueue)链表队列 (LinkedListQueue)push/pop 时间复杂度均摊 O(1)O(1)均摊 O(1)O(1)访问顶部/首部时间复杂度O(1)O(1)O(1)O(1)内存连续性好缓存友好差缓存不友好好缓存友好差缓存不友好额外内存开销小 (容量变量)大 (每个节点一个指针)小 (容量、索引变量)大 (每个节点一个指针)容量管理需动态扩容有拷贝成本动态无浪费需动态扩容有拷贝成本动态无浪费实现复杂度中等 (需处理扩容)简单中等 (需处理循环索引和扩容)简单主要适用场景通用场景元素数量可预估或波动不大元素数量波动极大或对象很大拷贝成本高高性能场景元素数量可预估元素数量波动大或需要频繁在两端操作可轻松扩展为双端队列6.2 典型应用场景举例栈的应用函数调用栈这是栈最经典的用途系统自动管理。表达式求值将中缀表达式转换为后缀表达式逆波兰表达式再用栈求值。括号匹配检查代码中的括号是否成对出现。浏览器的前进后退使用两个栈来实现。深度优先搜索DFS递归的本质就是栈非递归实现也显式用到栈。队列的应用任务调度操作系统中的进程就绪队列、打印队列。消息队列在分布式系统中进行异步通信如RabbitMQ, Kafka的核心抽象。广度优先搜索BFS遍历树或图时使用队列来管理待访问节点。缓存淘汰策略如FIFO先进先出缓存。数据流处理如网络数据包缓冲区。6.3 手动实现中的常见“坑”与排查技巧内存泄漏问题链表实现中pop或析构时忘记delete节点数组实现中扩容后忘记delete[]旧数组。排查使用Valgrind、AddressSanitizer等内存检测工具。养成“new/delete”、“new[]/delete[]”成对出现的编程习惯。技巧优先使用智能指针如std::unique_ptrNode管理节点内存可以极大降低泄漏风险。教学代码为了清晰展示指针操作未使用但生产代码强烈推荐。浅拷贝问题问题未定义拷贝构造函数或拷贝赋值运算符编译器生成的默认版本进行按成员拷贝浅拷贝。当对象持有动态内存如_data指针时两个对象会指向同一块内存析构时会导致重复释放double free。排查程序在拷贝对象后崩溃错误信息常与free()或malloc相关。技巧遵循“Rule of Three/Five”。一旦类需要手动管理资源定义了析构函数就应该同时定义或明确禁止拷贝构造和拷贝赋值。迭代器失效问题在我们的简单实现中未提供迭代器但若提供在push导致扩容数组实现或pop删除节点链表实现后之前获取的迭代器将指向无效内存。技巧文档中必须明确说明哪些操作会导致迭代器失效。参考STL容器的规范。异常安全问题在扩容拷贝元素、或拷贝构造函数拷贝元素时如果T的拷贝赋值/构造函数抛出异常可能导致资源泄漏或对象状态被破坏。技巧使用“copy-and-swap”惯用法来实现拷贝赋值运算符可以提供强异常安全保证。在可能抛出异常的操作前先分配新资源成功后再替换旧资源。循环队列的索引计算错误问题_rear (_rear 1) % _capacity这句代码如果_rear是size_t无符号当_rear为_capacity-1时_rear1等于_capacity取模后为0逻辑正确。但计算队尾元素时(_rear - 1 _capacity) % _capacity如果_rear为0_rear-1会发生下溢对于无符号数会变成一个很大的正数。因此必须加上_capacity再取模。技巧仔细测试边界情况空队列、单元素队列、满队列时的各种操作。手动实现这些基础数据结构就像木匠打磨自己的第一套工具。过程可能繁琐但每一次调试每一次对边界条件的思考都在加深你对程序如何与内存打交道的理解。当你再使用std::stack和std::queue时你看到的将不再是一个黑盒而是一个由精妙指针、索引和内存块构成的清晰图景。这种理解是写出高效、稳健的C代码的基石。
C++手动实现栈与队列：从原理到工业级实现的深度解析
发布时间：2026/7/25 7:55:41
1. 项目概述为什么需要手动实现栈和队列在C的日常开发中std::stack和std::queue几乎是信手拈来的工具STL标准模板库已经为我们封装好了稳定高效的实现。那么为什么我们还要“多此一举”地手动去实现它们呢这个问题在我带过的实习生和面试过的候选人中出现的频率相当高。答案远不止于“为了面试”这么简单。手动实现这些基础数据结构是深入理解计算机科学核心思想、锻炼底层编码能力、以及应对特定性能或资源约束场景的必经之路。当你亲手用数组或链表搭建起一个栈处理完边界溢出和空栈访问的每一个细节后你才能真正理解“后进先出”LIFO和“先进先出”FIFO不仅仅是两个抽象概念而是内存操作、函数调用、任务调度等无数场景背后的坚实支柱。对于初学者这是一个绝佳的、从“会用库”到“懂原理”的跨越。你会直面指针操作、内存管理、模板编程和异常安全这些C的核心议题。对于有经验的开发者这更像是一次“返璞归真”的练习能帮你写出更高效、更健壮的代码尤其是在嵌入式、游戏、高频交易等对性能和可控性要求极高的领域自定义的数据结构往往是优化性能的关键。接下来我将结合我十多年的C工程经验带你从零开始一步步构建出工业级强度的栈和队列并深入探讨其中的设计抉择、陷阱规避和性能考量。2. 核心数据结构设计思路与选型在动手写代码之前我们必须做出两个关键的设计决策底层存储容器用什么以及如何管理这个容器的生命周期和容量。这两个选择直接决定了我们实现的栈和队列的性能特性、内存占用和接口易用性。2.1 底层容器选型数组 vs. 链表这是最经典的数据结构选择题。对于栈和队列两者各有优劣。基于数组顺序存储的实现核心思路在堆上分配一块连续的内存空间。对于栈我们维护一个指向栈顶的索引或指针对于队列我们维护队头front和队尾rear两个索引可能还会配合“循环队列”的技巧来复用空间。优势极高的缓存友好性数据在内存中连续存放CPU预取效率高访问速度极快。这是数组最大的优势。内存开销小除了存储元素本身只需要额外的几个整型变量如容量、栈顶索引、队头队尾索引没有链表节点中next指针带来的额外开销。实现简单直观索引操作比指针操作更不容易出错。劣势固定容量创建时需要指定最大容量存在空间浪费或溢出的风险。虽然可以实现动态扩容如std::vector但扩容涉及数据拷贝有性能开销。队列的“假溢出”对于简单数组实现的队列即使数组尾部还有空间但队头移出后空出的位置无法被新元素使用这就是“假溢出”。必须引入“循环队列”的概念来解决。基于链表链式存储的实现核心思路每个元素封装在一个节点Node中节点包含数据域和指向下一个节点的指针。对于栈我们只需维护一个指向链表头即栈顶的指针对于队列则需要维护头指针队头和尾指针队尾。优势动态容量理论上可以无限添加元素直到内存耗尽没有预分配和溢出的烦恼空间利用率高。插入删除高效在已知位置如链表头插入删除节点是O(1)操作非常适合栈和队列的语义。劣势缓存不友好节点在内存中分散存储访问时容易引起缓存缺失遍历性能不如数组。内存开销大每个节点都需要额外的指针开销。对于存储小对象如int这个开销比例会很高。实现稍复杂涉及更多的指针操作容易引入内存泄漏、悬空指针等问题。实操心得在绝大多数通用场景下基于数组的动态扩容实现模拟std::vector是栈的最佳选择因为它平衡了性能和易用性。而对于队列如果对性能有极致要求且能预估最大容量循环数组是最佳选择如果元素数量波动很大或难以预估基于链表的实现则更省心。本次实现为了全面覆盖知识点我将分别展示数组栈、链表栈、循环数组队列和链表队列。2.2 类模板设计与接口定义我们要实现的是通用数据结构必须能够存储任意类型的数据。因此必须使用C的类模板。 接口设计应尽可能向STL看齐这样我们的实现既可以作为学习工具也可以在必要时作为STL的替代品。核心接口包括栈 (Stack)push(入栈),pop(出栈),top(查看栈顶),empty(判空),size(获取大小)。队列 (Queue)push(入队),pop(出队),front(查看队首),back(查看队尾),empty(判空),size(获取大小)。此外我们还需要构造函数、析构函数、拷贝控制成员拷贝构造、拷贝赋值、移动构造、移动赋值来完善资源管理这是体现C功力的地方。3. 基于数组的栈ArrayStack实现详解我们先从相对简单的数组栈开始。这里我们实现一个动态扩容的版本。3.1 类模板声明与成员变量template typename T class ArrayStack { private: T* _data; // 指向堆上数组的指针 size_t _capacity; // 数组的总容量 size_t _top; // 栈顶索引指向下一个可插入的位置 // _top 为 0 表示栈空 _top 为 _capacity 表示栈满需扩容 public: // 构造函数、析构函数及接口声明... };3.2 核心操作push 与动态扩容push操作的核心是检查容量并在必要时扩容。扩容策略直接影响性能。一个常见的策略是容量翻倍类似std::vector这样均摊下来的插入时间复杂度仍是O(1)。template typename T void ArrayStackT::push(const T value) { // 检查是否需要扩容 if (_top _capacity) { // 计算新容量初始容量为0时设为1否则翻倍 size_t newCapacity (_capacity 0) ? 1 : _capacity * 2; // 申请新内存 T* newData new T[newCapacity]; // 注意这里要求T有默认构造函数 // 将旧数据拷贝到新内存 for (size_t i 0; i _top; i) { newData[i] _data[i]; // 调用T的拷贝赋值运算符 } // 释放旧内存 delete[] _data; // 更新指针和容量 _data newData; _capacity newCapacity; } // 在栈顶位置放入新元素 _data[_top] value; // 调用T的拷贝赋值运算符 _top; // 栈顶指针上移 }注意事项这里使用的new T[newCapacity]要求类型T必须具有默认构造函数。对于没有默认构造的类型这种实现会编译失败。更鲁棒的做法是使用operator new分配原始内存然后使用placement new构造对象但这会大大增加实现的复杂性。作为教学实现我们暂且做此约定。此外异常安全也是问题如果在拷贝元素过程中抛出异常会导致内存泄漏。生产级代码需要考虑这些。3.3 核心操作pop 与 toptemplate typename T void ArrayStackT::pop() { if (empty()) { // 处理错误抛出异常或终止程序。这里简单处理。 // throw std::out_of_range(Stack is empty, cannot pop.); return; // 或者不做任何操作 } --_top; // 栈顶指针下移。注意这里并没有销毁对象。 // 对于非平凡类型可能需要显式调用析构函数_data[_top].~T(); } template typename T T ArrayStackT::top() { if (empty()) { throw std::out_of_range(Stack is empty, no top element.); } return _data[_top - 1]; // 返回栈顶元素的引用 } template typename T const T ArrayStackT::top() const { // const 版本用于const对象 if (empty()) { throw std::out_of_range(Stack is empty, no top element.); } return _data[_top - 1]; }实操心得pop操作通常只移动指针并不销毁内存中的对象。这是因为对于内置类型如int或可平凡析构的类型这样做没问题对象占用的内存会在整个数组被释放时回收。但严格来说对于需要管理资源的类型如持有动态内存的类我们应该在pop时显式调用其析构函数以避免资源泄漏。STL的std::stack的pop函数返回void而通过top获取元素部分原因就是为了提供“强异常安全”保证。3.4 构造、析构与拷贝控制Rule of Five这是手动管理资源类的重中之重必须正确处理否则极易导致内存泄漏、重复释放或浅拷贝等问题。template typename T class ArrayStack { public: // 1. 默认构造函数 ArrayStack() : _data(nullptr), _capacity(0), _top(0) {} // 2. 带初始容量的构造函数 explicit ArrayStack(size_t initialCapacity) : _data(new T[initialCapacity]), _capacity(initialCapacity), _top(0) {} // 3. 析构函数 ~ArrayStack() { delete[] _data; // 释放整个数组 } // 4. 拷贝构造函数深拷贝 ArrayStack(const ArrayStack other) : _data(other._capacity 0 ? new T[other._capacity] : nullptr) , _capacity(other._capacity) , _top(other._top) { for (size_t i 0; i _top; i) { _data[i] other._data[i]; // 深拷贝每个元素 } } // 5. 拷贝赋值运算符深拷贝提供强异常安全保证 ArrayStack operator(const ArrayStack other) { if (this ! other) { // 防止自赋值 // 先分配新内存如果失败原对象状态不变 T* newData nullptr; if (other._capacity 0) { newData new T[other._capacity]; for (size_t i 0; i other._top; i) { newData[i] other._data[i]; // 拷贝元素 } } // 成功后再替换和释放旧资源 (copy-and-swap 思想) delete[] _data; _data newData; _capacity other._capacity; _top other._top; } return *this; } // 6. 移动构造函数C11 ArrayStack(ArrayStack other) noexcept : _data(other._data), _capacity(other._capacity), _top(other._top) { other._data nullptr; // 将源对象置于有效但可析构状态 other._capacity 0; other._top 0; } // 7. 移动赋值运算符C11 ArrayStack operator(ArrayStack other) noexcept { if (this ! other) { delete[] _data; // 释放自身资源 _data other._data; _capacity other._capacity; _top other._top; other._data nullptr; other._capacity 0; other._top 0; } return *this; } // ... 其他接口 };实现拷贝控制成员是C资源管理的基本功。遵循“Rule of Three/Five/Zero”原则能有效避免绝大多数内存相关错误。移动语义的加入C11以后可以避免不必要的深拷贝提升性能。4. 基于链表的栈LinkedListStack实现详解链表栈的实现更关注节点的生命期管理。4.1 节点结构与类定义template typename T class LinkedListStack { private: // 内部节点类 struct Node { T data; Node* next; // 节点构造函数方便创建 Node(const T val, Node* nxt nullptr) : data(val), next(nxt) {} // 移动构造版本可选优化性能 Node(T val, Node* nxt nullptr) : data(std::move(val)), next(nxt) {} }; Node* _topNode; // 指向栈顶节点的指针 size_t _size; // 记录元素个数使size()操作为O(1) public: // 接口声明... };4.2 核心操作push 与 pop链表栈的push和pop都是在链表头部进行效率是O(1)。template typename T void LinkedListStackT::push(const T value) { // 创建新节点其next指向当前栈顶 Node* newNode new Node(value, _topNode); // 更新栈顶指针 _topNode newNode; _size; } template typename T void LinkedListStackT::pop() { if (empty()) { throw std::out_of_range(Stack is empty, cannot pop.); } Node* nodeToDelete _topNode; _topNode _topNode-next; // 栈顶指针下移 delete nodeToDelete; // 释放原栈顶节点内存 --_size; } template typename T T LinkedListStackT::top() { if (empty()) { throw std::out_of_range(Stack is empty, no top element.); } return _topNode-data; }链表实现的pop需要显式delete节点这是与数组实现最大的不同也更容易出现内存泄漏。4.3 析构函数与资源释放由于每个节点都是独立new出来的析构函数必须遍历整个链表并释放所有节点。template typename T LinkedListStackT::~LinkedListStack() { // 循环释放所有节点 while (_topNode ! nullptr) { Node* temp _topNode; _topNode _topNode-next; delete temp; } }拷贝构造函数和拷贝赋值运算符也需要深拷贝整个链表这里不再赘述其逻辑是遍历源链表为每个节点创建副本并链接起来。5. 队列的实现循环数组 vs. 链表队列的关键在于高效地在两端进行操作尾插、头删。我们分别用循环数组和链表来实现。5.1 循环数组队列CircularArrayQueue循环数组是解决数组队列“假溢出”问题的经典方案。我们使用两个索引_front和_rear并利用取模运算让它们在数组范围内“循环”。template typename T class CircularArrayQueue { private: T* _data; size_t _capacity; size_t _front; // 指向队首元素 size_t _rear; // 指向队尾的下一个位置即将插入的位置 size_t _size; // 当前元素个数用于区分队满和队空 public: CircularArrayQueue(size_t cap 8) // 默认容量 : _data(new T[cap]), _capacity(cap), _front(0), _rear(0), _size(0) {} ~CircularArrayQueue() { delete[] _data; } bool empty() const { return _size 0; } bool full() const { return _size _capacity; } size_t size() const { return _size; } void push(const T value) { if (full()) { // 队列已满需要扩容。扩容策略更复杂需要搬移元素。 resize(_capacity * 2); } _data[_rear] value; _rear (_rear 1) % _capacity; // 循环 _size; } void pop() { if (empty()) { throw std::out_of_range(Queue is empty, cannot pop.); } _front (_front 1) % _capacity; // 循环 --_size; } T front() { if (empty()) throw std::out_of_range(Queue is empty.); return _data[_front]; } T back() { if (empty()) throw std::out_of_range(Queue is empty.); // rear指向的是下一个空位队尾元素在它的前一个位置 return _data[(_rear - 1 _capacity) % _capacity]; } private: void resize(size_t newCapacity) { T* newData new T[newCapacity]; // 将旧队列中的元素按顺序拷贝到新数组的开头 for (size_t i 0; i _size; i) { newData[i] _data[(_front i) % _capacity]; } delete[] _data; _data newData; _capacity newCapacity; _front 0; // 搬移后队头重置为0 _rear _size; // 队尾指向最后一个元素的下一个位置 } };注意事项循环队列判断“队满”和“队空”是个经典问题。上面我们使用了一个额外的_size变量来记录元素个数这是最简单清晰的方法。另一种常见但不推荐的方法是牺牲一个存储单元约定_rear下一个位置是_front时表示队满_rear _front表示队空。使用_size变量避免了这种混淆代码更易读。5.2 链表队列LinkedListQueue链表队列需要维护头尾两个指针。入队push在尾部进行出队pop在头部进行。template typename T class LinkedListQueue { private: struct Node { T data; Node* next; Node(const T val) : data(val), next(nullptr) {} }; Node* _head; // 指向队首节点 Node* _tail; // 指向队尾节点 size_t _size; public: LinkedListQueue() : _head(nullptr), _tail(nullptr), _size(0) {} ~LinkedListQueue() { while (_head ! nullptr) { Node* temp _head; _head _head-next; delete temp; } } void push(const T value) { Node* newNode new Node(value); if (empty()) { // 队列为空新节点既是头也是尾 _head _tail newNode; } else { // 队列不为空链接到尾部并更新尾指针 _tail-next newNode; _tail newNode; } _size; } void pop() { if (empty()) throw std::out_of_range(Queue is empty.); Node* temp _head; _head _head-next; delete temp; --_size; // 如果弹出后队列为空需要将_tail也置为nullptr防止成为野指针 if (_head nullptr) { _tail nullptr; } } T front() { if (empty()) throw std::out_of_range(Queue is empty.); return _head-data; } T back() { if (empty()) throw std::out_range(Queue is empty.); return _tail-data; } // ... empty(), size() 等方法 };链表队列的实现需要注意边界条件特别是当队列为空或变为空时对_head和_tail指针的维护。6. 性能对比、适用场景与常见问题排查实现完成后我们有必要从工程角度进行复盘和对比。6.1 四种实现的性能与特性对比特性动态数组栈 (ArrayStack)链表栈 (LinkedListStack)循环数组队列 (CircularArrayQueue)链表队列 (LinkedListQueue)push/pop 时间复杂度均摊 O(1)O(1)均摊 O(1)O(1)访问顶部/首部时间复杂度O(1)O(1)O(1)O(1)内存连续性好缓存友好差缓存不友好好缓存友好差缓存不友好额外内存开销小 (容量变量)大 (每个节点一个指针)小 (容量、索引变量)大 (每个节点一个指针)容量管理需动态扩容有拷贝成本动态无浪费需动态扩容有拷贝成本动态无浪费实现复杂度中等 (需处理扩容)简单中等 (需处理循环索引和扩容)简单主要适用场景通用场景元素数量可预估或波动不大元素数量波动极大或对象很大拷贝成本高高性能场景元素数量可预估元素数量波动大或需要频繁在两端操作可轻松扩展为双端队列6.2 典型应用场景举例栈的应用函数调用栈这是栈最经典的用途系统自动管理。表达式求值将中缀表达式转换为后缀表达式逆波兰表达式再用栈求值。括号匹配检查代码中的括号是否成对出现。浏览器的前进后退使用两个栈来实现。深度优先搜索DFS递归的本质就是栈非递归实现也显式用到栈。队列的应用任务调度操作系统中的进程就绪队列、打印队列。消息队列在分布式系统中进行异步通信如RabbitMQ, Kafka的核心抽象。广度优先搜索BFS遍历树或图时使用队列来管理待访问节点。缓存淘汰策略如FIFO先进先出缓存。数据流处理如网络数据包缓冲区。6.3 手动实现中的常见“坑”与排查技巧内存泄漏问题链表实现中pop或析构时忘记delete节点数组实现中扩容后忘记delete[]旧数组。排查使用Valgrind、AddressSanitizer等内存检测工具。养成“new/delete”、“new[]/delete[]”成对出现的编程习惯。技巧优先使用智能指针如std::unique_ptrNode管理节点内存可以极大降低泄漏风险。教学代码为了清晰展示指针操作未使用但生产代码强烈推荐。浅拷贝问题问题未定义拷贝构造函数或拷贝赋值运算符编译器生成的默认版本进行按成员拷贝浅拷贝。当对象持有动态内存如_data指针时两个对象会指向同一块内存析构时会导致重复释放double free。排查程序在拷贝对象后崩溃错误信息常与free()或malloc相关。技巧遵循“Rule of Three/Five”。一旦类需要手动管理资源定义了析构函数就应该同时定义或明确禁止拷贝构造和拷贝赋值。迭代器失效问题在我们的简单实现中未提供迭代器但若提供在push导致扩容数组实现或pop删除节点链表实现后之前获取的迭代器将指向无效内存。技巧文档中必须明确说明哪些操作会导致迭代器失效。参考STL容器的规范。异常安全问题在扩容拷贝元素、或拷贝构造函数拷贝元素时如果T的拷贝赋值/构造函数抛出异常可能导致资源泄漏或对象状态被破坏。技巧使用“copy-and-swap”惯用法来实现拷贝赋值运算符可以提供强异常安全保证。在可能抛出异常的操作前先分配新资源成功后再替换旧资源。循环队列的索引计算错误问题_rear (_rear 1) % _capacity这句代码如果_rear是size_t无符号当_rear为_capacity-1时_rear1等于_capacity取模后为0逻辑正确。但计算队尾元素时(_rear - 1 _capacity) % _capacity如果_rear为0_rear-1会发生下溢对于无符号数会变成一个很大的正数。因此必须加上_capacity再取模。技巧仔细测试边界情况空队列、单元素队列、满队列时的各种操作。手动实现这些基础数据结构就像木匠打磨自己的第一套工具。过程可能繁琐但每一次调试每一次对边界条件的思考都在加深你对程序如何与内存打交道的理解。当你再使用std::stack和std::queue时你看到的将不再是一个黑盒而是一个由精妙指针、索引和内存块构成的清晰图景。这种理解是写出高效、稳健的C代码的基石。
