企业官网建设流程全解析

1. 从线性表到栈：为什么你写的栈总在边界上翻车

很多人第一次接触数据结构，都是从线性表开始的。数组和链表写顺了之后，觉得栈这东西简直不值一提——不就是个"后进先出"吗，一个数组加一个栈顶指针，几行代码就完事了。我当年也是这么想的，直到有一次在一个表达式求值的练习里，程序在特定输入下直接崩溃，排查了大半天才发现是栈顶指针的边界判断写漏了一种情况。从那以后我才真正意识到，栈虽然结构简单，但它的坑几乎全部集中在"边界"这两个字上。

栈本质上是一种操作受限的线性表。所谓受限，是指它的插入和删除只能在表的一端进行，这一端叫栈顶，另一端叫栈底。这个限制听起来是削弱了能力，但实际上它换来了非常清晰的语义：最后进来的元素一定最先出去。这个特性在计算机里到处都是影子，函数调用、表达式求值、括号匹配、深度优先搜索、撤销操作，背后都是栈在支撑。

用C语言实现栈，核心要解决的问题其实就三个：用什么存数据、怎么表示栈顶、以及满了和空了怎么办。这三个问题看起来简单，但每一种选择都会带来不同的代码结构和不同的坑。顺序栈用数组，链式栈用链表，两者在内存管理、扩容策略、性能表现上差别很大。这篇文章我会把这两种实现都拆开讲清楚，重点放在那些教科书上往往一笔带过、但实际写代码时最容易出问题的地方。

如果你正在学数据结构，或者准备用C语言手写一个栈来做练习项目，这篇文章应该能帮你少走一些弯路。我会从最基础的结构定义讲起，一路讲到共享栈、扩容策略、以及几个真实踩过的坑。代码都是可以直接编译运行的，你可以边看边敲。

2. 顺序栈的结构设计与栈顶指针的两种约定

2.1 用数组承载栈：结构体该怎么定义

顺序栈最自然的想法就是用数组来存元素。但光有一个数组还不够，我们还需要知道当前栈顶在哪里。所以一个完整的顺序栈结构体至少包含两部分：一个固定大小的数组，和一个标记栈顶位置的整数。

#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top; } SeqStack;

这里的top就是栈顶指针。注意我用的是"指针"这个词，但它其实是一个数组下标，不是真正的指针类型。这是数据结构里的习惯叫法，不要被误导。

结构体定义好之后，紧接着要面对一个看似不起眼但影响深远的问题：top到底指向哪里？是指向栈顶元素本身，还是指向栈顶元素的下一个空位？这两种约定都有人用，但它们的初始值和边界判断完全不同，混用就是灾难的开始。

2.2 栈顶指针指向栈顶元素：一种约定的完整推演

先看第一种约定：top始终指向当前栈顶的那个元素。那么空栈的时候没有元素，top应该是一个不可能作为有效下标的值，通常取 -1。

void InitStack(SeqStack *s) { s->top = -1; }

判断栈空就是s->top == -1。判断栈满呢？数组的有效下标是 0 到 MAXSIZE-1，既然top指向栈顶元素，那栈满时top就是 MAXSIZE-1，所以栈满条件是s->top == MAXSIZE - 1。

入栈操作要先把top加一，再往那个位置写数据：

int Push(SeqStack *s, int value) { if (s->top == MAXSIZE - 1) { return 0; // 栈满，入栈失败 } s->top++; s->data[s->top] = value; return 1; }

出栈操作先把栈顶元素取出来，再把top减一：

int Pop(SeqStack *s, int *value) { if (s->top == -1) { return 0; // 栈空，出栈失败 } *value = s->data[s->top]; s->top--; return 1; }

这套约定逻辑很直观，top的值就是当前元素个数减一。我个人比较推荐初学者用这种约定，因为"top 指向栈顶元素"这句话和代码是对得上的，不容易绕晕。

2.3 栈顶指针指向栈顶上方空位：另一种约定的推演

第二种约定：top指向栈顶元素的下一个空位置。这时候空栈的top应该是 0，因为下标 0 的位置是空的，等着第一个元素进来。

void InitStack(SeqStack *s) { s->top = 0; }

栈空条件是s->top == 0。栈满条件变成s->top == MAXSIZE，因为当top等于 MAXSIZE 时，说明 0 到 MAXSIZE-1 都已经被占满了。

入栈时先写数据再自增：

int Push(SeqStack *s, int value) { if (s->top == MAXSIZE) { return 0; } s->data[s->top] = value; s->top++; return 1; }

出栈时先自减再取数据：

int Pop(SeqStack *s, int *value) { if (s->top == 0) { return 0; } s->top--; *value = s->data[s->top]; return 1; }

这种约定的好处是top的值直接等于当前元素个数，取栈的大小不需要加减一。但坏处是入栈和出栈的自增自减顺序和第一种相反，如果你两种约定混着看，极容易写错。

2.4 两种约定的对比与选择建议

我把两种约定的关键差异整理成一张表，方便你对照：

我的建议是：选定一种就从头用到尾，不要中途换。如果你是在维护别人的代码，第一件事就是看初始化函数里top被设成了什么值，这能立刻告诉你对方用的是哪种约定。这个习惯帮我省过很多时间。

3. 链式栈：没有固定容量时的另一种活法

3.1 为什么顺序栈有时候不够用

顺序栈最大的问题是容量固定。MAXSIZE定小了不够用，定大了浪费内存。在一些场景里，你事先根本不知道会压入多少元素，比如解析一个深度未知的嵌套结构，这时候顺序栈就很尴尬。

链式栈用链表来存元素，理论上只要内存够就能一直压。它的栈顶就是链表的头节点，入栈相当于头插，出栈相当于删除头节点。因为所有操作都在头部进行，不需要遍历，时间复杂度都是 O(1)。

3.2 链式栈的节点与结构体定义

链式栈的节点和普通单链表节点一样：

typedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; int count; } LinkStack;

这里我用top直接指向栈顶节点，count记录元素个数。count不是必须的，但有了它取栈大小就是 O(1)，否则要遍历一遍。空栈时top为 NULL，count为 0。

void InitStack(LinkStack *s) { s->top = NULL; s->count = 0; }

3.3 入栈与出栈的指针操作细节

链式栈入栈就是创建一个新节点，让它指向当前的栈顶，然后更新栈顶指针：

int Push(LinkStack *s, int value) { StackNode *node = (StackNode *)malloc(sizeof(StackNode)); if (node == NULL) { return 0; // 内存分配失败 } node->data = value; node->next = s->top; s->top = node; s->count++; return 1; }

出栈要先把栈顶节点保存下来，更新栈顶指针，再释放节点：

int Pop(LinkStack *s, int *value) { if (s->top == NULL) { return 0; } StackNode *temp = s->top; *value = temp->data; s->top = temp->next; free(temp); s->count--; return 1; }

这里有一个非常经典的坑：出栈时如果先free(temp)再去读temp->data，就是访问已释放内存，结果不可预测。必须先取值、再改指针、最后释放。顺序错了，程序可能在小数据量下看起来正常，一旦跑起来就是随机崩溃。

3.4 链式栈与顺序栈的选型对照

实际选型时，如果你能预估最大规模且对性能敏感，顺序栈更合适；如果规模不确定或者频繁增删，链式栈更灵活。我做过一个括号匹配的小工具，输入长度完全不可控，用链式栈就省心很多。

4. 共享栈：两个栈共用一块空间的巧妙设计

4.1 共享栈的核心思想

共享栈是顺序栈的一个变种，让两个栈共用同一个数组，一个从下标 0 开始往右长，另一个从 MAXSIZE-1 开始往左长。当两个栈顶指针相遇时，才算真正满了。这样做的目的是提高空间利用率，特别适合两个栈此消彼长的场景。

typedef struct { int data[MAXSIZE]; int top1; // 左栈栈顶，初始为 -1 int top2; // 右栈栈顶，初始为 MAXSIZE } SharedStack;

初始化时top1 = -1，top2 = MAXSIZE。左栈入栈是top1++后写入，右栈入栈是top2--后写入。栈满的判断条件是top1 + 1 == top2，也就是两个指针相邻，中间没有空位了。

4.2 共享栈的入栈与出栈实现

int PushShared(SharedStack *s, int stackNo, int value) { if (s->top1 + 1 == s->top2) { return 0; // 共享空间已满 } if (stackNo == 1) { s->top1++; s->data[s->top1] = value; } else { s->top2--; s->data[s->top2] = value; } return 1; } int PopShared(SharedStack *s, int stackNo, int *value) { if (stackNo == 1) { if (s->top1 == -1) { return 0; } *value = s->data[s->top1]; s->top1--; } else { if (s->top2 == MAXSIZE) { return 0; } *value = s->data[s->top2]; s->top2++; } return 1; }

共享栈的坑在于两个栈的编号和方向容易搞混。我建议在代码里用宏定义LEFT_STACK和RIGHT_STACK代替裸的 1 和 2，可读性会好很多。另外要注意，共享栈满的判断是top1 + 1 == top2，不是top1 == top2，因为两个指针永远不会指向同一个位置，它们最多相邻。

5. 那些教科书不写但实际会踩的坑

5.1 出栈时忘记检查栈空

这是新手最常犯的错误。出栈函数如果不判断栈空，直接去读data[top]，当top为 -1 时就是数组越界访问。在 C 语言里，越界读可能不报错，但读到的是垃圾值，程序行为完全不可预测。更危险的是越界写，可能直接破坏其他变量的内存。

我的习惯是：任何出栈操作，第一行就是栈空判断，不通过就直接返回失败。这个检查的成本极低，但能挡掉大量莫名其妙的 bug。

5.2 入栈时忘记检查栈满

顺序栈入栈不检查栈满，top会一直加下去，最终写到数组外面。这种错误在小规模测试时往往发现不了，因为数组后面的内存可能恰好是可写的，程序看起来正常。但一旦数据量上来，或者内存布局变化，就会崩溃。

链式栈虽然理论上不会满，但malloc可能返回 NULL，这个也要判断。我见过不少代码直接对malloc的返回值解引用，在内存紧张的环境下就是必崩。

5.3 链式栈出栈时的释放顺序

前面提过，出栈时释放节点的顺序很关键。正确的顺序是：保存栈顶指针、取出数据、更新栈顶、释放旧节点。如果先释放再取数据，就是典型的 use-after-free。这个错误在单次测试里可能看不出来，因为释放后的内存内容往往还没被覆盖，但这是彻头彻尾的未定义行为。

5.4 共享栈的满判断写错

共享栈满的条件是top1 + 1 == top2。有人会写成top1 == top2，这样当两个指针相邻时还允许入栈，结果就是左栈写到右栈的位置，数据被覆盖。这个 bug 很隐蔽，因为只有在两个栈都快满的时候才会触发。

5.5 取栈顶元素和出栈混为一谈

取栈顶元素只读取不删除，top不变；出栈要删除，top要变。有些实现里把这两个操作写成一个函数，靠参数区分，很容易用错。我建议分成两个独立的函数，名字起清楚，比如GetTop和Pop，用的时候一眼就能看出意图。

6. 从括号匹配到表达式求值：栈的典型应用拆解

6.1 括号匹配：栈最直观的应用

括号匹配是理解栈的最佳入门案例。思路很简单：遇到左括号就入栈，遇到右括号就看栈顶是不是对应的左括号，是就出栈，不是就说明不匹配。扫描结束后如果栈为空，说明全部匹配。

int CheckBrackets(const char *str) { SeqStack s; InitStack(&s); for (int i = 0; str[i] != '\0'; i++) { char c = str[i]; if (c == '(' || c == '[' || c == '{') { Push(&s, c); } else if (c == ')' || c == ']' || c == '}') { if (s.top == -1) { return 0; // 右括号多了 } char topChar; Pop(&s, &topChar); if ((c == ')' && topChar != '(') || (c == ']' && topChar != '[') || (c == '}' && topChar != '{')) { return 0; // 类型不匹配 } } } return s.top == -1; // 栈空才说明全部匹配 }

这个实现里有两个容易漏的点：一是遇到右括号时栈已经空了，说明右括号多了；二是扫描结束后栈不为空，说明左括号多了。两个都要处理，缺一不可。

6.2 表达式求值：栈的进阶用法

表达式求值需要两个栈，一个存操作数，一个存运算符。核心是维护运算符的优先级：当前运算符优先级高于栈顶时才入栈，否则先弹出栈顶运算符进行计算。

这个算法的坑在于优先级的处理和括号的嵌套。左括号直接入栈，遇到右括号就不断弹出运算符计算，直到遇到左括号。整个过程要特别注意栈空的情况，因为弹出运算符时如果栈空了就是表达式有问题。

我建议先用中缀转后缀，再对后缀表达式求值，这样逻辑更清晰，调试也更容易。直接对中缀表达式求值虽然省一步，但边界情况多，容易出错。

6.3 用栈实现撤销操作

撤销是栈在交互系统里的经典应用。每次用户操作就入栈，撤销就出栈并反向执行。这个场景下栈里存的往往不是简单整数，而是操作记录结构体。用链式栈比较合适，因为操作次数不确定。

这里有个设计上的注意点：撤销栈通常需要限制最大深度，否则用户操作多了内存会一直涨。可以在入栈时判断count是否超过阈值，超过就丢弃最旧的操作，或者用循环数组实现固定容量的撤销栈。

7. 写在最后：几个我反复用到的实操习惯

栈这个结构，写出来不难，写对不容易。我这些年下来，有几个习惯是一直保持的。

第一，初始化函数里一定把栈顶指针设成明确的值，顺序栈设 -1 或 0，链式栈设 NULL，绝不依赖全局变量的默认零值。因为默认零值对顺序栈来说恰好是"指向栈顶上方空位"那种约定，如果你脑子里想的是另一种，初始化就错了。

第二，所有入栈出栈函数都返回状态码，调用方必须检查。不要写那种"假设不会出错"的代码，栈满和栈空是正常情况，不是异常。

第三，链式栈的每个malloc都配一个free，出栈时释放，销毁栈时把剩余节点全部释放。我见过太多只入不出、最后内存泄漏的实现。

第四，测试的时候一定要测边界：空栈出栈、满栈入栈、只有一个元素时出栈、连续入栈到满再连续出栈到空。这几个用例能覆盖绝大多数边界 bug。

第五，如果拿不准用哪种栈，先用顺序栈把逻辑跑通，等确认规模确实不可控了再换链式栈。过早优化存储结构，往往会让调试变得更麻烦。

这些经验谈不上高深，但都是实打实踩出来的。栈是数据结构的起点之一，把它写扎实了，后面学队列、树、图都会顺很多。