企业官网建设流程全解析

前言

前面几篇讲了顺序表、单链表和双链表，它们都是线性表的基础实现方式。而栈和队列，本质上是对线性表的操作方式做了限制之后得到的两种特殊线性结构。本文来讲讲栈——一种"后进先出"的数据结构，理解它是后续学习递归、DFS、表达式求值、括号匹配等内容的基础。

一、什么是栈

栈（Stack）是一种只允许在一端进行插入和删除操作的线性表。允许操作的一端叫栈顶（top），另一端叫栈底（bottom）。

栈的核心特性是后进先出（LIFO，Last In First Out）：数据压入栈的顺序和弹出栈的顺序正好相反，最后进栈的元素最先出来。

生活中的例子：

1.一摞盘子，只能从最上面拿，也只能从最上面放；

2.浏览器的"后退"功能；

3.函数调用时的调用栈（每次函数调用都会压栈，返回时弹栈）。

二、栈的实现方式

栈可以用数组实现，也可以用链表实现。

• 数组实现：从数组尾部进行插入删除，不需要挪动数据，效率是O(1)，且实现简单，是实际中最常用的方式（类似于顺序表的尾插尾删）；
• 链表实现：如果用链表实现，一般选择在链表头部进行插入删除，这样效率也是O(1)，但相对数组实现要多一层指针操作，实际使用较少。

本文以数组实现为主进行讲解。

三、栈的结构定义

栈本质上就是一个支持动态扩容的顺序表，只是把操作限制在了一端（栈顶）。

typedef int STDataType; typedef struct Stack { STDataType* array; // 存储数据的数组 int top; // 栈顶下标（也可以用size表示元素个数） int capacity; // 容量 } Stack;

四、栈的基本操作

4.1 初始化

void StackInit(Stack* ps) { ps->array = NULL; ps->top = 0; // top指向栈顶元素的下一个位置，初始为0表示空栈 ps->capacity = 0; }

4.2 检查容量（扩容）

​void StackCheckCapacity(Stack* ps) { if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->array, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->array = tmp; ps->capacity = newCapacity; } }

4.3 入栈（Push）

void StackPush(Stack* ps, STDataType x) { assert(ps != NULL); StackCheckCapacity(ps); ps->array[ps->top] = x; ps->top++; }

4.4 出栈（Pop）

void StackPop(Stack* ps) { assert(ps != NULL); assert(ps->top > 0); // 栈不能为空 ps->top--; }

4.5 取栈顶元素（Top）

STDataType StackTop(Stack* ps) { assert(ps != NULL); assert(ps->top > 0); return ps->array[ps->top - 1]; }

4.6 判空

bool StackEmpty(Stack* ps) { assert(ps != NULL); return ps->top == 0; }

4.7 获取有效元素个数

int StackSize(Stack* ps) { assert(ps != NULL); return ps->top; }

4.8 销毁

void StackDestroy(Stack* ps) { assert(ps != NULL); free(ps->array); ps->array = NULL; ps->top = ps->capacity = 0; }

五、完整测试代码

int main() { Stack st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); printf("栈顶元素: %d\n", StackTop(&st)); // 4 while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } printf("\n"); // 4 3 2 1，正好和入栈顺序相反 StackDestroy(&st); return 0; }

六、时间复杂度分析

栈的所有标准操作都是O(1)，这也是为什么用数组实现栈是最优选择——完全不需要像顺序表那样考虑头部/中间插入删除，因为栈根本不允许这样操作。

七、栈的经典应用场景

栈在实际开发和算法题中出镜率非常高，常见应用包括：

• 括号匹配：判断字符串中的()[]{}是否匹配，利用栈"后进先出"的特性，左括号入栈，遇到右括号就弹栈比对；
• 逆波兰表达式（后缀表达式）求值：操作数入栈，遇到运算符就弹出栈顶两个元素运算，结果再入栈；
• 函数调用栈：程序运行时，每次函数调用都会在栈上开辟一块栈帧，保存局部变量、返回地址等信息，函数返回时栈帧弹出，这也是递归可能导致栈溢出（Stack Overflow）的根本原因；
• 浏览器前进后退、编辑器撤销重做（Undo/Redo）：本质上都是用栈记录历史状态；
• 深度优先遍历（DFS）：可以用递归实现，也可以用显式栈模拟递归过程，避免递归层数过深导致栈溢出。

八、数组实现 vs 链表实现栈

综合来看，实际开发和面试中，栈基本都用数组来实现，C++ STL中的stack默认底层容器也是deque（本质上也是连续存储结构的组合）。

九、总结

栈是一种操作受限的线性表，核心特性只有一句话：后进先出。它的实现并不复杂，本质上就是"只能在一端操作的顺序表"，所有标准操作的时间复杂度都是O(1)。真正的难点和考察重点在于灵活运用——括号匹配、表达式求值、单调栈、DFS模拟等，都是建立在栈这个基础结构之上的经典问题，建议在掌握实现之后，多刷一些栈相关的算法题巩固理解。

如果这篇文章对你有帮助，欢迎点赞收藏，下一篇预告：队列的实现与应用，敬请期待！