栈：限定只能在表尾进行插入和删除的线性表。
两栈共享空间结构：使用数组同时实现两个栈，即栈1和栈2；栈1为空时，栈1的栈顶指针指向-1；栈2为空时，栈2 的栈顶指针指向MAXSIZE；栈1和栈2添加元素时，都会向数据中间靠拢，当栈1的指针+1等于栈2的指针的时候，栈满。
两栈共享空间结构特性：
- 在一个数据中同时存在两个栈，栈顶指针分别为top1、top2。
- 只能分别在对应的栈顶插入和删除元素。
- 后进先出（Last In First Out）的线性表，后进入的元素先出栈，剩下的元素才能出栈。
优点：
- 具有记忆功能，可用于表达式求值等操作。
- 添加和删除元素不需要移动大量元素，只需要移动栈顶指针。
- 可有效利用剩下的栈空间。
缺点：
- 只适用于类型相同的两个栈。
- 两个栈是此消彼长的关系，导致两个栈分别的栈长是动态变化的，无法确定。
时间复杂度
- 读取时的时间复杂度为O(1)。
- 插入、删除时的时间复杂度为O(1)。
空栈示意图
栈1插入元素示意图
栈2插入元素示意图
栈1删除元素示意图
栈2删除元素示意图
实现代码如下：
// 两栈共享空间
#include <stdio.h>
#include <malloc.h>
#include <time.h>
#define OK 1 // 执行成功
#define ERROR 0 // 执行失败
#define TRUE 1 // 返回值为真
#define FALSE 0 // 返回值为假
#define MAXSIZE 20 // 存储空间初始分配大小
typedef int Status; // 函数返回结果类型
typedef int ElemType; // 元素类型
// 两栈共享结构
typedef struct {
ElemType data[MAXSIZE]; // 用于存储元素值
int top1; // 用于指示栈1的栈顶指针
int top2; // 用于指示栈2的栈顶指针
}SqStack;
/**
* 初始化栈
* @param S 栈
* @return 执行状态
*/
Status InitStack(SqStack *S) {
S->top1 = -1; // 栈1的栈顶指针指向-1，此时栈1为空
S->top2 = MAXSIZE; // 栈2的栈顶指针指向MAXSIZE，此时栈2为空
return OK;
}
/**
* 清空栈中元素
* @param S 栈
* @return 执行状态
*/
Status ClearStack(SqStack *S) {
S->top1 = -1; // 栈1的栈顶指针指向-1，此时栈1为空
S->top2 = MAXSIZE; // 栈2的栈顶指针指向MAXSIZE，此时栈2为空
return OK;
}
/**
* 判断栈是否为空
* @param S 栈
* @return 执行状态
*/
Status StackEmpty(SqStack *S) {
// 栈1和栈2都为空时，栈才为空
if (S->top1 == -1 && S->top2 == MAXSIZE) {
return TRUE;
} else {
return FALSE;
}
}
/**
* 获取栈中元素个数（栈1和栈2的元素总数）
* @param S 栈
* @return 执行状态
*/
int StackLength(SqStack *S) {
return (S->top1 + 1) + (MAXSIZE - S->top2);
}
/**
* 获取栈顶元素的值，存到元素e中
* @param S 栈
* @param e 用于存储栈顶元素的值
* @param stackNumber 栈号
* @return 执行状态
*/
Status GetTop(SqStack *S, ElemType *e, int stackNumber) {
// 获取栈1的栈顶元素值
if (stackNumber == 1) {
// 栈1为空时，获取栈顶元素失败
if (S->top1 == -1) {
return ERROR;
}
// 将栈1的栈顶元素的值赋值给e元素
*e = S->data[S->top1];
} else { // 获取栈2的栈顶元素值
// 栈2为空，获取栈顶元素失败
if (S->top2 == MAXSIZE) {
return ERROR;
}
// 将栈2的栈顶元素的值赋值给e元素
*e = S->data[S->top2];
}
return OK;
}
/**
* 添加新元素e到栈顶
* @param S 栈
* @param e 新元素
* @param stackNumber 栈号
* @return 执行状态
*/
Status Push(SqStack *S, ElemType e, int stackNumber) {
// 栈满时，添加失败
if (S->top1 + 1 == S->top2) {
return ERROR;
}
// 给栈1添加新元素
if (stackNumber == 1) {
S->data[++S->top1] = e; // 将新元素添加到栈1的栈顶
} else { // 给栈2添加新元素
S->data[--S->top2] = e; // 将新元素添加到栈2的栈顶
}
return OK;
}
/**
* 弹出栈顶元素
* @param S 栈
* @param e 弹出元素
* @param stackNumber 栈号
* @return 执行状态
*/
Status Pop(SqStack *S, ElemType *e, int stackNumber) {
// 栈1弹出元素
if (stackNumber == 1) {
// 栈为空时，弹出元素失败
if (S->top1 == -1) {
return ERROR;
}
*e = S->data[S->top1--]; // 将栈顶元素的值赋给e元素，栈1的栈顶指针减1
} else { // 栈2弹出元素
if (S->top2 == MAXSIZE) {
return ERROR;
}
*e = S->data[S->top2++]; // 将栈顶元素的值赋给e元素，栈2的栈顶指针加1
}
return OK;
}
/**
* 打印单个元素的值
* @param e 元素
* @return 执行状态
*/
Status visit(ElemType e) {
printf("%d ", e);
return OK;
}
/**
* 从栈底开始遍历栈中元素
* @param S 栈
* @return 执行状态
*/
Status StackTraverse(SqStack S) {
int i = 0; // 指示器，用于指示栈顶指针的位置
printf("栈1中的元素为：[ ");
// 指示器位置小于栈1的栈顶指针
while (i <= S.top1) {
visit(S.data[i++]); // 打印i位置元素，i向下一个元素移动
}
printf("]\n");
i = MAXSIZE - 1;
printf("栈2中的元素为：[ ");
while (i >= S.top2) {
visit(S.data[i--]);
}
printf("]\n");
return OK;
}
int main() {
int j; // 用于遍历
SqStack s; // 栈
ElemType e; // 元素
// 如果初始化成功
if (InitStack(&s) == OK) {
// 向栈1中插入5个元素
for (j = 1; j <= 5; j++) {
Push(&s, j, 1); // 向栈1的栈顶插入元素j
}
// 向栈2中插入5个元素
for (j = MAXSIZE; j > MAXSIZE - 5; j--) {
Push(&s, j, 2); // 向栈2的栈顶插入元素j
}
}
printf("栈中的元素如下：\n");
StackTraverse(s); // 遍历栈中元素
Pop(&s, &e, 1); // 弹出栈1的栈顶元素
printf("弹出的栈顶元素为：e = %d\n", e);
printf("弹出一个元素之后，栈是否为空：%s\n", StackEmpty(&s) == TRUE ? "是" : "否");
GetTop(&s, &e, 1); // 获取栈1的栈顶元素的值
printf("栈1的栈顶元素的值为：e = %d\n", e);
GetTop(&s, &e, 2); // 获取栈1的栈顶元素的值
printf("栈2的栈顶元素的值为：e = %d\n", e);
printf("栈的长度为：%d\n", StackLength(&s)); // 获取栈的长度
ClearStack(&s); // 清空栈中元素
printf("清空栈后，栈是否为空：%s\n", StackEmpty(&s) == TRUE ? "是" : "否");
return 0;
}
运行结果
