1. 项目概述：为什么需要手动实现栈和队列？

在C++的日常开发中，std::stack和std::queue几乎是信手拈来的工具，STL（标准模板库）已经为我们封装好了稳定高效的实现。那么，为什么我们还要“多此一举”地手动去实现它们呢？这个问题，在我带过的实习生和面试过的候选人中，出现的频率相当高。答案远不止于“为了面试”这么简单。手动实现这些基础数据结构，是深入理解计算机科学核心思想、锻炼底层编码能力、以及应对特定性能或资源约束场景的必经之路。当你亲手用数组或链表搭建起一个栈，处理完边界溢出和空栈访问的每一个细节后，你才能真正理解“后进先出”（LIFO）和“先进先出”（FIFO）不仅仅是两个抽象概念，而是内存操作、函数调用、任务调度等无数场景背后的坚实支柱。

对于初学者，这是一个绝佳的、从“会用库”到“懂原理”的跨越。你会直面指针操作、内存管理、模板编程和异常安全这些C++的核心议题。对于有经验的开发者，这更像是一次“返璞归真”的练习，能帮你写出更高效、更健壮的代码，尤其是在嵌入式、游戏、高频交易等对性能和可控性要求极高的领域，自定义的数据结构往往是优化性能的关键。接下来，我将结合我十多年的C++工程经验，带你从零开始，一步步构建出工业级强度的栈和队列，并深入探讨其中的设计抉择、陷阱规避和性能考量。

2. 核心数据结构设计思路与选型

在动手写代码之前，我们必须做出两个关键的设计决策：底层存储容器用什么，以及如何管理这个容器的生命周期和容量。这两个选择直接决定了我们实现的栈和队列的性能特性、内存占用和接口易用性。

2.1 底层容器选型：数组 vs. 链表

这是最经典的数据结构选择题。对于栈和队列，两者各有优劣。

基于数组（顺序存储）的实现：

• 核心思路：在堆上分配一块连续的内存空间。对于栈，我们维护一个指向栈顶的索引（或指针）；对于队列，我们维护队头（front）和队尾（rear）两个索引，可能还会配合“循环队列”的技巧来复用空间。
• 优势：
  1. 极高的缓存友好性：数据在内存中连续存放，CPU预取效率高，访问速度极快。这是数组最大的优势。
  2. 内存开销小：除了存储元素本身，只需要额外的几个整型变量（如容量、栈顶索引、队头队尾索引），没有链表节点中next指针带来的额外开销。
  3. 实现简单直观：索引操作比指针操作更不容易出错。
• 劣势：
  1. 固定容量：创建时需要指定最大容量，存在空间浪费或溢出的风险。虽然可以实现动态扩容（如std::vector），但扩容涉及数据拷贝，有性能开销。
  2. 队列的“假溢出”：对于简单数组实现的队列，即使数组尾部还有空间，但队头移出后空出的位置无法被新元素使用，这就是“假溢出”。必须引入“循环队列”的概念来解决。

基于链表（链式存储）的实现：

• 核心思路：每个元素封装在一个节点（Node）中，节点包含数据域和指向下一个节点的指针。对于栈，我们只需维护一个指向链表头（即栈顶）的指针；对于队列，则需要维护头指针（队头）和尾指针（队尾）。
• 优势：
  1. 动态容量：理论上可以无限添加元素（直到内存耗尽），没有预分配和溢出的烦恼，空间利用率高。
  2. 插入删除高效：在已知位置（如链表头）插入删除节点是O(1)操作，非常适合栈和队列的语义。
• 劣势：
  1. 缓存不友好：节点在内存中分散存储，访问时容易引起缓存缺失，遍历性能不如数组。
  2. 内存开销大：每个节点都需要额外的指针开销。对于存储小对象（如int），这个开销比例会很高。
  3. 实现稍复杂：涉及更多的指针操作，容易引入内存泄漏、悬空指针等问题。

实操心得：在绝大多数通用场景下，基于数组的动态扩容实现（模拟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 ArrayStack<T>::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 与 top

template <typename T> void ArrayStack<T>::pop() { if (empty()) { // 处理错误：抛出异常或终止程序。这里简单处理。 // throw std::out_of_range("Stack is empty, cannot pop."); return; // 或者不做任何操作 } --_top; // 栈顶指针下移。注意：这里并没有销毁对象。 // 对于非平凡类型，可能需要显式调用析构函数：_data[_top].~T(); } template <typename T> T& ArrayStack<T>::top() { if (empty()) { throw std::out_of_range("Stack is empty, no top element."); } return _data[_top - 1]; // 返回栈顶元素的引用 } template <typename T> const T& ArrayStack<T>::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. 移动构造函数（C++11） ArrayStack(ArrayStack&& other) noexcept : _data(other._data), _capacity(other._capacity), _top(other._top) { other._data = nullptr; // 将源对象置于有效但可析构状态 other._capacity = 0; other._top = 0; } // 7. 移动赋值运算符（C++11） 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”原则，能有效避免绝大多数内存相关错误。移动语义的加入（C++11以后）可以避免不必要的深拷贝，提升性能。

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 LinkedListStack<T>::push(const T& value) { // 创建新节点，其next指向当前栈顶 Node* newNode = new Node(value, _topNode); // 更新栈顶指针 _topNode = newNode; ++_size; } template <typename T> void LinkedListStack<T>::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& LinkedListStack<T>::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> LinkedListStack<T>::~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 四种实现的性能与特性对比

6.2 典型应用场景举例

• 栈的应用：

  • 函数调用栈：这是栈最经典的用途，系统自动管理。
  • 表达式求值：将中缀表达式转换为后缀表达式（逆波兰表达式），再用栈求值。
  • 括号匹配：检查代码中的括号是否成对出现。
  • 浏览器的前进后退：使用两个栈来实现。
  • 深度优先搜索（DFS）：递归的本质就是栈，非递归实现也显式用到栈。

• 队列的应用：

  • 任务调度：操作系统中的进程就绪队列、打印队列。
  • 消息队列：在分布式系统中进行异步通信，如RabbitMQ, Kafka的核心抽象。
  • 广度优先搜索（BFS）：遍历树或图时，使用队列来管理待访问节点。
  • 缓存淘汰策略：如FIFO（先进先出）缓存。
  • 数据流处理：如网络数据包缓冲区。

6.3 手动实现中的常见“坑”与排查技巧

1. 内存泄漏：

   • 问题：链表实现中，pop或析构时忘记delete节点；数组实现中，扩容后忘记delete[]旧数组。
   • 排查：使用Valgrind、AddressSanitizer等内存检测工具。养成“new/delete”、“new[]/delete[]”成对出现的编程习惯。
   • 技巧：优先使用智能指针（如std::unique_ptr<Node>）管理节点内存，可以极大降低泄漏风险。教学代码为了清晰展示指针操作未使用，但生产代码强烈推荐。

2. 浅拷贝问题：

   • 问题：未定义拷贝构造函数或拷贝赋值运算符，编译器生成的默认版本进行按成员拷贝（浅拷贝）。当对象持有动态内存（如_data指针）时，两个对象会指向同一块内存，析构时会导致重复释放（double free）。
   • 排查：程序在拷贝对象后崩溃，错误信息常与free()或malloc相关。
   • 技巧：遵循“Rule of Three/Five”。一旦类需要手动管理资源（定义了析构函数），就应该同时定义或明确禁止拷贝构造和拷贝赋值。

3. 迭代器失效：

   • 问题：在我们的简单实现中未提供迭代器，但若提供，在push导致扩容（数组实现）或pop删除节点（链表实现）后，之前获取的迭代器将指向无效内存。
   • 技巧：文档中必须明确说明哪些操作会导致迭代器失效。参考STL容器的规范。

4. 异常安全：

   • 问题：在扩容拷贝元素、或拷贝构造函数拷贝元素时，如果T的拷贝赋值/构造函数抛出异常，可能导致资源泄漏或对象状态被破坏。
   • 技巧：使用“copy-and-swap”惯用法来实现拷贝赋值运算符，可以提供强异常安全保证。在可能抛出异常的操作前先分配新资源，成功后再替换旧资源。

5. 循环队列的索引计算错误：

   • 问题：_rear = (_rear + 1) % _capacity这句代码如果_rear是size_t（无符号），当_rear为_capacity-1时，_rear+1等于_capacity，取模后为0，逻辑正确。但计算队尾元素时(_rear - 1 + _capacity) % _capacity，如果_rear为0，_rear-1会发生下溢（对于无符号数，会变成一个很大的正数）。因此必须加上_capacity再取模。
   • 技巧：仔细测试边界情况：空队列、单元素队列、满队列时的各种操作。

手动实现这些基础数据结构，就像木匠打磨自己的第一套工具。过程可能繁琐，但每一次调试，每一次对边界条件的思考，都在加深你对程序如何与内存打交道的理解。当你再使用std::stack和std::queue时，你看到的将不再是一个黑盒，而是一个由精妙指针、索引和内存块构成的清晰图景。这种理解，是写出高效、稳健的C++代码的基石。