C++栈数据结构：从数组与链表实现到括号匹配与表达式求值

很多C初学者在面试或笔试时一遇到“栈”相关的问题就心里发慌。他们可能背得出“后进先出”的定义但被问到“如何用数组实现一个栈”、“括号匹配怎么用栈解决”、“递归调用和栈帧有什么关系”时却常常卡壳。这背后的原因往往是把栈当成了一个抽象的理论概念而没有真正理解它作为一种基础数据结构在内存管理和算法逻辑中的核心作用。这篇文章要解决的正是这个痛点。我们不只讲“栈是什么”更要讲清楚“为什么需要栈”以及“如何用C从零实现它”。更重要的是我会带你剖析几个高频的栈应用场景让你看到栈是如何将复杂问题如表达式求值、函数调用变得清晰可控的。读完本文你将不仅能手写一个健壮的栈结构更能理解其设计思想从容应对相关面试题和实际开发。1. 栈不止是“后进先出”的容器在深入代码之前我们必须先破除一个误区栈Stack绝不仅仅是一个有特殊存取规则的数据容器。它的核心价值在于模拟“最近相关性”问题的处理过程。想象一下你正在编辑代码每次输入一个左括号(编辑器都需要知道最近一个等待匹配的是哪个括号。又或者你的程序执行到一个函数调用系统必须记住执行完这个函数后应该返回到哪里继续。这些场景都有一个共同点最后发生的事件需要最先被处理。栈就是为这种场景而生的完美模型。与“堆”Heap这个容易混淆的概念相比两者的区别至关重要栈Stack由编译器自动管理用于存储函数调用时的局部变量、参数、返回地址等。内存分配和回收速度极快但容量有限生命周期与函数调用同步。堆Heap由程序员手动管理在C中通过new/delete或malloc/free用于动态分配大块内存。容量大但分配和回收速度慢管理不当易产生内存泄漏。我们本文讨论的“栈结构”是指可以模拟这种“后进先出”LIFO, Last In First Out逻辑的抽象数据类型ADT。它既可以用数组实现也可以用链表实现。2. 环境准备你的C学习环境在开始编码前请确保你有一个可用的C开发环境。对于学习数据结构而言一个轻量级的配置就足够了。编译器推荐使用GCC(MinGW-w64) 或Clang。它们是现代、标准的C编译器。IDE或编辑器Visual Studio Code (VSCode)轻量配合C插件体验很好。CLionJetBrains出品对C支持非常智能但需要付费或使用教育许可。Visual Studio (Windows)功能强大但比较重型。简单的文本编辑器如Notepad, Sublime Text配合命令行编译也可。验证环境打开终端或命令行输入以下命令检查GCC是否就绪g --version如果看到类似g (MinGW.org GCC-8.2.0-3) 8.2.0的输出说明环境已准备好。本文的所有代码示例均使用标准C11及以上语法确保在主流编译器中都能顺利编译运行。3. 栈的抽象接口设计先定义再实现在动手实现之前我们先从使用者的角度思考一个栈应该提供哪些最基本的操作这能帮助我们设计出清晰、易用的接口。一个最小化的栈通常包含以下核心操作push(element): 将元素压入栈顶。pop(): 移除并返回栈顶元素如果栈非空。top(): 查看栈顶元素但不移除它。isEmpty(): 检查栈是否为空。size(): 返回栈中元素的数量。我们将这些操作定义在一个类模板中这样我们的栈就能存储任意类型的数据。// File: stack_interface.hpp (可选用于说明设计) template typename T class Stack { public: virtual ~Stack() {} // 核心操作 virtual void push(const T element) 0; virtual void pop() 0; virtual T top() const 0; virtual bool isEmpty() const 0; virtual size_t size() const 0; };这是一个抽象基类它规定了栈的“契约”。接下来我们将用两种最经典的方式来实现这个契约基于数组和基于链表。4. 核心实现一基于动态数组的栈推荐入门使用动态数组如std::vector的简化版实现栈是最直观的方法。它的优势在于内存连续访问速度快尤其是在栈顶操作上可以达到O(1)时间复杂度。关键设计点我们需要一个底层数组data_来存储元素。需要一个变量topIndex_或直接用size_来跟踪栈顶位置。当数组容量不足时需要进行动态扩容通常是翻倍这是一个需要理解的关键细节。下面是完整的实现代码// File: array_stack.hpp #ifndef ARRAY_STACK_HPP #define ARRAY_STACK_HPP #include stdexcept // 用于抛出标准异常 #include cstddef // 用于 size_t template typename T class ArrayStack { private: T* data_; // 指向动态数组的指针 size_t capacity_; // 数组的总容量 size_t size_; // 栈当前的大小也指向栈顶的下一个位置 // 扩容内部方法 void resize(size_t newCapacity) { T* newData new T[newCapacity]; // 将旧数据拷贝到新数组 for (size_t i 0; i size_; i) { newData[i] data_[i]; // 注意这里要求T类型支持拷贝赋值 } delete[] data_; // 释放旧数组内存 data_ newData; capacity_ newCapacity; } public: // 构造函数初始容量默认为10 ArrayStack(size_t initialCapacity 10) : capacity_(initialCapacity), size_(0) { if (initialCapacity 0) { throw std::invalid_argument(Initial capacity must be positive.); } data_ new T[capacity_]; } // 析构函数释放动态内存 ~ArrayStack() { delete[] data_; } // 拷贝构造函数深拷贝防止浅拷贝问题 ArrayStack(const ArrayStack other) : capacity_(other.capacity_), size_(other.size_) { data_ new T[capacity_]; for (size_t i 0; i size_; i) { data_[i] other.data_[i]; } } // 赋值运算符深拷贝 ArrayStack operator(const ArrayStack other) { if (this ! other) { // 防止自赋值 delete[] data_; capacity_ other.capacity_; size_ other.size_; data_ new T[capacity_]; for (size_t i 0; i size_; i) { data_[i] other.data_[i]; } } return *this; } // 核心操作实现 void push(const T element) { // 检查是否需要扩容 if (size_ capacity_) { resize(capacity_ * 2); // 常见的扩容策略容量翻倍 } data_[size_] element; // 在size_位置插入然后size_加1 } void pop() { if (isEmpty()) { throw std::out_of_range(Cannot pop from an empty stack.); } --size_; // 简单地将大小减一。对于对象可能需要调用析构函数这里简化处理。 // 可选当栈大小远小于容量时可以缩容以节省空间。 // if (size_ 0 size_ capacity_ / 4) { // resize(capacity_ / 2); // } } T top() { if (isEmpty()) { throw std::out_of_range(Cannot get top from an empty stack.); } return data_[size_ - 1]; // 栈顶元素位于 size_-1 的位置 } const T top() const { // 提供const版本用于const对象 if (isEmpty()) { throw std::out_of_range(Cannot get top from an empty stack.); } return data_[size_ - 1]; } bool isEmpty() const { return size_ 0; } size_t size() const { return size_; } size_t capacity() const { return capacity_; } }; #endif // ARRAY_STACK_HPP代码关键点解析动态扩容 (resize)这是数组实现的核心。当push时发现size_ capacity_我们创建一个容量翻倍的新数组将旧数据拷贝过去然后释放旧内存。这保证了栈的容量能动态增长。缩容逻辑被注释掉了在实际生产库中为了减少内存碎片和浪费通常会添加。异常安全在pop()和top()中如果栈为空我们抛出std::out_of_range异常。这是比直接崩溃或返回垃圾值更友好的做法。深拷贝我们手动实现了拷贝构造函数和赋值运算符。这是必须的因为类管理着动态内存 (data_)。如果使用编译器生成的默认拷贝函数会导致多个对象指向同一块内存在析构时引发“重复释放”的严重错误。栈顶索引我们使用size_变量同时表示“元素数量”和“下一个可插入位置的索引”。因此栈顶元素始终在data_[size_ - 1]。5. 核心实现二基于链表的栈链表实现的栈在理论上不需要预先分配固定容量每次push动态申请一个节点内存即可。它的push和pop操作也始终是O(1)时间复杂度且没有扩容带来的拷贝开销。但每个节点需要额外的指针空间且内存不连续缓存不友好。关键设计点定义一个内部Node结构体包含数据data和指向下一个节点的指针next。栈只需要维护一个指向链表头节点即栈顶的指针top_。push相当于在链表头部插入新节点。pop相当于删除链表头节点。// File: linked_list_stack.hpp #ifndef LINKED_LIST_STACK_HPP #define LINKED_LIST_STACK_HPP #include stdexcept template typename T class LinkedListStack { private: // 链表节点定义 struct Node { T data; Node* next; Node(const T val, Node* nxt nullptr) : data(val), next(nxt) {} }; Node* top_; // 栈顶指针指向链表头部 size_t size_; // 记录栈大小避免遍历链表计算 public: LinkedListStack() : top_(nullptr), size_(0) {} ~LinkedListStack() { // 析构时释放所有节点内存 while (!isEmpty()) { pop(); } } // 禁止拷贝构造和赋值简化处理也可实现深拷贝 LinkedListStack(const LinkedListStack) delete; LinkedListStack operator(const LinkedListStack) delete; void push(const T element) { // 创建新节点其next指向原栈顶然后更新top_指针 top_ new Node(element, top_); size_; } void pop() { if (isEmpty()) { throw std::out_of_range(Cannot pop from an empty stack.); } Node* nodeToDelete top_; top_ top_-next; // 栈顶指针下移 delete nodeToDelete; // 释放原栈顶节点内存 --size_; } T top() { if (isEmpty()) { throw std::out_of_range(Cannot get top from an empty stack.); } return top_-data; } const T top() const { if (isEmpty()) { throw std::out_of_range(Cannot get top from an empty stack.); } return top_-data; } bool isEmpty() const { return top_ nullptr; // 或者 return size_ 0; } size_t size() const { return size_; } }; #endif // LINKED_LIST_STACK_HPP两种实现的对比与选择特性数组栈 (ArrayStack)链表栈 (LinkedListStack)内存连续缓存友好可能有空闲容量非连续每个元素有额外指针开销扩容需要复制数据有性能波动每次push动态分配无扩容概念访问O(1)随机访问虽然栈只用栈顶只能顺序访问实现复杂度需处理扩容和深拷贝需处理节点内存管理适用场景元素数量可预估或变化平稳元素数量波动极大或无法预估对于大多数学习和面试场景掌握数组实现更为重要因为它涉及了动态内存管理、深拷贝等C核心概念。链表实现则有助于理解指针操作。6. 运行与测试验证你的栈实现之后必须进行测试。一个好的测试应覆盖正常操作和边界异常。// File: test_stack.cpp #include iostream #include array_stack.hpp // 或 #include linked_list_stack.hpp int main() { std::cout Testing ArrayStack std::endl; ArrayStackint stack; // 测试 push 和 top stack.push(10); stack.push(20); stack.push(30); std::cout After pushes, top is: stack.top() std::endl; // 应输出 30 std::cout Size is: stack.size() std::endl; // 应输出 3 // 测试 pop stack.pop(); std::cout After one pop, top is: stack.top() std::endl; // 应输出 20 // 测试 isEmpty stack.pop(); stack.pop(); std::cout After popping all, isEmpty: std::boolalpha stack.isEmpty() std::endl; // 应输出 true // 测试异常处理 (尝试从空栈pop) try { stack.pop(); } catch (const std::out_of_range e) { std::cout Caught expected exception: e.what() std::endl; } // 测试扩容 ArrayStackint smallStack(2); // 初始容量为2 smallStack.push(1); smallStack.push(2); std::cout Capacity before overflow: smallStack.capacity() std::endl; // 应为2 smallStack.push(3); // 触发扩容 std::cout Capacity after push (should be doubled): smallStack.capacity() std::endl; // 应为4 std::cout Top after push: smallStack.top() std::endl; // 应为3 std::cout \nAll tests passed! std::endl; return 0; }编译与运行 在终端中使用g编译并运行测试程序g -stdc11 -o test_stack test_stack.cpp ./test_stack你应该能看到预期的输出确认栈的基本功能正常工作并且异常处理也按设计执行。7. 栈的经典应用场景剖析理解了栈的实现我们来看看它如何解决实际问题。这是将知识内化的关键。7.1 场景一括号匹配检查这是栈最直观的应用。给定一个包含()、[]、{}的字符串判断括号是否匹配。算法思路遍历字符串。遇到左括号 ((,[,{)将其压入栈。遇到右括号 (),],})检查栈顶的左括号是否与之匹配。如果栈为空或不匹配则表达式无效。如果匹配则将栈顶的左括号弹出。遍历结束后如果栈为空则所有括号匹配否则不匹配。#include iostream #include string #include array_stack.hpp // 使用我们实现的栈 bool isBalanced(const std::string expression) { ArrayStackchar stack; for (char ch : expression) { if (ch ( || ch [ || ch {) { stack.push(ch); } else if (ch ) || ch ] || ch }) { if (stack.isEmpty()) { return false; // 有右括号但没有左括号 } char top stack.top(); stack.pop(); // 检查是否匹配 if ((ch ) top ! () || (ch ] top ! [) || (ch } top ! {)) { return false; } } // 忽略其他字符 } // 最后栈必须为空才表示完全匹配 return stack.isEmpty(); } int main() { std::string test1 (([]){}); std::string test2 ([)]; std::string test3 ((()); std::cout test1 is balanced? isBalanced(test1) std::endl; // true std::cout test2 is balanced? isBalanced(test2) std::endl; // false std::cout test3 is balanced? isBalanced(test3) std::endl; // false return 0; }7.2 场景二函数调用与递归栈帧这是栈在计算机系统层面的核心应用。每次函数调用时系统都会在调用栈Call Stack上压入一个栈帧Stack Frame其中包含了函数的返回地址调用结束后回到哪里。函数的参数。函数的局部变量。一些保存的寄存器信息。当函数返回时其对应的栈帧被弹出程序回到调用点继续执行。递归函数就是利用这一机制每一层递归调用都会创建一个新的栈帧。如果递归深度过大就会导致栈溢出Stack Overflow。理解这一点你就能明白为什么递归问题如二叉树遍历、DFS通常都可以用**显式的栈我们实现的数据结构**来改写为非递归迭代形式以避免系统调用栈的深度限制。7.3 场景三表达式求值中缀转后缀计算3 4 * 2 / (1 - 5)这样的表达式编译器或计算器内部通常使用栈来处理运算符的优先级。最经典的算法是“调度场算法”Shunting-yard algorithm它使用两个栈一个输出队列一个运算符栈将中缀表达式转换为后缀表达式逆波兰表示法后者没有括号求值顺序唯一非常适合栈计算。由于篇幅所限这里给出一个简化版的思路初始化一个操作数栈和一个运算符栈。遍历表达式。遇到数字压入操作数栈。遇到运算符与运算符栈顶比较优先级如果栈顶优先级更高或相等则先弹出栈顶运算符进行计算从操作数栈弹出两个数将结果压回操作数栈然后将当前运算符压栈。否则直接压入运算符栈。遇到左括号压入运算符栈遇到右括号则不断弹出运算符栈顶并计算直到遇到左括号。遍历结束后将运算符栈中所有剩余运算符弹出并计算。操作数栈最后剩下的数就是结果。这个例子深刻体现了栈在管理“待处理任务”上的强大能力。8. 常见问题与排查思路在实现和使用栈时你可能会遇到以下问题问题现象可能原因排查方式解决方案程序崩溃Segmentation Fault1. 访问了空栈的top()。2. 数组实现中data_指针未初始化或已释放后被访问。3. 链表实现中访问了nullptr的next。1. 在top()和pop()开头添加空栈检查。2. 使用调试器如gdb查看崩溃时的调用栈和变量值。3. 检查构造函数、析构函数、拷贝函数的正确性。1. 确保所有操作前检查栈状态。2. 遵循RAII原则在构造函数中分配资源在析构函数中释放。3. 实现正确的拷贝控制深拷贝或禁用拷贝如链表栈示例。内存泄漏1. 数组实现new[]后没有对应的delete[]。2. 链表实现pop()时没有delete节点或析构函数未清理所有节点。使用内存检测工具如 Valgrind (Linux) 或 CRT Debug Heap (Windows)。1. 确保new/deletenew[]/delete[]成对出现。2. 在链表栈的析构函数中循环调用pop()或遍历删除所有节点。扩容后数据错误或程序异常1. 扩容函数resize()实现有误如拷贝范围错误。2. 扩容后未正确更新capacity_和data_指针。在resize()函数内和调用后打印data_地址和内容进行调试。1. 仔细检查resize中的循环边界 (i size_)。2. 确保先分配新内存、拷贝数据再释放旧内存最后更新指针和容量。拷贝对象时发生浅拷贝使用了编译器生成的默认拷贝构造函数或赋值运算符导致多个栈对象共享同一块动态数组。观察两个栈对象操作后数据是否相互影响。为管理动态资源的类必须自定义拷贝构造函数和赋值运算符实现深拷贝。或者使用std::vector等管理底层数组它们已正确处理拷贝。9. 最佳实践与工程建议优先使用标准库在实际C项目中除非有极特殊的性能或定制需求否则永远优先使用std::stack。它是模板类底层容器默认为std::deque稳定且高效。#include stack #include vector std::stackint s1; // 使用deque std::stackint, std::vectorint s2; // 指定用vector作底层容器自己实现栈的主要目的是学习数据结构原理和C内存管理。考虑异常安全如我们的示例所示在可能失败的操作如空栈pop中抛出标准异常std::out_of_range比让程序崩溃更好。这给了调用者处理错误的机会。为自定义栈添加迭代器如果需要遍历栈中的元素虽然不符合栈的抽象但有时调试需要可以为你的栈类实现迭代器。这能让你使用基于范围的for循环 (for (auto elem : myStack))。性能考量数组栈关注扩容因子如2倍。因子太大会浪费内存太小会导致频繁扩容。std::vector的扩容策略是经验值。链表栈每次push都是new操作在频繁操作的场景下可能成为性能瓶颈。可以考虑使用内存池来优化。线程安全我们实现的栈不是线程安全的。如果需要在多线程环境下使用需要对push,pop,top等操作加锁例如使用std::mutex或者直接使用std::stack并配合互斥锁。理解栈是理解许多高级算法和系统机制的基础。从函数调用的栈帧到深度优先搜索的显式栈再到语法解析中的符号栈其“后进先出”的思想无处不在。建议你不仅掌握本文的实现更要多用栈的思路去思考问题。接下来可以尝试用栈实现一个简单的计算器或者将递归的二叉树遍历改为迭代版本这能极大地巩固你的学习成果。