“共享栈”这个词第一次撞进视野很多人脑子里蹦出来的是并发、加锁、多线程共用一块栈内存。我当年也这么想直到翻开数据结构教材才发现它讲的是两个栈挤进同一个数组一个从下标 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为例初始状态下下标分布是这样的下标01234567归属栈 0 可用区← 空闲← 空闲← 空闲← 空闲← 空闲← 空闲← 栈 1 可用区栈顶指针top0 -1top1 8top0 -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 0top1 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._top1Python 版本看起来更干净但注意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)最后一步预期失败。步骤操作数组内容top0top1空闲槽位0初始[_, _, _, _, _]-1541push0(1)[1, _, _, _, _]0532push1(9)[1, _, _, _, 9]0423push0(2)[1, 2, _, _, 9]1414push1(8)[1, 2, _, 8, 9]1305push0(3)[1, 2, 3, 8, 9]2306push1(7)失败判满230注意第 4 步到第 5 步第 4 步结束时top0 1, top1 3判满条件top0 1 top1是2 3还没满所以第 5 步push0(3)能成功把data[2]填上。填完之后top0 22 1 3成立槽位归零。第 6 步任何一个栈再入栈都会失败因为它们共享同一个满判定。再来看一次出栈后的复用。从第 5 步的状态开始执行pop0()返回值是 3top0退回 1此时data[2]里的 3 还在但逻辑上已经不属于任何栈了。接着执行push1(7)top1从 3 减到 2data[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 工程选型的四个自问每次我考虑要不要用共享栈都会先过一遍这四个问题判断维度倾向用共享栈倾向用独立栈或动态数组元素类型两个栈元素类型一致类型不同需要 void* 或联合体负载特征两个栈此消彼长峰值错开两个栈可能同时接近上限扩容需求容量可预估、基本不需要扩需要动态增长容量不可预测代码维护单人维护、边界清晰多人协作、可读性优先现代语言里动态数组C 的vector、Java 的ArrayList、Python 的list已经把扩容这件事做得足够好普通业务代码里几乎轮不到共享栈出场。它真正有价值的地方是资源受限的环境嵌入式设备内存就那么几 KB两个栈的负载特征又明确互补这时候共享栈省下的那几百字节可能就是能不能把功能塞进去的差别。还有一个很容易被忽略的隐性成本共享栈的容量上限是硬性的。独立栈还能靠扩容续命共享栈在满的那一刻如果两个栈都在涨你除了整体扩容或者中止流程没有第三个选择。所以在容量不可预测的场景里共享栈反而更脆。5.4 一个我常用的验证套路写共享栈的代码光靠肉眼检查是不够的。我一般会准备一组固定操作序列来跑冒烟测试专门压边界先连续压栈 0 到只剩一个空位再压栈 1 占掉最后一格确认此时两个栈再入栈都返回失败然后连续弹栈 0 直到空确认弹空栈返回失败同时在弹到只剩一个元素时反复取栈顶最后把弹出的空间再用栈 1 填回去确认覆盖行为符合预期。这组序列里最关键的是“只剩一个空位时压栈 1”。很多共享栈的 bug 就藏在这一步判满用的实现如果指针状态稍有偏差会在这一刻放行一次非法写入越界到数组外面。跑通这组序列基本能拦住九成的边界错误。我在实际项目里用这套东西的次数不多但每次用都能省下真金白银的内存。印象最深的是面试里被问到共享栈的判满条件我下意识说了top0 1 top1面试官追问“为什么不是top0 top1”那一刻我才意识到自己之前一直是背下来的没真正推过。回去把区间长度公式重新推一遍之后类似的边界问题就再也没靠记忆蒙过。所以如果你只从这篇文章带走一件事我希望是把那段推导过程记住——公式会忘推导不会。