一文吃透栈结构：从基本操作到算法应用，零基础也能轻松掌握_栈结构基本操作

引言

栈（Stack）是计算机科学中一种重要的数据结构，遵循\"后进先出（LIFO, Last In First Out）\"的原则。它在程序设计中有着广泛的应用，如函数调用、表达式求值、括号匹配等。本文将从栈的基本概念出发，详细解析栈的实现代码，补充关键知识点与易错点，并通过经典案例展示栈的实际应用。

一、栈的基本概念

1.1 定义

栈是一种操作受限的线性表，仅允许在表的一端（称为栈顶）进行插入和删除操作。

• 入栈（Push）：在栈顶插入元素
• 出栈（Pop）：从栈顶删除元素
• 栈顶（Top）：允许操作的一端
• 栈底（Bottom）：固定的一端，不允许直接操作

1.2 图示

 栈顶 ↓┌───┐│ 4 │├───┤│ 3 │├───┤│ 2 │├───┤│ 1 │└───┘ ↑ 栈底

1.3 基本操作

• 初始化（STInit）
• 销毁（STDestroy）
• 入栈（STPush）
• 出栈（STPop）
• 取栈顶元素（STTop）
• 判空（STEmpty）
• 获取元素个数（STSize）

二、栈的实现（动态数组版）

2.1 目录结构

stack_demo/├── Stack.h // 栈的声明├── Stack.c // 栈的实现└── main.c // 测试代码

2.2 头文件（Stack.h）

#include #include #include #include #pragma once// 栈中元素的数据类型typedef int STDataType;// 栈的结构体定义typedef struct Stack{ STDataType* arr; // 动态数组存储元素 int top; // 栈顶指针（指向栈顶元素的下一个位置） int capacity; // 栈的容量}ST;// 栈初始化和销毁void STInit(ST* ps);void STDestroy(ST* ps); // 注意：原代码此处函数名拼写错误（STDestory），已修正// 入栈和出栈void STPush(ST* ps, STDataType num);void STPop(ST* ps);// 取栈顶数据STDataType STTop(ST* ps);// 判空bool STEmpty(ST* ps);// 获取数据个数int STSize(ST* ps);

代码解析：

• 使用typedef定义STDataType，方便后续修改栈存储的数据类型
• 栈结构体包含三个成员：动态数组arr（存储元素）、top（栈顶指针）、capacity（容量）
• 函数声明清晰列出了栈的所有基本操作
• 注意：原代码中STDestroy误写为STDestory，实际使用时需修正，否则会出现链接错误

2.3 实现文件（Stack.c）

#include \"Stack.h\"// 栈初始化void STInit(ST* ps){ assert(ps); // 确保传入的指针非空 ps->arr = NULL; ps->capacity = 0; ps->top = 0; // top=0表示栈顶指针指向栈顶元素的下一个位置}// 栈销毁void STDestroy(ST* ps){ assert(ps); free(ps->arr); // 释放动态数组内存 ps->arr = NULL; // 避免野指针 ps->top = ps->capacity = 0; // 重置状态}// 入栈操作void STPush(ST* ps, STDataType num){ assert(ps); // 检查容量，若满则扩容 if (ps->top == ps->capacity) { // 初始容量为4，后续扩容为当前的2倍 int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType)); if (tmp == NULL) { perror(\"realloc fail !\"); // 打印错误信息 return; } ps->arr = tmp; ps->capacity = newcapacity; } // 存入元素，栈顶指针上移 ps->arr[ps->top] = num; ps->top++;}// 出栈操作void STPop(ST* ps){ // 确保栈非空才能出栈 assert(ps && ps->top > 0); ps->top--; // 仅移动栈顶指针即可（逻辑删除）}// 取栈顶数据STDataType STTop(ST* ps){ // 确保栈非空才能取栈顶 assert(ps && ps->top > 0); return ps->arr[ps->top - 1]; // top指向栈顶元素的下一个位置，所以-1}// 判空操作bool STEmpty(ST* ps){ assert(ps); return ps->top == 0; // top为0表示栈空}// 获取数据个数int STSize(ST* ps){ assert(ps); return ps->top; // top的值就是元素个数}

代码解析：

1. 初始化（STInit）：

   • 将动态数组置空，容量和栈顶指针初始化为0
   • 使用assert确保传入的指针有效（非空）

2. 销毁（STDestroy）：

   • 释放动态数组内存，避免内存泄漏
   • 将指针置空，防止野指针问题
   • 重置top和capacity为0

3. 入栈（STPush）：

   • 核心逻辑：先检查容量，不足则扩容，再存入元素
   • 扩容策略：初始容量4，后续每次翻倍（时间复杂度摊还为O(1)）
   • 使用realloc进行内存分配，需判断分配是否成功

4. 出栈（STPop）：

   • 仅通过移动栈顶指针实现（top--），无需真正删除元素
   • 必须确保栈非空才能出栈（assert(ps->top > 0)）

5. 取栈顶（STTop）：

   • 由于top指向栈顶元素的下一个位置，所以实际栈顶元素是arr[top-1]

2.4 测试代码（main.c）

#include \"Stack.h\"int main(){ // 测试流程：入栈1→入栈2→出栈2→入栈3→入栈4→出栈所有元素 ST s; STInit(&s); STPush(&s, 1); // 栈：[1] STPush(&s, 2); // 栈：[1,2] printf(\"%d \", STTop(&s)); // 打印2 STPop(&s);  // 栈：[1] STPush(&s, 3); // 栈：[1,3] STPush(&s, 4); // 栈：[1,3,4] // 出栈所有元素并打印 while (!STEmpty(&s)) { printf(\"%d \", STTop(&s)); // 依次打印4、3、1 STPop(&s); } // 最终输出：2 4 3 1 STDestroy(&s); return 0;}

执行过程解析：

操作 栈中元素 输出 STInit(&s) [] - STPush(&s, 1) [1] - STPush(&s, 2) [1,2] - STTop(&s) [1,2] 2 STPop(&s) [1] - STPush(&s, 3) [1,3] - STPush(&s, 4) [1,3,4] - 第一次循环（STTop） [1,3,4] 4 第二次循环（STTop） [1,3] 3 第三次循环（STTop） [1] 1

三、栈的经典应用

3.1 括号匹配问题

问题描述：判断一个字符串中的括号是否匹配，包括()、[]、{}三种类型。

匹配规则：

• 左括号必须用相同类型的右括号闭合
• 左括号必须以正确的顺序闭合
• 空字符串视为匹配

实现思路：

1. 遍历字符串中的每个字符
2. 遇到左括号则入栈
3. 遇到右括号则判断栈顶是否为对应的左括号：
   • 是则出栈
   • 否则匹配失败
4. 遍历结束后，栈必须为空才表示完全匹配

代码实现：

#include \"Stack.h\"#include // 判断左右括号是否匹配bool isMatch(char left, char right){ return (left == \'(\' && right == \')\') ||  (left == \'[\' && right == \']\') ||  (left == \'{\' && right == \'}\');}// 括号匹配函数bool isValid(char* s){ ST st; STInit(&st); int len = strlen(s); for (int i = 0; i < len; i++) { // 左括号入栈 if (s[i] == \'(\' || s[i] == \'[\' || s[i] == \'{\') { STPush(&st, s[i]); } // 右括号处理 else { // 右括号多了 if (STEmpty(&st)) { STDestroy(&st); return false; } char top = STTop(&st); STPop(&st); // 类型不匹配 if (!isMatch(top, s[i])) { STDestroy(&st); return false; } } } // 左括号多了 bool ret = STEmpty(&st); STDestroy(&st); return ret;}// 测试括号匹配void testBracketMatch(){ char* s1 = \"()\"; char* s2 = \"()[]{}\"; char* s3 = \"(]\"; char* s4 = \"([)]\"; char* s5 = \"{[]}\"; printf(\"测试括号匹配：\\n\"); printf(\"%s: %s\\n\", s1, isValid(s1) ? \"匹配\" : \"不匹配\"); // 匹配 printf(\"%s: %s\\n\", s2, isValid(s2) ? \"匹配\" : \"不匹配\"); // 匹配 printf(\"%s: %s\\n\", s3, isValid(s3) ? \"匹配\" : \"不匹配\"); // 不匹配 printf(\"%s: %s\\n\", s4, isValid(s4) ? \"匹配\" : \"不匹配\"); // 不匹配 printf(\"%s: %s\\n\", s5, isValid(s5) ? \"匹配\" : \"不匹配\"); // 匹配}// 在main函数中调用testBracketMatch()即可测试

3.2 逆波兰表达式求值

逆波兰表达式（后缀表达式）是一种没有括号的表达式，运算符放在两个操作数后面，例如：

• 中缀表达式：(1+2)*(3+4)
• 逆波兰表达式：1 2 + 3 4 + *

求值思路：

1. 遍历表达式的每个元素
2. 遇到数字则入栈
3. 遇到运算符则弹出栈顶两个元素，计算结果后将结果入栈
4. 遍历结束后，栈中仅剩的元素就是表达式的结果

代码示例：

// 简化版逆波兰表达式求值（仅支持+、-、*、/）int evalRPN(char** tokens, int tokensSize){ ST st; STInit(&st); for (int i = 0; i < tokensSize; i++) { char* token = tokens[i]; // 如果是运算符 if (token[0] == \'+\' || token[0] == \'-\' || token[0] == \'*\' || token[0] == \'/\') { int b = STTop(&st); STPop(&st); int a = STTop(&st); STPop(&st); int res = 0; switch (token[0]) { case \'+\': res = a + b; break; case \'-\': res = a - b; break; case \'*\': res = a * b; break; case \'/\': res = a / b; break; } STPush(&st, res); } // 如果是数字 else { STPush(&st, atoi(token)); } } int result = STTop(&st); STDestroy(&st); return result;}

四、知识点补充

4.1 数组栈 vs 链表栈

特性 数组栈 链表栈 实现复杂度 简单 中等 访问效率 O(1)（随机访问） O(1)（仅栈顶） 扩容 需要（动态扩容） 不需要（按需分配） 内存利用率 可能有浪费（预分配） 较高（无浪费） 缓存友好性 好（连续内存） 差（分散内存）

总结：数组栈实现简单且访问高效，适合大多数场景；链表栈适合内存受限或元素数量波动大的场景。

4.2 栈的时间复杂度

栈的所有基本操作（入栈、出栈、取栈顶、判空、获取大小）的时间复杂度均为O(1)，这使得栈成为效率极高的数据结构。

• 入栈：虽然可能涉及扩容（O(n)），但采用翻倍扩容策略，摊还复杂度为O(1)
• 出栈：仅移动指针，O(1)
• 取栈顶：直接访问数组元素，O(1)

4.3 栈的应用场景

1. 函数调用：操作系统用栈保存函数调用上下文（返回地址、局部变量等）
2. 表达式求值：如逆波兰表达式求值
3. 括号匹配：编译器语法分析
4. 浏览器历史记录：前进/后退功能
5. 撤销操作：文本编辑器的撤销功能
6. 深度优先搜索（DFS）：递归本质上是栈的应用

五、易错点总结

1. top指针的初始值：

   • 本文实现中top=0（指向栈顶元素的下一个位置）
   • 另一种常见实现是top=-1（指向栈顶元素）
   • 两种方式均可，但需保持一致，否则会导致逻辑错误

2. 函数名拼写错误：

   • 原代码中STDestroy误写为STDestory（少了一个r）
   • 这类错误编译器不会报错，但链接时会提示\"未定义的引用\"，需特别注意

3. 内存管理：

   • realloc可能失败（返回NULL），需判断并处理
   • 销毁栈后必须将指针置空，避免野指针
   • 扩容时原内存可能被释放，需用临时指针接收realloc返回值

4. 边界检查：

   • 出栈和取栈顶操作前必须检查栈是否为空
   • 使用assert可以帮助快速定位错误，但发布版本中可禁用

5. 扩容策略：

   • 固定大小扩容（如每次+4）会导致频繁扩容，时间复杂度高
   • 翻倍扩容策略更优，摊还时间复杂度为O(1)

六、总结

栈作为一种简单而强大的数据结构，其\"后进先出\"的特性使其在众多场景中发挥重要作用。本文从栈的基本概念出发，详细解析了动态数组实现栈的代码，补充了关键知识点与易错点，并通过括号匹配、逆波兰表达式求值等经典案例展示了栈的实际应用。

掌握栈的实现与应用，不仅能帮助我们解决特定问题，更能培养我们的抽象思维和数据结构设计能力。在实际开发中，应根据具体需求选择合适的栈实现方式，并注意内存管理和边界条件处理，写出健壮高效的代码。

希望本文能帮助你深入理解栈的原理与应用！如果有任何疑问或建议，欢迎在评论区留言讨论。