企业官网建设流程全解析

写表达式求值、括号匹配这类算法题的人，多半都遇到过这样一个尴尬场面：一个栈常年半空，另一个栈动不动就溢出。你明明给两块栈各分了一半内存，可实际跑起来，常常是一个饿死、一个撑死。共享栈这个结构，就是冲着这个浪费来的。它把两个栈塞进同一段连续空间，一个从这头往中间长，一个从那头往中间长，谁需要谁就多占一点，只有当两边真正撞上时才算满。我最早是在看数据结构教材里的“两栈共享空间”时接触到它，当时觉得这就是个考试知识点，后来在做表达式求值、撤销重做缓存、以及自己写小型虚拟机的时候，发现它其实相当实用。这篇文章会把共享栈的来龙去脉、边界条件、完整实现、坑点和排查方法全部讲清楚，适合正在准备数据结构考试的同学、刚入行想补基础的开发者，以及需要在资源受限环境下榨出一点内存的人。

1. 共享栈到底解决什么问题：从两个栈抢内存说起

1.1 一个真实的内存浪费场景

先还原一个具体场景。假设你要写一个中缀表达式转后缀表达式的程序，标准做法是准备两个栈：一个存操作数，一个存运算符。你预算了 200 个元素的空间，于是很自然地各分 100。问题是，输入一个像1+2+3+4+5这样的表达式时，操作数栈会堆很多数，而运算符栈最多同时压一层；反过来，遇到((((((1))))))这种深度嵌套的括号，运算符栈又会被括号塞满，操作数栈几乎空着。这种“一方吃紧、一方闲置”的错配，在栈容量固定时几乎是常态。

单独分配两个栈的根本问题在于，你无法预知两个栈各自的峰值，只能按最坏情况各留一份余量。余量留少了某个栈会溢出，留多了就是纯浪费。更要命的是一些嵌入式场景，比如单片机上的命令行解析器，总共可能就几 KB 的可用内存，你根本没有余量可以浪费。

共享栈的思路很直接：既然两个栈不会同时到达各自的峰值，那就让它们共用一整块空间，用动态的边界来分配，谁在用就多给谁一点。这本质上是一种非常朴素的“内存池”思想，只不过池子里只有两个用户，而且这两个用户的增长方向是相向的。

注意，免费的内存共享永远有代价：共享栈的总容量是固定的，它换取的是“平均利用率更高”，但并没有凭空变出空间。当两个栈真的同时接近峰值时，它依然会满，只是满得更晚、更体面。

1.2 核心约定与边界条件，先把它钉死

共享栈的全部精妙，都集中在两个指针的约定上。以容量为maxSize的数组data为例：

• 左栈（记作栈 1）的栈底固定在数组下标 0，栈顶指针top1初始为-1，每压入一个元素，top1加一。
• 右栈（记作栈 2）的栈底固定在数组末尾maxSize - 1，栈顶指针top2初始为maxSize，每压入一个元素，top2减一。

这里top2的初值为什么是maxSize而不是maxSize - 1？这是最容易被记错的地方。把top2看成“下一个可写入位置”的右边界更直观：栈 2 的第一个元素应该写在maxSize - 1，所以写入前先执行--top2，那初始值自然要设在maxSize。这样两个栈共享同一套“指针指向栈顶元素”的语义，判定逻辑才统一。

由此推出四条关键判定：

• 栈 1 空：top1 == -1
• 栈 2 空：top2 == maxSize
• 栈满：top1 + 1 == top2，两边指针贴在一起，中间没有空隙
• 当前元素总数：(top1 + 1) + (maxSize - top2)

注意栈满条件是top1 + 1 == top2，不是top1 == top2。这个“差一”关系是所有出错的源头：一旦写成top1 == top2，最后一个空位会被当场覆盖，两个栈的值互相污染，而且这种 bug 在测试数据不极端时经常不触发，非常隐蔽。

1.3 为什么是两个栈，而不是三个或更多

教科书大多只讲两栈共享，这不是偷懒。两个栈能做到“相向生长且互不干扰”，是因为它们的增长方向恰好只有两条：从低地址往高地址、从高地址往低地址。空间被两端的增长夹在中间，边界只有一个接触面，判定简单。

三个栈就麻烦了。三个方向在一条线上没有解，它们终会互相交错；要么引入更复杂的分段管理，要么退化成给每个栈划固定区间，那又回到了浪费的老路。真要在多栈之间动态调度，实用的做法是链式存储或维护一个空闲块链表，让每个栈的块按需伸