企业官网建设流程全解析

共享栈这个名字听起来朴素，但它是很多人数据结构期中考、考研408、面试手撕环节里反复出现的一个小考点，也是实际写底层代码时真能省下一块内存的实用技巧。它解决的核心问题很具体：手上有两个栈，如果各自独立开数组，就会出现一个栈爆了、另一个栈还空着一大半的尴尬局面。共享栈的做法是让这两个栈共用同一段连续空间，一个从下标 0 往右长，一个从末尾往左长，中间那堵"墙"谁先碰到谁就负责喊满。读完这篇你能搞清楚它的空间布局、指针约定、判满判空这四个最容易写错的地方、C 和 Python 两版能直接跑的代码，以及几个我踩过的坑。不管你是刚学数据结构的在校生，还是复习时想顺手把这个知识点一次吃透的开发者，都能直接照着抄作业。

1. 共享栈到底是个什么东西

1.1 从"两个数组各开一半"的浪费说起

假设你现在要写一个小模块，需要两个栈同时干活，比如一个用来存操作数、一个用来存运算符，做四则运算求值。最直觉的写法是开两个数组，各自定一个容量，比如int a[50]; int b[50];。这种写法本身没问题，但它有个隐含假设：两个栈的峰值用量差不多，谁也不比谁多太多。现实往往不是这样。

我做过一个表达式计算器，运算符栈最多同时压七八个符号就见底了，而操作数栈在处理长数字串的时候一度冲到三十多个。如果我把两个栈都定成 50，操作数栈够用，运算符栈浪费了四十多个格子；如果我精打细算给运算符栈定 10、操作数栈定 40，某天输入一个特别变态的表达式，运算符栈先炸了。这就是独立开数组的痛点：两个栈的容量是硬绑定的常量，没法互相借。

共享栈要解决的就是这个"借"的问题。它不开两块地，只开一块，两个栈从这块地的两头往中间种。谁用得多，谁就自然地多占中间那些空闲格子，不需要提前拍脑袋分配。这样同一段内存的利用率立刻上来了，代码里也不再多一个数组变量。

1.2 共享栈的空间布局：两端向中间生长

把共享栈画成一条横线，下标从左到右是0, 1, 2, ..., MaxSize-1。0 号栈的栈底定死在下标 0，它的栈顶指针从左往右推，所以叫"向右生长"；1 号栈的栈底定死在MaxSize-1，它的栈顶指针从右往左推，叫"向左生长"。中间空出来的那段，是两个栈随时可以争夺的公共区域。

用一个具体的例子感受一下。设MaxSize = 8，一开始：

• 0 号栈栈顶指针top[0] = -1，表示空；
• 1 号栈栈顶指针top[1] = 8，也表示空。

现在往 0 号栈压三个元素A、B、C，那么top[0]依次变成 0、1、2，data[0]=A、data[1]=B、data[2]=C。接着往 1 号栈压两个元素X、Y，top[1]依次变成 7、6，data[7]=X、data[6]=Y。此时的数组长这样：

两个栈顶之间还隔着下标 3、4、5 三个空格，这就是还能继续压入的空间。注意这里的关键点：两个栈的栈底是固定的，栈顶是活动的。很多初学者下意识以为栈底会动，结果画图越画越乱，一定要先把这个固定/活动的区别记牢。

1.3 简单算一笔账：空间利用率到底提升了多少

不讲大道理，直接算。假设两个栈的实际峰值分别是m和n，独立开数组就必须开m + n总容量，而且为了防溢出，实际往往要开得比峰值还大不少。共享栈只需要开m + n就够了，因为两个栈加起来最多也就占m + n个格子，公共区域会自动吸收它们用量此消彼长的部分。

更值得说的是"波动"场景。比如某个业务里，A 栈和 B 栈的用量会在运行中来回跷跷板：处理阶段 A 用 30 个、B 用 5 个；输出阶段 A 缩到 5 个、B 涨到 30 个。独立开数组为了保证两个阶段都不炸，得给 A 和 B 各开 30，总共 60 个格子，但任一时刻实际只用到 35 个左右。共享栈开 35 就稳稳够了，直接省下四成空间。

提示：共享栈省的是"两个栈峰值不同时出现"的那部分冗余，如果两个栈的峰值注定同时出现、且都很高，共享栈帮不了你多少，这一点别抱幻想。

从底层视角看，这其实就是用时间换空间的一种反向操作——它没增加任何时间复杂度，反而把内存的边角料榨干了。对一个容量固定、且两个栈用量难以预测的场景，这个设计几乎稳赚不赔。

2. 指针约定与核心判断条件

2.1 初始化：两个栈顶指针怎么摆

共享栈的初始化是整个实现的地基，摆错了后面全是坑。标准写法是两句话：top[0] = -1，top[1] = MaxSize。

为什么 0 号栈的初始栈顶是 -1 而不是 0？这是数组栈的通用约定：栈顶指针指向当前栈顶元素的下标，空栈时指向一个"无效位置"。0 号栈从下标 0 开始往上长，它的第一个元素要落在下标 0，所以空的时候栈顶必须停在 -1，这样第一次入栈时top[0]++正好变成 0，刚好指向第一个位置。如果初始化成 0，那你第一次入栈后栈顶就是 1 了，data[0]这个格子永远存不进东西，白白漏掉一个位置。

1 号栈同理，它从MaxSize-1开始往下长，第一个元素要落在MaxSize-1，所以空的时候栈顶停在MaxSize，第一次入栈top[1]--变成MaxSize-1，正好指向最后一个格子。这两句话看起来是死记硬背，其实背后是同一个逻辑：空栈的栈顶指向"即将入栈的那个位置的反方向"，也就是下一次入栈的落脚点再往外挪一格。理解了这个，你就再也不会把 -1 和 0、MaxSize 和 MaxSize-1 记混。

2.2 入栈出栈时指针怎么动

指针的移动方向是两个栈相反的，这是共享栈一切操作的关键。

0 号栈入栈：先top[0]++，再data[top[0]] = x。因为它向左往右长，每次入栈栈顶加一。0 号栈出栈：先取data[top[0]]作为返回值，再top[0]--。注意顺序，先取值后减指针。

1 号栈入栈：先top[1]--，再data[top[1]] = x。它从右往左长，每次入栈栈顶减一。1 号栈出栈：先取data[top[1]]，再top[1]++。

这个"先动指针还是先取元素"的顺序不能乱，尤其是入栈。如果 0 号栈你先写data[top[0]] = x; top[0]++;，那第一个元素会写到data[-1]，直接越界崩溃。为什么必须先加再写？因为我们的约定是"栈顶指针指向栈顶元素"，入栈前那个位置还是空的，得先把指针推进到新位置才能落笔。这个细节我在第一次手写共享栈时栽过，编译器不一定报错，但结果是灾难性的，可能默默改掉了数组外的内存。

出栈的顺序刚好相反，先取后减。因为栈顶指针此时指的是真正有元素的位置，取完这个元素之后，栈顶才该退回到下一个元素的位置。养成"入栈先移指针、出栈后移指针"的习惯，能避开九成的边界错误。

2.3 栈满与栈空：最容易写错的四个判断

共享栈的判满只有一条，但判空要分两个栈，加上判满，一共四个判断，全写在下面这张表里，建议直接背下来。

先看判满。为什么是top[0] + 1 == top[1]，而不是top[0] == top[1]？因为我们的指针语义是"指向栈顶元素的实际下标"，两个栈顶能占据的格子不能重叠。当某个栈要把新元素压进去时，它必须占用两个指针之间的那个空位。对 0 号栈来说，下一个要占的位置是top[0] + 1；对 1 号栈来说，下一个要占的位置是top[1] - 1。这两个"下一个位置"只要碰上了，就说明一个格子都不剩了，所以满的条件是top[0] + 1 == top[1]。

再看判空为什么两个栈不一样。0 号栈从 -1 起步，空就是-1；1 号栈从MaxSize起步，空就是MaxSize。它俩不可能用同一个数，这也是为什么判空函数通常要带一个"哪个栈"的参数，而不是无脑写一个统一条件。

注意：top[0] == top[1]这种写法是错的，它会让中间永远空着一个格子，空间利用率偷偷掉了 1 个位置。测试量小的时候看不出来，容量卡得很紧的时候就暴露了。

把这四个判断吃透，共享栈就没有难点了。说到底它只是一个"两个指针相向而行"的小把戏，真正要小心的是指针移动方向和判断条件的严格对应关系。

3. 手把手实现：C语言与Python两个版本

3.1 C语言版本：数组 + 双指针

先上 C 语言版本，因为数据结构课、考研基本都是这个语境，指针语义也最直观。我把完整代码贴出来，能直接编译运行。

#include <stdio.h> #include <stdbool.h> #define MAXSIZE 8 typedef struct { int data[MAXSIZE]; int top[2]; // top[0] 是 0 号栈栈顶下标，top[1] 是 1 号栈栈顶下标 } SharedStack; // 初始化：两个栈都置空 void initStack(SharedStack *s) { s->top[0] = -1; s->top[1] = MAXSIZE; } bool isEmpty(SharedStack *s, int i) { if (i == 0) return s->top[0] == -1; return s->top[1] == MAXSIZE; } bool isFull(SharedStack *s) { return s->top[0] + 1 == s->top[1]; } // i 表示操作哪个栈，取值 0 或 1 bool push(SharedStack *s, int i, int x) { if (isFull(s)) return false; if (i == 0) { s->top[0]++; s->data[s->top[0]] = x; } else { s->top[1]--; s->data[s->top[1]] = x; } return true; } bool pop(SharedStack *s, int i, int *x) { if (isEmpty(s, i)) return false; if (i == 0) { *x = s->data[s->top[0]]; s->top[0]--; } else { *x = s->data[s->top[1]]; s->top[1]++; } return true; }

3.2 逐行拆解与边界测试

先说结构体。data[MAXSIZE]是唯一的存储区，top[2]用一个长度为 2 的数组同时装下两个栈顶，这样写的好处是push和pop里可以用i来统一寻址，代码短且不容易复制粘贴出错。也有人喜欢开两个独立变量top0和top1，可读性更直白，各有取舍，我个人倾向数组，因为扩展成多栈共享时可以直接往上加。

isEmpty里对 0 和 1 分别判断，这正是前面表格里那两条空栈条件的落地。isFull只有一句，top[0] + 1 == top[1]，被push在真正写数据之前调用，保证不会越界。这个"先判满、再入栈"的顺序不能省，一旦省略，数组溢出之后行为不可预测。

pop的出口参数用int *x，把弹出的值带回去，同时用返回值true/false表示这次操作成不成功。这是 C 语言里处理"可能失败的操作"的经典套路：值走指针，状态走返回值。

写完之后一定要跑边界用例，我习惯测这四组：

1. 反复压 0 号栈直到满，验证第 8 个元素被拒绝；
2. 反复压 1 号栈直到满，同样验证满的拦截；
3. 两边交替压，验证"总共 8 个"这个总量约束，不管怎么分配；
4. 把两个栈都弹空，验证isEmpty在两栈上都能正确返回。

尤其第 3 组最有意思。下面这段测试代码把"两边都能压，但加起来不能超 8"这件事验证得明明白白：

#include <stdio.h> int main() { SharedStack s; initStack(&s); // 0 号栈压 4 个 for (int i = 0; i < 4; i++) push(&s, 0, i); // 1 号栈压 4 个 for (int i = 0; i < 4; i++) push(&s, 1, 100 + i); printf("0号栈剩空位测试: %d\n", push(&s, 0, 999)); // 应为 0 (失败) printf("栈满状态: %d\n", isFull(&s)); // 应为 1 int v; while (pop(&s, 1, &v)) printf("1号栈弹出 %d\n", v); printf("1号栈空: %d\n", isEmpty(&s, 1)); // 应为 1 printf("0号栈还能压吗: %d\n", push(&s, 0, 42)); // 应为 1 return 0; }

运行下来你会发现，两侧各占 4 个之后栈就满了，此时不管往哪个栈压都会被拒绝；而只要有一侧弹出一个，公共空间立刻让出来，另一侧马上就能继续压。这个"弹性"就是共享栈的精髓。

3.3 Python版本：换个思路写同一件事

同样一件事用 Python 写会更短，但指针语义一点都不能含糊，因为 Python 的列表越界抛异常反而能帮我们做断言。

class SharedStack: def __init__(self, capacity): self.capacity = capacity self.data = [None] * capacity self.top = [-1, capacity] def is_empty(self, i): return self.top[0] == -1 if i == 0 else self.top[1] == self.capacity def is_full(self): return self.top[0] + 1 == self.top[1] def push(self, i, x): if self.is_full(): raise OverflowError("共享栈已满") if i == 0: self.top[0] += 1 self.data[self.top[0]] = x else: self.top[1] -= 1 self.data[self.top[1]] = x def pop(self, i): if self.is_empty(i): raise IndexError("对应栈为空") if i == 0: x = self.data[self.top[0]] self.top[0] -= 1 else: x = self.data[self.top[1]] self.top[1] += 1 return x def peek(self, i): if self.is_empty(i): raise IndexError("对应栈为空") return self.data[self.top[0]] if i == 0 else self.data[self.top[1]]

代码几乎和 C 版一一对应，多了个peek方便取栈顶但不弹。有一点提醒：Python 里self.top = [-1, capacity]这种初始化非常紧凑，但如果你手滑写成self.top = [-1, capacity - 1]，1 号栈就会永远少一个可用位置，而且不会报错，只在某个用例里默默失败。这种错最烦人，所以初始化那两行我永远单独写、单独测。

3.4 时间复杂度与实现细节对比

两种语言的复杂度完全一样：入栈、出栈、判满、判空全是O(1)，这是栈这种结构的天然优势。空间上，除了data本身占MaxSize个位置，额外开销只有两个栈顶指针，常数级。

选哪个版本看场景。要追求极致性能、贴近底层内存，用 C；要快速验证逻辑、写单元测试，用 Python 更舒服。我在做算法题时经常先用 Python 把逻辑理清，再用 C 复刻一遍练手感，两版对照着看，指针语义会记得特别牢。

4. 常见问题与排查技巧实录

4.1 栈满条件写成 top1 + 1 == top2 的坑

这是我最想单独拎出来说的一条。有些人图省事，把两个栈顶叫top1、top2，然后满的条件随手写成top2 - top1 == 1。这个写法本身没错，等价于top0 + 1 == top1，但它和后面的判空条件一混，就容易埋雷。

真正的坑在别处：如果你把 0 号栈的初始值写成了 0（而不是 -1），那么判满条件还得跟着变，否则整个逻辑就错位了。我见过太多人把初始化和判满分开改，结果一个用 -1 起步、一个按 0 起步来判，程序在某次边界测试时才崩。初始化的约定和判满、判空的公式是一个整体，要么全按 -1/MaxSize 这一套来，要么就别乱动，千万不能一半一套。

排查这类问题有个笨但极其有效的办法：拿MaxSize = 2这种极端小容量手工推演一遍。容量是 2 的时候，两个栈最多各放 1 个。你手动模拟：初始化top[0]=-1, top[1]=2；0 号栈压 A，top[0]变 0；1 号栈压 B，top[1]变 1；此时top[0]+1 = 1，等于top[1]，判定为满，正确。就这么推四五个元素，任何条件写错都会当场现形。

4.2 0号栈判空到底是 -1 还是 0

这个问题的答案取决于你的栈顶指针语义，取决于你定义它是"指向栈顶元素"还是"指向下一个空位"。这两种约定在教科书里都存在，而它们把初始化、判空、判满全都改了。

用下面这张表把两套约定对齐着看，就再也不会混：

看到差别了吗？约定 B 下栈满条件反而变成了top[0] == top[1]，因为它们都指向"下一个空位"，当两个空位重合时就满了。而约定 A 下满条件是+1 ==。这两套没有对错，但你必须只选一套，并且在注释里写清楚。我在自己的代码里一律用约定 A，因为它和很多教材、和标准库栈接口的语义一致，迁移成本最低。

提示：接手别人的共享栈代码时，第一件事不是看入栈出栈，而是看初始化和判空判满这四个条件是否自洽。四个条件对不上，问题一定出在约定混用。

4.3 常见问题速查表

把实际调试中最高频的几个症状和原因整理成表，出问题的时候对着查，比从头读代码快很多。

这张表看着简单，但每一条都是真金白银踩出来的。尤其是"满栈还多一个空位"那一条，静态检查根本发现不了，只有容量卡到极限的用例才会暴露。

再补一个经验：写完之后不要只用随机数据测，一定要构造"只压一个栈直到满"和"两个栈交替压到满"两类用例。前者测单侧指针方向对不对，后者测总的容量约束对不对。这两类过了，共享栈基本就稳了。

5. 共享栈在真实场景里的影子

5.1 表达式求值与双栈配合

共享栈最经典的应用场景就是表达式求值，用两个栈，一个存操作数、一个存运算符，边扫描边计算。这种题目里两个栈的用量波动非常明显：遇到一长串数字，操作数栈猛涨；遇到一长串括号和运算符，运算符栈猛涨。用共享栈来实现，两个栈共享一块内存，谁需要谁就多占，几乎是为这个场景量身定做的。

具体做法是：给共享栈的 0 号栈存操作数，1 号栈存运算符。扫描到数字就压 0 号栈，扫描到运算符就和 1 号栈栈顶的运算符比优先级，该算就先弹出一对操作数和一个运算符做完再压回去。整个过程中两个栈的深度此消彼长，共享栈把这种波动吸收得很自然，换成两个独立数组反而要先估一个安全容量。

需要提醒的是，这种场景里"用哪个栈"一定要用常量或枚举标清楚，别在代码里到处写魔法数字 0、1，读起来太费劲。我一般会定义#define STACK_OPERAND 0和#define STACK_OPERATOR 1，一眼就知道压的是哪个栈。

5.2 从双栈共享到多栈共享的推广

双栈共享一维数组这个思路，其实可以往多栈方向推。一个常见的推广是"两个栈共享一个双向生长的空间"，再进一步，还有"多个栈共享一个数组、按需动态调整边界"的变体。这些变体在操作系统的内存管理、编译器的符号表管理里都有类似的思想：让多块逻辑上独立的区域共享一段物理空间，按实际使用量动态伸缩，而不是静态切分。

不过我得说句实在话，多栈共享的边界管理比双栈复杂得多，判满不再是两个指针相邻这么简单，需要额外的空闲块链表或者动态迁移策略，工程上很少真的去手写。共享栈真正的价值，除了它本身的实用性，更在于它训练了一种思维方式：当多个结构的使用量此消彼长、又无法预测时，用一个共享的弹性池去承接，比给每个结构预留固定的容量更划算。这个思路一旦建立，你看很多缓存池、连接池、内存分配器的设计都会有种熟悉感。

如果你正在准备数据结构考试或者面试，共享栈值得你动手照着本文的代码完整实现一遍，再把边界用例全跑通。我第一次写完只测了正常流程，觉得自己会了，结果面试时被追问"栈满条件为什么是 +1"当场卡壳。后来我逼自己用MaxSize = 2手工推演了一遍所有状态，才真正把四个判断刻进脑子。这个笨办法看着低效，但它能让你在写代码时完全不用查表，手指自然就知道该敲哪一行。至于后续想再深挖，可以拿共享栈去实现一下双栈排序、或者把它套进带最小值追踪的栈里，都是练手的好题目。