企业官网建设流程全解析

“共享栈”这个词第一次撞进视野，很多人脑子里蹦出来的是并发、加锁、多线程共用一块栈内存。我当年也这么想，直到翻开数据结构教材才发现，它讲的是两个栈挤进同一个数组，一个从下标 0 往右长，一个从 MaxSize-1 往左长，中间那片空地谁先占谁用，跟并发一点关系都没有。这个反差本身就挺有意思——一个听起来很“系统级”的名字，内核却是一个纯粹的空间划分技巧。

但别被它的简单骗了。共享栈真正的价值不在数据结构本身，而在于它把“数组下标边界”这件事的坑一次性全摆到了你面前：初始化写成什么样、判空怎么写、判满条件是一个等号还是两个、出栈顺序会不会踩到对方地盘，每一条都卡在边界上，写错一个符号程序照样跑，但结果是静默错的。这篇文章我打算把共享栈从设计动机、指针约定、完整代码、边界推演一路讲到它的思想迁移，该手写的一行不省，该算的账一笔不漏。适合正在啃数据结构的同学，也适合工作几年后想回头把这些基础边界捋清楚的开发者——毕竟越是基础的东西，越容易在面试和线上事故里咬人。

1. 两个栈塞进一个数组：共享栈到底在省什么

1.1 定长顺序栈的浪费，往往藏在你不会去算的地方

顺序栈用一段连续数组实现，用之前必须先定容量。这事看起来无害，问题出在“两个栈”这个场景上：假设某个模块里有两个逻辑上独立、但生命周期重叠的栈，各自开了 1000 个元素的空间。跑一段时间后，栈 A 压了 980 个元素，栈 B 只有 30 个。总占用 1010/2000，一半多的空间在睡觉，可栈 A 再来 21 个元素就直接溢出。

这时候你有两条路：要么给栈 A 单独扩容，申请更大的数组、把已有的 980 个元素搬过去、释放旧空间——一次 O(n) 的搬移外加一次可能失败的内存分配；要么整个流程报错退出。两条路都不舒服。更尴尬的是，栈 B 那块闲着的大片空间完全帮不上忙，因为从语言层面看，它们是两块毫不相干的内存。

共享栈要干的事很直接：既然两个栈的负载此消彼长、不会同时顶到上限，那就把它们放进同一块数组，让空闲的部分可以互相“借”。这不是压缩总容量，而是把容量的使用方式从“各管各的”改成“共享同一池子”。

1.2 从两端向中间长：一次理解布局

共享栈的布局可以用一句话概括：栈 0 从数组低地址端向高地址端生长，栈 1 从高地址端向低地址端生长，中间的空闲区是两者共用的缓冲带。

以MaxSize = 8为例，初始状态下下标分布是这样的：

top0 = -1表示栈 0 空，top1 = 8表示栈 1 空，注意这里的 8 比最大下标还大一位，不是笔误，后面第 2 章会把这个约定的理由讲透。随着元素进出，两个指针会朝彼此靠近，中间的空白条越来越窄，直到某一刻它们“贴”在一起，那就是整个共享栈满了。

这里有一个很多人第一遍会忽略的事实：共享栈满，不等于两个栈各自满。它只要求两个栈的元素总数不超过MaxSize。栈 0 压 7 个、栈 1 压 1 个，照样是满的；反过来栈 0 压 0 个、栈 1 压 7 个，也满。容量的分配权交给了运行时的实际负载，而不是你提前拍脑袋写的两个常量。

1.3 它改变的不是容量数字，而是溢出条件的形状

把共享栈理解成“省内存”其实是走偏的。它的总容量还是MaxSize，一个字节都没多。真正变化的是溢出判定条件的形式：

• 两个独立栈：栈 0 溢出当且仅当len0 > MaxSize，栈 1 溢出当且仅当len1 > MaxSize，两者互不影响。最坏情况下你需要的总空间是两倍，因为必须假设两个栈同时顶满。
• 共享栈：整体溢出当且仅当len0 + len1 > MaxSize。最坏情况下的需求就降到了一个MaxSize。

也就是说，它把“加法约束”换成了“总量约束”。在概率上，两个栈同时达到各自峰值的可能性远小于它们峰值错开——这正是它能省空间的理论依据。如果你的场景里两个栈确实会同时顶满，那共享栈一点好处都捞不到，反而多了一堆边界判断的复杂度，这时候老老实实开两个独立栈才是对的。

2. 指针约定：从 top0 = -1 到 top1 = MaxSize 的每一步理由

2.1 两个栈顶指针的初始化为什么故意不对称

先把这个最容易被记混的地方说清楚。共享栈同一种初始化有两种写法，区别在于栈顶指针指向哪里。

约定 A：栈顶指针指向栈顶元素本身。空栈时栈 0 的top0 = -1（栈里没有元素，指向“上一个”位置），栈 1 的top1 = MaxSize（同样没元素，指向数组末尾之外的那一格）。这是绝大多数教材采用的约定，也是本文后续代码使用的约定。

约定 B：栈顶指针指向栈顶元素的下一个可用位置。空栈时top0 = 0，top1 = MaxSize - 1，因为它指向的是即将写入的位置。

两种约定本身没有对错，但绝不能在同一个实现里混用。我见过最典型的翻车是：初始化的时候按约定 A 写top1 = MaxSize，入栈的时候却按约定 B 写data[top1--]，结果第一次入栈就把元素写到了data[MaxSize]越界位置。两者差一步，编译器不会提醒你，运行时要看运气。

top0和top1初始化不对称，根源在于两个栈的生长方向相反。栈 0 往右长，它的“下一个空位”是top0 + 1；栈 1 往左长，它的“下一个空位”是top1 - 1。为了保持“先移动指针、再写数据”这个统一节奏，两个初值就必须一个在数学左侧之外（-1），一个在数学右侧之外（MaxSize）。

2.2 入栈出栈时，指针到底怎么动

把操作拆到指针级别，共享栈的所有行为就变成了四句话：

• 栈 0 入栈：++top0，然后data[top0] = x。指针先加，再加完指向的就是新写入的位置。
• 栈 1 入栈：--top1，然后data[top1] = x。指针先减，减完指向新写入的位置。
• 栈 0 出栈：先x = data[top0]，再top0--。先取值，取完再退回去。
• 栈 1 出栈：先x = data[top1]，再top1++。同理。

这四步的方向记混一次，整个栈就会往反方向跑。我的记忆方法是看“指针指向栈顶元素”这个约定，指针永远站在它管的那个元素的脚下：栈 0 的元素在低地址，指针往前走是加；栈 1 的元素在高地址，指针往前走是减。写代码之前先在纸上把push0和push1各走一遍，比盯着屏幕改 bug 快得多。

2.3 判空条件：两种约定写出来的式子不一样

按约定 A，栈 0 空的条件是top0 == -1，栈 1 空的条件是top1 == MaxSize。这两个式子看起来别扭，但逻辑是一致的：指针退回到了“栈里面第一个位置的前一格”。

按约定 B，栈 0 空是top0 == 0，栈 1 空是top1 == MaxSize - 1。写法上更整齐，但代价是判满和取栈顶都要多一次偏移运算。

我个人的偏好是约定 A，原因是取栈顶元素时可以直接写data[top0]，不需要写data[top0 - 1]。在写循环、做批量出栈的时候，少一层偏移能少一堆 off-by-one 的怀疑。关键是选定之后就别换，把约定写进代码注释里。

2.4 判满条件 top0 + 1 == top1 的完整推导

这是全书最容易背错的一个式子。我不背它，每次用的时候现场推一遍。

栈 0 占用的下标区间是[0, top0]，栈 1 占用的区间是[top1, MaxSize - 1]。中间空闲区是[top0 + 1, top1 - 1]。空闲区的长度是：

(top1 - 1) - (top0 + 1) + 1 = top1 - top0 - 1

空闲区长度为 0 就是满栈：

top1 - top0 - 1 = 0

移项得到top0 + 1 == top1。这就是那个式子的来历。它不是凑出来的，而是从区间长度推出来的。推导过程还有一个副产品：任意时刻共享栈的空闲槽位数恰好等于top1 - top0 - 1，调试的时候可以直接打印这个值。

至于写==还是>=，正常流程里每次只移动一格，==完全够用。但如果你想写得更防御一点——比如担心外部代码直接改了指针、或者未来加并发——写成top0 + 1 >= top1更安全，因为即使指针被搞乱了，判满逻辑也不会误判成“还有空间”。

2.5 长度计算与取其反的对称性

栈 0 的长度：top0 - (-1) = top0 + 1。 栈 1 的长度：MaxSize - top1。 总长度：top0 + 1 + MaxSize - top1。

这三个式子里最值得记的是它们背后的对称性：栈 0 的长度是把-1当作“虚拟栈底”，栈 1 的长度是把MaxSize当作“虚拟栈底”。也就是说，-1和MaxSize这两个初值并不是随便选的，它们代表了两个栈“逻辑上的起点”，只不过起点落在数组之外。理解了这一点，判空公式top0 == -1、top1 == MaxSize就变得非常自然了——长度算出来是 0，栈当然是空的。

3. 从零手写：C 与 Python 两版实现的逐行对照

3.1 C 语言版本：结构体定义与五个核心操作

C 是写共享栈最顺手的语言，因为数组边界是你亲手管的，任何越界都怪不到别人头上。

#include <stdbool.h> #define MaxSize 100 typedef struct { int data[MaxSize]; int top0; /* 栈0栈顶下标，空栈为 -1 */ int top1; /* 栈1栈顶下标，空栈为 MaxSize */ } SharedStack; void InitStack(SharedStack *S) { S->top0 = -1; S->top1 = MaxSize; } bool StackEmpty(const SharedStack *S, int no) { if (no == 0) return S->top0 == -1; return S->top1 == MaxSize; } bool StackFull(const SharedStack *S) { return S->top0 + 1 >= S->top1; } bool Push(SharedStack *S, int no, int x) { if (StackFull(S)) return false; /* 整体满，无论压哪个栈都失败 */ if (no == 0) S->data[++S->top0] = x; else S->data[--S->top1] = x; return true; } bool Pop(SharedStack *S, int no, int *x) { if (StackEmpty(S, no)) return false; /* 该栈自己空，出不了 */ if (no == 0) *x = S->data[S->top0--]; else *x = S->data[S->top1++]; return true; } bool GetTop(const SharedStack *S, int no, int *x) { if (StackEmpty(S, no)) return false; if (no == 0) *x = S->data[S->top0]; else *x = S->data[S->top1]; return true; } int StackLength(const SharedStack *S, int no) { if (no == 0) return S->top0 + 1; return MaxSize - S->top1; }

这里有两个设计决定值得说一句。第一，Push里判满用的是整体判满StackFull(S)，因为共享栈的满是一个全局状态，跟你要压哪个栈无关。第二，Pop和GetTop里判的是“该栈自己空”，用的是StackEmpty(S, no)，这两者不能混。我第一次写的时候就犯过把Pop里也写整体判满的错误，结果栈 0 明明还有元素，栈 1 却是空的，出栈操作被整体判满挡住，逻辑全乱。

另外注意Push的返回值是bool，用返回值而不是直接exit或断言，是为了让调用方决定怎么处理失败。嵌入式环境里栈满可能是常态，直接退出比溢出还糟。

3.2 Python 版本：语言帮你藏起来的坑

同一个结构翻译到 Python，代码短了，但坑换个地方冒出来。

class SharedStack: def __init__(self, size): self._max = size self._data = [None] * size self._top0 = -1 self._top1 = size def is_full(self): return self._top0 + 1 >= self._top1 def is_empty(self, no): if no == 0: return self._top0 == -1 return self._top1 == self._max def push(self, no, value): if self.is_full(): raise OverflowError("共享栈已满") if no == 0: self._top0 += 1 self._data[self._top0] = value else: self._top1 -= 1 self._data[self._top1] = value def pop(self, no): if self.is_empty(no): raise IndexError("该栈为空") if no == 0: value = self._data[self._top0] self._top0 -= 1 else: value = self._data[self._top1] self._top1 += 1 return value def length(self, no): if no == 0: return self._top0 + 1 return self._max - self._top1

Python 版本看起来更干净，但注意pop里如果不写is_empty检查，栈 0 空的时候self._data[self._top0]就是self._data[-1]——Python 不会报错，它会老老实实返回数组最后一个元素。这个 bug 非常阴险，因为程序不崩，只是数据悄悄错了，等你发现的时候可能已经跑了几十万条记录。

提示：用 Python 实现这种“指针式”数据结构时，凡是用负数下标取数组元素的地方，都要先确认这真的是你想要的语义。data[-1]在 Python 里永远合法，这是它和 C 之间最危险的一条差异。

3.3 跟着指针走一遍：MaxSize = 5 的完整推演

光看代码不够，我们把MaxSize = 5的每一帧都画出来。操作序列是：push0(1) → push1(9) → push0(2) → push1(8) → push0(3) → push1(7)，最后一步预期失败。

注意第 4 步到第 5 步：第 4 步结束时top0 = 1, top1 = 3，判满条件top0 + 1 >= top1是2 >= 3，还没满，所以第 5 步push0(3)能成功，把data[2]填上。填完之后top0 = 2，2 + 1 >= 3成立，槽位归零。第 6 步任何一个栈再入栈都会失败，因为它们共享同一个满判定。

再来看一次出栈后的复用。从第 5 步的状态开始，执行pop0()，返回值是 3，top0退回 1，此时data[2]里的 3 还在，但逻辑上已经不属于任何栈了。接着执行push1(7)，top1从 3 减到 2，data[2] = 7直接覆盖掉了刚才那个 3。这是共享栈正常且必要的行为——被弹出的位置重新变成公共空闲区，谁先来谁用。如果你在调试时看到“刚弹出的值还在数组里”，那不是 bug，只是逻辑上它已经失效了。

4. 边界与异常：共享栈最容易翻车的几个地方

4.1 判满用 == 还是 >=，取决于你有多不信任调用方

前面代码里我用的是top0 + 1 >= S->top1。正常流程下==完全够，因为每次操作只移动一格，指针不可能一次跳两格。但在真实项目里，指针被写坏的方式比你想的多：外部代码为了调试直接改了结构体字段、多线程并发导致指针交错更新、序列化反序列化时字段对不上。这些情况下一旦top0越过了top1，==判满就完全失效，程序会继续往中间压，两个栈的数据互相踩踏。

用>=的代价是零，收益是即使指针暂时错乱，判满逻辑也能先兜住。这是典型的防御性写法，我在任何需要长期维护的代码里都会用>=。顺带一提，判空也可以用类似思路：top0 < -1这种异常状态用== -1是判不出来的。

4.2 取栈顶元素前忘记判空，是最高频的事故

GetTop和Pop必须判空，这一条写在任何教科书里，但真实项目里漏掉的比例高得吓人。原因很简单：写的时候脑子想的是“这个栈这时候肯定有东西”，过两个月代码改了几轮，前面多了个出栈操作，这里的假设就不成立了。

C 语言里data[top0]在top0 = -1时是越界读，行为未定义，可能拿到垃圾值，可能触发行错误，也可能恰好什么都不发生。Python 里data[-1]是合法访问，会拿到最后一个元素，看起来“有值”，其实取错了。两种语言都不会给你一个清晰的报错，这就是它危险的地方。

我的习惯是：所有对外暴露的栈操作，入口第一件事就是判空/判满，没有例外。如果性能敏感想省掉这个判断，那就把这个函数标记成内部接口，并且写注释说明调用方负责保证前置条件。把责任明确下来，比默默省略检查安全得多。

4.3 两个栈的元素类型必须一致，这是个硬约束

共享栈在物理上只是一块连续内存，两个栈是对同一块内存的两种逻辑视图。这意味着它们存储的元素类型必须同构，因为底层是一个真正的数组int data[MaxSize]。

如果栈 0 需要存整数、栈 1 需要存字符串指针，直接共用这个数组就不行了。可行的绕法是改成void* data[MaxSize]或者用联合体，但那样每个元素多占一个指针的空间，判满和长度计算不变，取用的时候却要自己做类型转换。这时候你就得算一笔账：省下的那点空间，够不够抵消类型转换带来的复杂度和出错概率？

类型约束还带来一个使用上的限制：栈 0 和栈 1 无法独立扩容。独立栈可以在自己的空间不足时单独realloc，共享栈一旦要扩，两个栈顶指针都得跟着调，而且扩容后数组地址变了，如果外部还持有指向某个元素的指针，全部失效。这也是它在工程里少见的直接原因。

4.4 并发场景下，判满和移指针之间有个致命间隙

多线程同时往里压数据时，StackFull的判断和指针的移动必须是原子的。否则会出现：线程 A 判满通过，正准备写；线程 B 也判满通过，也准备写；两个线程都以为自己占到了最后一个空闲槽，结果其中一个写到了另一个的位置上，或者干脆越界。

修法不外乎两种。粗粒度的是一个互斥锁把整个共享栈包起来，简单但两个栈互相阻塞，违背了共享栈让两个栈独立工作的初衷。细粒度的是给两个栈各配一把锁，但判满逻辑是全局的，仍然需要一个共享的计数或原子变量来同步空闲槽位。真到了这一步，用std::atomic加 CAS 循环也好，干脆改用无锁队列也好，代码复杂度都会上去一个大台阶。

我的判断是：共享栈适合单线程或单生产者场景。多线程下如果你发现自己需要给共享栈加锁，那省下来的那点内存很可能不值这份复杂度，不如退回两个独立栈各自加锁。

5. 比共享栈本身更值钱的两件事：思想迁移与选型判断

5.1 一块连续空间配两个反向分配器，这个模式到处都是

把共享栈的骨架抽象出来：一段连续内存，两个分配器从两端相向分配，中间的空白是共享缓冲。这个模式在别的地方反复出现。

最接近的是双端队列。很多双端队列的底层实现就是环形缓冲或双端数组，头尾两个指针相向或同向移动，中间是可用空间。它和共享栈的区别在于两端是同一个逻辑容器的两个接口，而共享栈是两个独立容器共享一块存储。骨架相同，语义不同。

再往外一层是有序数组上的相向双指针。判断回文串时左指针右移、右指针左移，相遇即结束；有序数组求两数之和时也是首尾指针相向逼近。这些算法的正确性依赖同一个事实：[0, left]和[right, n-1]是两块确定的区域，中间(left, right)是尚未探索的区间。和共享栈的[0, top0]、[top1, MaxSize-1]、(top0, top1)完全同构。你在共享栈里搞清楚的边界推导，换到双指针题上可以原样复用。

5.2 三个以上的栈想共享一块空间，就得换思路了

共享栈的漂亮之处在于两个栈的方向天然相反，可以直接把数组一劈两半。这个性质一旦扩展到三个或更多栈就不成立了——你没法让三个指针同时向中间生长还互不干扰。

经典的做法有这么几种。第一种是均分：把数组切成 k 份，每个栈独占一份，满了再想办法。问题很明显，又回到了最开始那个“一个满一个闲”的老麻烦上，只是规模变成了 k 倍。

第二种是整体搬移：给每个栈记录栈底和栈顶，当某个栈满了，看它右边有没有空闲块，有的话就把右边所有栈整体往右挪一段，像整理书架一样给满的那个栈腾位置。搬移的代价是 O(n)，但均摊到每次操作上还能接受，关键是要挑一个合适的搬移时机，别每次满了才挪。这个方法实现复杂，写起来容易出错，一般只在特定的存储管理场景里出现。

第三种是放弃数组，改用链式栈。多个链式栈可以任意共享内存池，每个节点单独分配，不存在空间切割的问题。代价是失去了数组的随机访问和连续存储带来的缓存友好性，每个节点还多一个指针开销。

这三种方案的存在本身就说明了共享栈的适用边界：它的最佳使用场景就是两个栈，多了不合适，少了没必要。

5.3 工程选型的四个自问

每次我考虑要不要用共享栈，都会先过一遍这四个问题：

现代语言里，动态数组（C++ 的vector、Java 的ArrayList、Python 的list）已经把扩容这件事做得足够好，普通业务代码里几乎轮不到共享栈出场。它真正有价值的地方是资源受限的环境：嵌入式设备内存就那么几 KB，两个栈的负载特征又明确互补，这时候共享栈省下的那几百字节可能就是能不能把功能塞进去的差别。

还有一个很容易被忽略的隐性成本：共享栈的容量上限是硬性的。独立栈还能靠扩容续命，共享栈在满的那一刻，如果两个栈都在涨，你除了整体扩容或者中止流程，没有第三个选择。所以在容量不可预测的场景里，共享栈反而更脆。

5.4 一个我常用的验证套路

写共享栈的代码，光靠肉眼检查是不够的。我一般会准备一组固定操作序列来跑冒烟测试，专门压边界：先连续压栈 0 到只剩一个空位，再压栈 1 占掉最后一格，确认此时两个栈再入栈都返回失败；然后连续弹栈 0 直到空，确认弹空栈返回失败，同时在弹到只剩一个元素时反复取栈顶；最后把弹出的空间再用栈 1 填回去，确认覆盖行为符合预期。

这组序列里最关键的是“只剩一个空位时压栈 1”。很多共享栈的 bug 就藏在这一步：判满用==的实现如果指针状态稍有偏差，会在这一刻放行一次非法写入，越界到数组外面。跑通这组序列，基本能拦住九成的边界错误。

我在实际项目里用这套东西的次数不多，但每次用都能省下真金白银的内存。印象最深的是面试里被问到共享栈的判满条件，我下意识说了top0 + 1 == top1，面试官追问“为什么不是top0 == top1”，那一刻我才意识到自己之前一直是背下来的，没真正推过。回去把区间长度公式重新推一遍之后，类似的边界问题就再也没靠记忆蒙过。所以如果你只从这篇文章带走一件事，我希望是把那段推导过程记住——公式会忘，推导不会。