在C面试和日常开发中栈Stack是数据结构里最基础、最核心的概念之一。无论是函数调用、表达式求值还是括号匹配、撤销操作栈的身影无处不在。很多开发者虽然知道“后进先出”这个特性但被问到如何手写一个栈、如何分析其时间复杂度、或者在实际项目中如何应用时却常常语焉不详。本文将从零开始手把手带你用C实现一个完整的栈结构不仅理解其原理更能掌握从数组实现到链表实现、从基础操作到综合应用的完整知识链让你在15分钟实际练习可能需要17分钟内真正“学会”栈。1. 栈的核心概念与为什么需要它1.1 什么是栈你可以把栈想象成一个只有一个开口的羽毛球筒。你只能从筒的顶部放入压入或取出弹出羽毛球。最后放进去的羽毛球会最先被取出来。这就是栈最核心的特性后进先出Last In, First Out, LIFO。在计算机科学中栈是一种线性数据结构它只允许在数据序列的一端称为栈顶Top进行插入入栈Push和删除出栈Pop操作。另一端则称为栈底Bottom。专业定义补充栈是限定仅在表尾进行插入和删除操作的线性表。这个“表尾”就是栈顶。1.2 栈解决了什么问题应用场景有哪些栈的核心价值在于它提供了一种临时存储和管理数据序列的机制特别适合处理具有嵌套、回溯或反转顺序关系的问题。常见应用场景函数调用栈这是栈最经典的应用。每次调用函数系统都会将当前函数的返回地址、参数、局部变量等压入一个称为“调用栈”的内存区域。函数返回时再将这些信息弹出恢复到调用者的状态。这也是“栈溢出”错误的根源。表达式求值编译器利用栈来处理中缀表达式如3 5 * 2转换为后缀表达式并计算其值。运算符和操作数根据优先级在栈中暂存和计算。括号匹配检查代码或文本中的括号(),[],{}是否成对且嵌套正确。遇到左括号就入栈遇到右括号就检查栈顶是否匹配的左括号。浏览器的前进/后退浏览历史被保存在两个栈中。一个栈存放“后退”的页面另一个存放“前进”的页面。撤销Undo操作文本编辑器或图形软件将用户的操作记录压入栈中执行撤销时就从栈顶弹出最近的操作进行回退。1.3 栈与堆Heap的区别这是一个高频面试点也是初学者最容易混淆的概念。这里的“堆”指的是内存管理中的堆区而非数据结构中的“堆一种特殊的树”。特性栈 (Stack)堆 (Heap)管理方式由编译器自动分配和释放如函数局部变量由程序员手动申请和释放如new/malloc空间大小较小且连续。在Windows上默认约1MBLinux上约8MB较大受限于系统虚拟内存空间不连续生长方向通常向低地址方向生长通常向高地址方向生长分配效率快仅移动栈顶指针慢需要寻找合适的内存块碎片问题无内存碎片有内存碎片数据存取后进先出LIFO访问局部性强速度快自由存取通过指针访问主要用途存储函数调用信息、局部变量、参数存储动态分配的数据、全局变量部分系统、大对象简单记忆函数调用、局部变量用栈动态创建、大块数据用堆。2. 环境准备与项目说明本文将使用纯C标准库进行实现和演示不依赖任何第三方库。你只需要一个能编译C代码的环境即可。推荐环境操作系统Windows 10/11, macOS, 或任意Linux发行版。编译器支持C11或更高版本的编译器。Windows: MinGW-w64 (包含在Code::Blocks, Dev-C或单独安装), 或 Visual Studio 的 MSVC 编译器。macOS/Linux: GCC 或 Clang (通常系统自带或可通过包管理器安装)。开发工具任何文本编辑器如VS Code, Sublime Text或集成开发环境如Visual Studio, CLion, Code::Blocks均可。项目结构我们将创建两个主要的实现文件和一个测试文件。stack_learning/ ├── array_stack.cpp // 使用数组实现栈 ├── list_stack.cpp // 使用链表实现栈 └── main.cpp // 测试代码版本说明本文代码基于C11标准编写核心逻辑与C98兼容。使用了一些C11特性如nullptr使代码更现代安全如果你使用的是更早的编译器将nullptr替换为NULL即可。3. 栈的ADT抽象数据类型与核心操作在动手实现之前我们先定义栈这个数据结构应该支持哪些操作即它的抽象数据类型ADT。对于一个栈S我们通常需要以下基本操作push(x)/入栈将元素x压入栈顶。pop()/出栈移除并返回栈顶元素。如果栈为空此操作通常定义为错误或返回特定值。top()/peek()/取栈顶返回栈顶元素的值但不移除它。isEmpty()/empty()判断栈是否为空。isFull()判断栈是否已满仅在使用固定大小数组实现时需要考虑。size()返回栈中当前元素的个数。在C标准库STL中std::stack容器适配器提供了push,pop,top,empty,size这些接口。4. 实战一使用数组实现栈顺序栈使用数组实现栈是最直观的方法。我们需要一个数组来存储元素一个整型变量通常称为topIndex或top来记录栈顶的位置。4.1 设计思路与类定义核心思想数组的0号位置作为栈底。topIndex初始化为-1表示空栈。push操作topIndex先加1然后将元素放入array[topIndex]。pop操作先获取array[topIndex]的值然后将topIndex减1。栈满条件topIndex capacity - 1。栈空条件topIndex -1。代码实现(array_stack.cpp)#include iostream #include stdexcept // 用于标准异常 template typename T class ArrayStack { private: T* array; // 指向存储元素的数组 int capacity; // 栈的最大容量 int topIndex; // 栈顶索引初始为-1 public: // 构造函数初始化一个指定容量的栈 ArrayStack(int size 10) { capacity size; array new T[capacity]; // 动态分配数组 topIndex -1; // 栈空 } // 析构函数释放动态分配的内存 ~ArrayStack() { delete[] array; } // 入栈操作 void push(const T value) { if (isFull()) { // 可以在这里选择扩容这里我们先抛出异常 throw std::overflow_error(Stack is full! Cannot push.); } array[topIndex] value; // 先移动栈顶指针再赋值 std::cout Pushed: value std::endl; } // 出栈操作 T pop() { if (isEmpty()) { throw std::underflow_error(Stack is empty! Cannot pop.); } T value array[topIndex--]; // 先取值再移动栈顶指针 std::cout Popped: value std::endl; return value; } // 查看栈顶元素 T top() const { if (isEmpty()) { throw std::underflow_error(Stack is empty! No top element.); } return array[topIndex]; } // 判断栈是否为空 bool isEmpty() const { return topIndex -1; } // 判断栈是否已满 bool isFull() const { return topIndex capacity - 1; } // 返回栈中元素个数 int size() const { return topIndex 1; } // 打印栈中所有元素从栈底到栈顶用于调试 void print() const { if (isEmpty()) { std::cout Stack is empty. std::endl; return; } std::cout Stack (bottom - top): ; for (int i 0; i topIndex; i) { std::cout array[i] ; } std::cout std::endl; } };4.2 代码详解与关键点模板类template typename T这使得我们的ArrayStack可以存储任意类型的数据int,double,string等提高了代码的复用性。动态数组T* array使用new[]在堆上分配内存构造函数中指定容量。析构函数~ArrayStack()必须用delete[]释放内存防止内存泄漏。栈顶指针topIndex初始化为-1是关键这使空栈的判断非常简洁 (topIndex -1)。前加加与后减加push中的array[topIndex] value;是前加加先让topIndex从-1变成0再赋值给array[0]。这保证了第一个元素在索引0处。pop中的T value array[topIndex--];是后减加先取出array[topIndex]的值再将topIndex减1。这确保了topIndex始终指向当前栈顶元素。异常处理使用std::overflow_error和std::underflow_error来处理栈满和栈空的操作使程序更健壮。在实际项目中也可以选择扩容策略如倍增容量来代替抛出异常。4.3 测试我们的数组栈创建一个main.cpp文件来测试功能#include iostream #include “array_stack.cpp” // 注意实际项目中应将声明放在.h定义放在.cpp。这里为演示简单直接包含。 int main() { std::cout “ Testing ArrayStack ” std::endl; // 1. 创建一个容量为5的整型栈 ArrayStackint stack(5); // 2. 测试入栈 stack.push(10); stack.push(20); stack.push(30); stack.print(); // 输出: Stack (bottom - top): 10 20 30 // 3. 测试查看栈顶 std::cout “Top element is: “ stack.top() std::endl; // 输出: 30 // 4. 测试出栈 int popped stack.pop(); // 输出: Popped: 30 std::cout “After pop, top is: “ stack.top() std::endl; // 输出: 20 stack.print(); // 输出: Stack (bottom - top): 10 20 // 5. 测试栈空和栈满 std::cout “Stack size: “ stack.size() std::endl; // 输出: 2 std::cout “Is empty? “ (stack.isEmpty() ? “Yes” : “No”) std::endl; // 输出: No std::cout “Is full? “ (stack.isFull() ? “Yes” : “No”) std::endl; // 输出: No // 6. 继续入栈直到满 stack.push(40); stack.push(50); stack.push(60); // 这里会抛出异常因为容量是5已经满了 // stack.print(); // 7. 清空栈 while (!stack.isEmpty()) { stack.pop(); } std::cout “Stack is now empty: “ (stack.isEmpty() ? “Yes” : “No”) std::endl; return 0; }编译与运行在命令行中# 假设所有文件在同一目录 g -stdc11 main.cpp -o stack_test ./stack_test5. 实战二使用链表实现栈链式栈数组实现的栈有容量限制。使用链表单向链表即可可以实现一个动态扩容的栈理论上只要内存足够可以一直入栈。5.1 设计思路与节点定义核心思想将链表的头节点作为栈顶。这样入栈和出栈操作都只需要在链表头部进行时间复杂度为 O(1)。每个节点包含数据域data和指向下一个节点的指针next。push操作创建新节点将其next指向当前头节点然后更新头节点为新节点。pop操作保存头节点的数据将头节点更新为原头节点的next然后删除原头节点。栈空条件头节点指针为nullptr。代码实现(list_stack.cpp)#include iostream #include stdexcept template typename T class ListNode { public: T data; ListNode* next; ListNode(const T val) : data(val), next(nullptr) {} }; template typename T class LinkedListStack { private: ListNodeT* topNode; // 栈顶节点指针 int count; // 栈中元素个数便于size()操作 public: // 构造函数 LinkedListStack() : topNode(nullptr), count(0) {} // 析构函数需要释放所有节点内存 ~LinkedListStack() { while (!isEmpty()) { pop(); } } // 入栈操作 void push(const T value) { ListNodeT* newNode new ListNodeT(value); newNode-next topNode; // 新节点指向原栈顶 topNode newNode; // 更新栈顶为新节点 count; std::cout “Pushed: “ value std::endl; } // 出栈操作 T pop() { if (isEmpty()) { throw std::underflow_error(“Stack is empty! Cannot pop.”); } ListNodeT* nodeToDelete topNode; T value nodeToDelete-data; topNode topNode-next; // 栈顶下移 delete nodeToDelete; // 释放原栈顶内存 count--; std::cout “Popped: “ value std::endl; return value; } // 查看栈顶元素 T top() const { if (isEmpty()) { throw std::underflow_error(“Stack is empty! No top element.”); } return topNode-data; } // 判断栈是否为空 bool isEmpty() const { return topNode nullptr; } // 返回栈中元素个数 int size() const { return count; } // 打印栈中所有元素从栈顶到栈底注意链表栈打印顺序是反的 void print() const { if (isEmpty()) { std::cout “Stack is empty.” std::endl; return; } std::cout “Stack (top - bottom): “; ListNodeT* current topNode; while (current ! nullptr) { std::cout current-data “ “; current current-next; } std::cout std::endl; } };5.2 两种实现的对比与选择特性数组实现 (顺序栈)链表实现 (链式栈)内存预先分配固定大小可能浪费或不足动态分配每个元素有额外指针开销扩容扩容麻烦需要数据拷贝天然支持动态扩容访问速度连续内存CPU缓存友好访问快内存不连续访问稍慢基本操作时间复杂度Push/Pop/Top: O(1)Push/Pop/Top: O(1)适用场景栈大小可预估、追求性能的场景栈大小变化大、内存碎片不敏感的场景如何选择大多数情况下C STL 的std::stack默认使用std::deque作为底层容器它在数组和链表之间取得了平衡。在需要自己实现的场景下如果对性能有极致要求且容量固定用数组如果需要灵活的容量用链表。6. 综合实战利用栈解决经典问题——括号匹配现在我们已经有了自己的栈让我们用它来解决一个实际问题巩固理解。问题描述给定一个只包含字符(,),{,},[,]的字符串s判断字符串中的括号是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。解题思路初始化一个空栈。遍历字符串中的每个字符c如果c是左括号(,[,{将其压入栈中。如果c是右括号),],} a. 检查栈是否为空。若空说明没有匹配的左括号返回false。 b. 弹出栈顶元素topChar。 c. 检查topChar是否与c匹配。若不匹配返回false。遍历结束后检查栈是否为空。若为空说明所有括号都匹配成功返回true否则说明还有未匹配的左括号返回false。代码实现在main.cpp中增加函数使用我们实现的LinkedListStack#include “list_stack.cpp” #include string #include unordered_map bool isValidParentheses(const std::string s) { LinkedListStackchar stack; // 使用哈希表建立右括号到左括号的映射方便匹配检查 std::unordered_mapchar, char pairMap { {‘)’, ‘(‘}, {‘]’, ‘[‘}, {‘}’, ‘{‘} }; for (char c : s) { // 如果是左括号入栈 if (c ‘(‘ || c ‘[‘ || c ‘{‘) { stack.push(c); } // 如果是右括号 else if (c ‘)’ || c ‘]’ || c ‘}’) { // 栈为空或栈顶不匹配 if (stack.isEmpty() || stack.top() ! pairMap[c]) { return false; } stack.pop(); // 匹配成功弹出栈顶左括号 } // 其他字符可以忽略或者根据题目要求处理 } // 最后栈必须为空才算完全匹配 return stack.isEmpty(); } int main() { // ... 之前的测试代码 ... std::cout “\n Testing Parentheses Matching ” std::endl; std::string test1 “()[]{}”; std::string test2 “([{}])”; std::string test3 “(]”; std::string test4 “([)]”; std::string test5 “((())”; std::cout test1 “ is valid? “ (isValidParentheses(test1) ? “Yes” : “No”) std::endl; std::cout test2 “ is valid? “ (isValidParentheses(test2) ? “Yes” : “No”) std::endl; std::cout test3 “ is valid? “ (isValidParentheses(test3) ? “Yes” : “No”) std::endl; std::cout test4 “ is valid? “ (isValidParentheses(test4) ? “Yes” : “No”) std::endl; std::cout test5 “ is valid? “ (isValidParentheses(test5) ? “Yes” : “No”) std::endl; return 0; }运行结果()[]{} is valid? Yes ([{}]) is valid? Yes (] is valid? No ([)] is valid? No ((()) is valid? No7. 常见问题与排查思路在实现和使用栈时你可能会遇到以下问题问题现象可能原因排查与解决思路程序崩溃Segmentation Fault1. 数组栈访问越界topIndex为 -1 时取top或超过capacity-1。2. 链表栈对nullptr进行解引用空栈时调用top()或pop()。1. 在所有pop(),top()操作前严格检查isEmpty()。2. 在数组栈push前检查isFull()或实现自动扩容。3. 使用调试器如gdb查看崩溃时的调用栈和变量值。内存泄漏链表栈的节点在pop()时没有用delete释放或析构函数未清空栈。1. 确保pop()操作中delete被正确调用。2. 在链表栈的析构函数中循环调用pop()直到栈空。3. 使用智能指针如std::unique_ptr管理节点内存可以避免此问题。逻辑错误结果不对1. 栈顶指针topIndex初始化或更新逻辑错误如前加加/后减加用错。2. 括号匹配等算法中匹配条件写反。1.画图在纸上模拟入栈、出栈过程跟踪topIndex或topNode的变化。2. 添加详细的打印语句输出每一步操作后的栈状态。3. 使用简单的测试用例如单个元素进行调试。使用STL的std::stack时编译错误1. 未包含头文件stack。2. 对空栈调用.top()或.pop()。1. 确保#include stack。2. 调用.top()或.pop()前务必用.empty()判断。STL不会在运行时自动检查未定义行为可能导致崩溃。8. 最佳实践与工程建议优先使用标准库在实际C项目中除非有特殊需求如嵌入式环境无STL否则应优先使用std::stack。它经过充分测试高效且安全。#include stack #include iostream int main() { std::stackint st; st.push(1); st.push(2); std::cout st.top() std::endl; // 2 st.pop(); std::cout st.top() std::endl; // 1 return 0; }注意异常安全如我们的示例所示在自定义栈的实现中对非法操作空栈弹出、满栈压入要进行处理可以抛出标准异常让调用者捕获。考虑底层容器std::stack是一个容器适配器默认使用std::deque作为底层容器。你也可以指定std::vector或std::list。std::stackint, std::vectorint stack_using_vector; // 使用vector底层std::vector内存连续但扩容时可能需要整体拷贝。std::deque默认两端插入删除都是O(1)内存分段连续是折中方案。std::list每次插入删除都是O(1)但内存不连续开销大。线程安全标准库的std::stack不是线程安全的。如果需要在多线程环境下使用需要在外部加锁如std::mutex或使用支持并发的数据结构。性能考量对于性能关键的代码如果栈大小固定使用原生数组或std::array实现的栈可能最快。避免在栈中存储非常大的对象以免影响入栈/出栈速度或造成栈内存溢出对于函数调用栈而言。理解递归与栈的关系递归函数本质上就是利用系统调用栈来实现的。过深的递归会导致栈溢出Stack Overflow。遇到递归问题时可以思考能否用显式的栈如std::stack将其改写成迭代形式以规避递归深度限制。通过从零实现两种栈、解决实际算法问题再到对比STL的最佳实践你已经掌握了栈这一数据结构的核心精髓。这不仅有助于你通过技术面试更能让你在遇到需要“倒序处理”、“临时存储”、“回溯状态”的业务场景时立刻想到栈这个利器。接下来可以尝试用栈去解决“逆波兰表达式求值”、“二叉树的中序遍历”等问题进一步巩固理解。
