当前位置：首页 > backend >正文

双栈共享一个栈空间

backend 2025/6/29 4:10:50

一、核心思想：“一个数组，两个栈”

想象一下：

你有一个数组 V（长度为 m），但想同时用它实现两个栈（栈 0 和栈 1）。
栈 0 从数组 ** 左边（下标 0）** 开始往右 “生长”（入栈时栈顶下标增大）。
栈 1 从数组 ** 右边（下标 m-1）** 开始往左 “生长”（入栈时栈顶下标减小）。
两个栈 “相向而行”，直到碰到一起（栈 0 顶和栈 1 顶相邻），就说明栈满了。

这样做的好处是节省空间：两个栈共享同一块数组，不用给每个栈单独开空间，适合不确定哪个栈用更多空间的场景。

二、关键变量定义

V：数组，存两个栈的数据。
b[0]：栈 0 的底部下标（固定为 0）。
b[1]：栈 1 的底部下标（固定为 m-1）。
t[0]：栈 0 的栈顶下标（初始和 b[0] 一样，入栈时增大）。
t[1]：栈 1 的栈顶下标（初始和 b[1] 一样，入栈时减小）。

三、操作实现（C 语言代码）

下面用代码一步步实现 “初始化、判空、判满、入栈、出栈”，每一步都有详细解释。

1. 定义结构体（管理双栈）

#define MAXSIZE 100  // 数组最大长度（双栈共享）// 双栈结构体
typedef struct {int V[MAXSIZE];  // 共享的数组int b[2];        // 两个栈的底部下标（b[0]=0，b[1]=MAXSIZE-1）int t[2];        // 两个栈的栈顶下标（t[0]初始=0，t[1]初始=MAXSIZE-1）
} DoubleStack;

2. 初始化双栈

初始化时，让：

栈 0 的底部 b[0] = 0，栈顶 t[0] = 0（表示栈 0 为空，还没元素）。
栈 1 的底部 b[1] = MAXSIZE-1，栈顶 t[1] = MAXSIZE-1（表示栈 1 为空）。

代码：

// 初始化双栈
void InitDoubleStack(DoubleStack *ds) {// 栈 0：底部在 0，栈顶初始也在 0（空栈）ds->b[0] = 0;ds->t[0] = 0;// 栈 1：底部在 MAXSIZE-1，栈顶初始也在 MAXSIZE-1（空栈）ds->b[1] = MAXSIZE - 1;ds->t[1] = MAXSIZE - 1;
}

3. 判断栈空

栈空的条件：

栈 0 空：t[0] == b[0]（栈顶下标等于底部下标，说明没元素）。
栈 1 空：t[1] == b[1]（同理）。

代码：

// 判断栈是否为空（stackIndex：0 表示栈 0，1 表示栈 1）
int IsEmpty(DoubleStack *ds, int stackIndex) {if (stackIndex == 0) {// 栈 0 空：栈顶 == 栈底return ds->t[0] == ds->b[0];} else {// 栈 1 空：栈顶 == 栈底return ds->t[1] == ds->b[1];}
}

4. 判断栈满

栈满的条件：两个栈顶 “碰到一起”，即 t[0] + 1 == t[1]（栈 0 顶的下一个位置就是栈 1 顶的位置）。

代码：

// 判断栈是否已满
int IsFull(DoubleStack *ds) {// 栈 0 顶 +1 == 栈 1 顶 → 满了return ds->t[0] + 1 == ds->t[1];
}

5. 进栈（入栈）

逻辑：

选一个栈（0 或 1），检查是否满。
没满的话，把元素放到栈顶位置，然后更新栈顶下标。

代码：

// 进栈操作（stackIndex：0 或 1；value：要入栈的值）
int Push(DoubleStack *ds, int stackIndex, int value) {// 先判断是否栈满if (IsFull(ds)) {printf("栈满了，无法入栈！\n");return 0;  // 入栈失败}if (stackIndex == 0) {// 栈 0 入栈：把值放到 t[0] 位置，然后 t[0]++ds->V[ds->t[0]] = value;ds->t[0]++;} else {// 栈 1 入栈：把值放到 t[1] 位置，然后 t[1]--ds->V[ds->t[1]] = value;ds->t[1]--;}return 1;  // 入栈成功
}

6. 出栈

逻辑：

选一个栈，检查是否空。
没空的话，把栈顶元素 “取出来”，然后更新栈顶下标。

代码：

// 出栈操作（stackIndex：0 或 1；value：用来存出栈的值）
int Pop(DoubleStack *ds, int stackIndex, int *value) {// 先判断是否栈空if (IsEmpty(ds, stackIndex)) {printf("栈空了，无法出栈！\n");return 0;  // 出栈失败}if (stackIndex == 0) {// 栈 0 出栈：t[0]--，然后取值ds->t[0]--;*value = ds->V[ds->t[0]];} else {// 栈 1 出栈：t[1]++，然后取值ds->t[1]++;*value = ds->V[ds->t[1]];}return 1;  // 出栈成功
}

四、完整示例（测试代码）

把这些函数拼起来，测试一下：

#include <stdio.h>#define MAXSIZE 100typedef struct {int V[MAXSIZE];int b[2];int t[2];
} DoubleStack;// 初始化双栈
void InitDoubleStack(DoubleStack *ds) {ds->b[0] = 0;ds->t[0] = 0;ds->b[1] = MAXSIZE - 1;ds->t[1] = MAXSIZE - 1;
}// 判断栈空
int IsEmpty(DoubleStack *ds, int stackIndex) {if (stackIndex == 0) {return ds->t[0] == ds->b[0];} else {return ds->t[1] == ds->b[1];}
}// 判断栈满
int IsFull(DoubleStack *ds) {return ds->t[0] + 1 == ds->t[1];
}// 进栈
int Push(DoubleStack *ds, int stackIndex, int value) {if (IsFull(ds)) {printf("栈满了，无法入栈！\n");return 0;}if (stackIndex == 0) {ds->V[ds->t[0]] = value;ds->t[0]++;} else {ds->V[ds->t[1]] = value;ds->t[1]--;}return 1;
}// 出栈
int Pop(DoubleStack *ds, int stackIndex, int *value) {if (IsEmpty(ds, stackIndex)) {printf("栈空了，无法出栈！\n");return 0;}if (stackIndex == 0) {ds->t[0]--;*value = ds->V[ds->t[0]];} else {ds->t[1]++;*value = ds->V[ds->t[1]];}return 1;
}// 测试主函数
int main() {DoubleStack ds;int value;// 初始化双栈InitDoubleStack(&ds);// 栈 0 入栈：10、20、30Push(&ds, 0, 10);Push(&ds, 0, 20);Push(&ds, 0, 30);// 栈 1 入栈：100、200、300Push(&ds, 1, 100);Push(&ds, 1, 200);Push(&ds, 1, 300);// 栈 0 出栈Pop(&ds, 0, &value);printf("栈 0 出栈：%d\n", value);  // 输出 30// 栈 1 出栈Pop(&ds, 1, &value);printf("栈 1 出栈：%d\n", value);  // 输出 300return 0;
}

五、运行流程演示

初始化：
- 栈 0：b[0]=0，t[0]=0（空）。
- 栈 1：b[1]=99（假设 MAXSIZE=100），t[1]=99（空）。
栈 0 入栈 10、20、30：
- 入栈 10 → V[0]=10，t[0]=1。
- 入栈 20 → V[1]=20，t[0]=2。
- 入栈 30 → V[2]=30，t[0]=3。
栈 1 入栈 100、200、300：
- 入栈 100 → V[99]=100，t[1]=98。
- 入栈 200 → V[98]=200，t[1]=97。
- 入栈 300 → V[97]=300，t[1]=96。
栈 0 出栈：
- t[0]-- → t[0]=2，取 V[2]=30。
栈 1 出栈：
- t[1]++ → t[1]=97，取 V[97]=300。