Appearance
共享栈
两个栈背对背，中间的空地就能共用
顺序栈的空间困境在上一篇已经说过：MaxSize 猜大了浪费、猜小了上溢。如果程序里要同时用两个栈，这个困境会加倍——各开一个 MaxSize/2 的数组，很容易出现"一个已经满了、另一个还空着一大半"，而空着的那一半借不出来。
共享栈的办法是：一个数组，两个栈底钉在两端，让两个栈相向生长。
text
下标: 0 1 2 ... ... MaxSize-2 MaxSize-1
[s1 s1 s1] → 空闲区 ← [s2 s2 s2 ]
↑ top1 ↑ top2栈 1 的底在下标 0，top1 向右增长；栈 2 的底在 MaxSize-1，top2 向左增长。中间的空闲区归两者共有，谁需要谁用。
两个栈的约定保持一致：top 都指向本栈的栈顶元素，空栈时指向"栈底再往外一格"。所以初值是 top1 = -1、top2 = MaxSize——这两个数不是硬记的，是约定的推论。注意栈 2 的"增长"表现为 top2 减小，方向与下标增大相反。
先看一眼
让一个栈多压几个、另一个少压几个，看中间的空闲区怎么被挤占。重点体会一个栈弹出一格，另一个栈立刻就能用上——这一格在两个独立栈的方案里是永远借不到的。
结构定义与入栈出栈
c
#define MaxSize 10
typedef struct {
int data[MaxSize];
int top1; // 栈1栈顶指针，指向栈1的栈顶元素
int top2; // 栈2栈顶指针，指向栈2的栈顶元素
} SharedStack;
// 初始化：两个指针都放在各自"栈底的外侧"
void InitStack(SharedStack *s) {
s->top1 = -1; // 栈1为空：还没占用 data[0]
s->top2 = MaxSize; // 栈2为空：还没占用 data[MaxSize-1]
}
// stackNum: 1 表示栈1，2 表示栈2
bool Push(SharedStack *s, int stackNum, int x) {
if (s->top1 + 1 == s->top2) // 栈满：空闲区为 0，两个栈都不能再入
return false;
if (stackNum == 1)
s->data[++s->top1] = x; // 栈1：指针右移一格到空位，再写入
else
s->data[--s->top2] = x; // 栈2：指针左移一格到空位，再写入
return true;
}
bool Pop(SharedStack *s, int stackNum, int *x) {
if (stackNum == 1) {
if (s->top1 == -1) // 栈1空
return false;
*x = s->data[s->top1--]; // 后缀：先取值，再指针左移
} else {
if (s->top2 == MaxSize) // 栈2空
return false;
*x = s->data[s->top2++]; // 后缀：先取值，再指针右移
}
return true;
}出栈方向与入栈严格相反：栈 1 入栈右移、出栈左移；栈 2 入栈左移、出栈右移。入栈一律用前缀、出栈一律用后缀，理由和顺序栈那一篇的不变量分析完全相同——约定是"top 指元素"，所以入栈必须先把指针挪到空位再写。
⚠️ 别把入栈写成后缀。
data[top1++] = x是先用旧下标写入、再移指针，会把新元素写到当前栈顶元素身上，把它覆盖掉；初始top1 = -1时更直接——写入data[-1]，越界。栈 2 同理，data[top2--] = x在初始top2 = MaxSize时会写data[MaxSize]，也越界。
栈满条件是推出来的
这一条不要背，因为题目常把栈 2 的约定改掉。按本篇的约定数一数：
- 栈 1 占用
data[0 .. top1]，共top1 + 1个单元； - 栈 2 占用
data[top2 .. MaxSize-1]，共MaxSize - top2个单元； - 空闲区是
data[top1+1 .. top2-1]，共top2 - top1 - 1个单元。
"栈满"的含义就是空闲区大小为 0：
也就是两个栈顶指针相邻。由它直接读出三个推论：
- 🔴 共享栈不牺牲存储单元。 满时总元素数
，整个数组一个空位都不剩。这一点常被拿来与循环队列的"牺牲一个单元"方案对比——共享栈有两个独立指针，不会出现"相等即歧义"的情况，所以不必留空位。 - 🔴 判满两栈共用，判空各栈各自。 只要两针相邻，两个栈都不能再入；而判空是
top1 == -1与top2 == MaxSize两条独立条件。混淆这两者，是本篇最容易出的错。 - 🔴 判满误写成
top1 == top2会晚拦一步。 两针相邻时该条件还不成立，于是这次入栈被放行，++top1之后才变成top1 == top2——而这一次入栈已经把对方的栈顶元素覆盖掉了。等下一次入栈被拦住时，数据早就丢了。反过来说，在正确的实现里top1 == top2是不可达状态。
配套的几个查询也都是一行的事：
c
bool IsEmpty1(SharedStack *s) { return s->top1 == -1; }
bool IsEmpty2(SharedStack *s) { return s->top2 == MaxSize; }
bool IsFull (SharedStack *s) { return s->top1 + 1 == s->top2; }
int Length1(SharedStack *s) { return s->top1 + 1; } // 栈1元素个数
int Length2(SharedStack *s) { return MaxSize - s->top2; } // 栈2元素个数
int FreeCells(SharedStack *s) { return s->top2 - s->top1 - 1; } // 剩余空位用 MaxSize = 4 把边界跑一遍（想手工验一遍就展开）
初始 top1 = -1, top2 = 4，空闲区
| 操作 | top1 | top2 | 数组内容 | 判满 top1+1==top2 |
|---|---|---|---|---|
| 初始 | 4 | [_ _ _ _] | ||
| 栈1 压 A | 0 | 4 | [A _ _ _] | |
| 栈2 压 X | 0 | 3 | [A _ _ X] | |
| 栈1 压 B | 1 | 3 | [A B _ X] | |
| 栈1 压 C | 2 | 3 | [A B C X] | |
| 再压任何栈 | — | — | — | 拒绝入栈 |
| 栈2 弹 X | 2 | 4 | [A B C _] |
最后一行是共享栈的价值所在：栈 2 让出一格，栈 1 立刻就能用。
它到底省了什么
假设程序里要同时用两个栈，总共最多存
| 方案 | 何时上溢 | 空间利用 |
|---|---|---|
| 两个独立顺序栈，各分配 | 任一个栈的元素数超过 | 差：一个满了另一个可能还空着一大半 |
| 共享栈，共用 | 两个栈元素数之和超过 | 好：一个栈可以占用远超一半的空间 |
举个具体数字：
注意共享栈并没有增加总空间，它只是把"哪个栈用多少"的决定权从编译期推迟到了运行期——典型的用"延迟绑定"换灵活性。所以它成立的前提是两个栈此消彼长：一个用得多时另一个用得少。若两个栈同时增长到接近
入栈、出栈、判空判满、求任一栈长度全是
换一种约定：栈 2 的指针指向空位（题面改了约定时展开）
题目常把栈 2 的约定改成"top2 指向下一个入栈位置（空位）"，初值 top2 = MaxSize - 1， 入栈写成 data[top2--] = x。此时所有结论都要重推——推法仍然是"空闲区有多大"：
- 栈 1 占
data[0 .. top1]，共top1 + 1个（约定不变）； - 栈 2 占
data[top2+1 .. MaxSize-1]，共MaxSize - 1 - top2个； - 空闲区是
data[top1+1 .. top2]，共top2 - top1个。
于是栈满条件变成 top1 == top2：
| 项 | top2 指元素（本篇默认） | top2 指空位 |
|---|---|---|
| 初值 | top1 = -1，top2 = MaxSize | top1 = -1，top2 = MaxSize - 1 |
| 栈 2 判空 | top2 == MaxSize | top2 == MaxSize - 1 |
| 栈 2 入栈 | data[--top2] = x（先移后写） | data[top2--] = x（先写后移） |
| 栈 2 出栈 | x = data[top2++]（先读后移） | x = data[++top2]（先移后读） |
| 栈满 | top1 + 1 == top2 | top1 == top2 |
| 空闲区大小 | top2 - top1 - 1 | top2 - top1 |
用 MaxSize = 4 复核第二列：初始 top1 = -1, top2 = 3，空闲 top1 = 0，空闲 3）→ 栈 2 压 X（写 data[3]，top2 = 2，空闲 2）→ 栈 1 压 B（top1 = 1，空闲 1）→ 栈 1 压 C（top1 = 2，空闲 0，top1 == top2 == 2，满）。 数组 [A B C X] 四格全用上 ✓。
上面这张表正是"推导比记忆重要"的理由：top1 + 1 == top2 只是某一种约定下的答案，题目改一个字，答案就变；而"空闲区大小为 0"这句话永远不变。
为什么不能三个栈共享
不能用这种方式。 共享之所以成立，是因为它把两个栈的栈底固定在数组的两个端点上，让它们相向增长——增长方向背对背，中间的空闲区被两者共享，且每个栈的边界只有一侧会动。
一维数组只有两个端点。第三个栈的栈底只能放在中间某处，那么它的增长会与左右两边同时冲突，必须引入"整体搬移"才能维持，
被追问时，正确的回答不是"因为数组只有两端"这句结论，而是"因为需要每个栈只有一侧边界会移动，而一维空间里满足这一点的位置只有两个端点"。
考点速记
这一节不单独成题。 共享栈是顺序存储下的一种空间优化方案，它在卷面上的出现方式是作为设计题的备选方案或判断题里的一个选项——问栈满条件是什么、能不能存满 MaxSize 个元素、为什么最多只能两个栈共享。所以这一篇要会的是推导，不是背条件。
三条会被调用的结论：
- 栈满条件
top1 + 1 == top2是从"空闲区为 0"推出来的，改约定就重推。 - 共享栈不牺牲存储单元，满时可以存满
MaxSize个——常被拿来与循环队列"牺牲一个单元"的方案对照。 - 判满共用、判空各自。
易错：判满写成
top1 == top2。 它比正确条件晚拦一步，那一步已经把对方的栈顶元素覆盖了。
易错：栈 2 的入栈方向写反。 栈 2 向低地址生长，入栈是
--top2、出栈是top2++。
易错：把两个栈的判空条件也写成共用的。 判满才共用；判空是各自独立的两条。
教材出处
- 两栈共享一个数组空间的做法（栈底分别设在数组的两端、栈顶相向而行、 仅当两个栈顶相遇时才判定为满）：本篇按"空闲区大小为 0"重新推导， 严蔚敏《数据结构（C 语言版）》（第 2 版）p58 3.2.1 节在讨论顺序栈的空间分配时 提到了"两栈共享空间"的思路。
相关知识
顺序栈（单栈实现，本篇的推导方法来自那里）｜ 链栈（容量完全不可预估时的另一条路）｜ 循环队列（同样面对"判空判满会撞车"的问题，但解法不同）｜ 栈和队列的基本概念