Appearance
共享栈
为什么需要共享栈
使用两个独立的栈时，如果一个栈满而另一个栈几乎为空，存储空间就被浪费了。共享栈的思路是：让两个栈共享同一片数组空间，各自从数组的两端向中间生长，从而更充分地利用存储空间。
408 考研中，共享栈是栈的顺序存储章节的重要考点，常以选择题、填空题的形式出现。
核心思想
用一个大小为 MaxSize 的数组 data 同时存放两个栈：
- 栈 1：栈底在下标
0，入栈时top1从左向右增长 - 栈 2：栈底在下标
MaxSize-1，入栈时top2从右向左增长
两个栈相向生长，共同利用中间的空闲空间：
下标: 0 1 2 ... ... MaxSize-2 MaxSize-1
[s1 s1 s1] → 空闲区 ← [s2 s2 s2 ]
↑ top1 ↑ top2数据结构定义：
c
#define MaxSize 10
typedef struct {
int data[MaxSize];
int top1; // 栈1栈顶指针
int top2; // 栈2栈顶指针
} SharedStack;
// 初始化
void InitStack(SharedStack *s) {
s->top1 = -1; // 栈1为空
s->top2 = MaxSize; // 栈2为空
}初始状态下 top1 = -1，top2 = MaxSize，表示两个栈均为空。
交互可视化
通过下方的交互动画，你可以逐步观察共享栈的执行过程：
操作详解
入栈操作
入栈前必须先判断栈是否已满。根据操作的栈编号，分别移动对应的栈顶指针并写入元素。
c
// stackNum: 1 表示栈1，2 表示栈2
bool Push(SharedStack *s, int stackNum, int x) {
if (s->top1 + 1 == s->top2) // 栈满
return false;
if (stackNum == 1)
s->data[++s->top1] = x; // 栈1：指针右移后入栈
else
s->data[--s->top2] = x; // 栈2：指针左移后入栈
return true;
}关键步骤：
- 判断栈满条件
top1 + 1 == top2 - 栈 1 入栈：先
top1++，再赋值 - 栈 2 入栈：先
top2--，再赋值
出栈操作
出栈前先判断对应的栈是否为空，然后取出栈顶元素并移动指针。
c
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 判空：
top1 == -1 - 栈 2 判空：
top2 == MaxSize - 出栈方向与入栈方向相反
栈满判断
两个栈的栈顶指针相邻时，共享空间用尽：
c
bool IsFull(SharedStack *s) {
return s->top1 + 1 == s->top2;
}| 状态 | 条件 |
|---|---|
| 栈 1 空 | top1 == -1 |
| 栈 2 空 | top2 == MaxSize |
| 栈满（两栈共同满） | top1 + 1 == top2 |
注意：栈满不等于某一个栈满，而是两个栈的总元素数占满了整个数组。只要另一个栈还有空间让出来，就可以继续入栈。
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 入栈 | O(1) | 直接操作栈顶指针 |
| 出栈 | O(1) | 直接操作栈顶指针 |
| 判空 | O(1) | 比较栈顶指针与初始值 |
| 判满 | O(1) | 比较两个栈顶指针 |
空间复杂度：O(1)，所有操作只需常数级辅助空间。共享栈本身使用 O(MaxSize) 的数组空间，但相比两个独立栈，空间利用率更高。
考研高频考点
- ⭐ 栈满条件
top1 + 1 == top2（选择题/填空题高频） - ⭐ 栈空条件：栈 1 空
top1 == -1，栈 2 空top2 == MaxSize（易混淆） - ⭐ 共享栈的优点：提高空间利用率，适用于两个栈此消彼长的场景
- 入栈/出栈时指针的移动方向（栈 1 和栈 2 方向相反）
- 共享栈 vs 两个独立栈的空间利用率对比（简答题）