前言：
- 虽然顺序栈的存储已经十分方便，但是它有一个非常致命的缺陷：
即必须事先确定数组存储空间的大小，万一不够用就需要动态扩容 - 但对于两个相同类型的栈，我们可以做到最大限度的利用其事先开辟的存储空间，既让两栈共享空间
1.共享栈的定义
两个栈共享同一个存储空间，这片空间不单独属于任何一个栈，某个栈需要的多一点，它就可能得到更多的存储空间
2.共享栈的情况分析
注意：
- 这里所说的栈顶指针为int 下标模拟出来的指针功能
- 这里栈顶指针指向栈顶元素
2.1栈为空的情况：
top1等于-1: 一号栈为空栈
top2等于数组长度： 二号栈为空栈
2.3栈满的情况：
极端情况1：一号栈为空栈，二号栈为满栈;此时 top2=0，top1=-1
极端情况2：一号栈为满栈，二号栈为空栈;此时 top2=数组长度，top1=数组长度
最多出现的情况：
两个栈顶指针见面的时候：
而不管是极端情况还是最多出现的情况，都可以总结成一种情况：
即两个指针之差结果等于1这种情况
3.共享栈的相关核心操作
3.1共享栈的结构定义：
包括了一号栈 与 二号栈的栈顶指针，以及容纳两个栈中元素的数组
//1.共享栈的结构定义
typedef struct StackNode
{
SElemType data[MAXSIZE];
int top1;//栈1的栈顶指针(从数组的0开始)
int top2;//栈2的栈顶指针（从数组的n-1开始）
}DoubleStack;
//DoubleStack:用来定义栈的结构
3.2共享栈的入栈操作
注意：要传入栈的结构体指针，即&s，以及要入栈的元素，要入栈的栈号
Push(DoubleStack * s, SElemType e,int stacknumber)
3.2.1算法步骤：
（1判断两个栈是否栈满
（2）若给一号栈入栈，进行一号栈的入栈操作
<1>栈顶指针后移
<2>为当前栈顶空间赋值
两步可以合并为一步：s->data[++s->top1]; 先移动栈顶指针，再赋值
（3）若给二号栈入栈，进行二号栈的入栈操作
<1>栈顶指针前移
<2>为当前栈顶空间赋值
两步可以合并为一步：s->data[–s->top2]; 先移动栈顶指针，再赋值
- 一号栈的入栈图解：
2.先后移栈顶指针
3.再赋值
- 二号栈的入栈图解：
2.先前移栈顶指针
3.再赋值
//2.共享栈的入栈操作
//注意：要传入栈的结构体指针，即&s，以及要入栈的元素，要入栈的栈号
bool Push(DoubleStack * s, SElemType e,int stacknumber)
{
//[1]判断两个栈是否栈满
if (s->top1 + 1 == s->top2)
{
printf("栈满！\n");
return false;
}
//[2]若给一号栈入栈，进行一号栈的入栈操作
if(stacknumber == 1)
{
//<1>栈顶指针后移
s->top1++;
//<2>为当前栈顶空间赋值
s->data[s->top1] = e;
//两步可以合并为一步：
//s->data[++s->top1];先移动栈顶指针，再赋值
return true;
}
//[3]若给二号栈入栈，进行二号栈的入栈操作
else if (stacknumber == 2)
{
//<1>栈顶指针前移
s->top2--;
//<2>为当前栈顶空间赋值
s->data[s->top2] = e;
//两步可以合并为一步：
//s->data[--s->top2];先移动栈顶指针，再赋值
return true;
}
else
{
return false;//错误的栈编号！
}
}
3.3共享栈的出栈操作：
注意：要传入栈的结构体指针，即&s，以及接收栈顶元素的变量，要出栈的栈号
Pop(DoubleStack* s, SElemType* e, int stacknumber)
3.3.1算法步骤：
（1）若给一号栈出栈，进行一号栈的出栈操作
<1>若栈空，则返回false
<2>将当前栈顶元素赋值给e
<3>栈顶指针前移
2,3步可以合并为一步：*e = s->data[s->top1- -]; 先将栈顶元素出栈，再将栈顶指针前移
（2）若给二号栈出栈，进行二号栈的出栈操作
<1>若栈空，则返回false
<2>将当前栈顶元素赋值给e
<3>栈顶指针后移
2,3步可以合并为一步：*e = s->data[s->top1++]; 先将栈顶元素出栈，再将栈顶指针前移
(3) 若栈编号不正确，则返回false
- 一号栈的出栈图解：
2.先将当前栈顶元素赋值给e
3.再前移栈顶指针
- 二号栈的出栈图解：
2.先将当前栈顶元素赋值给e
3.再后移栈顶指针
//3.共享栈的出栈操作
bool Pop(DoubleStack* s, SElemType* e, int stacknumber)
{
//[1]若给一号栈出栈，进行一号栈的出栈操作
if (stacknumber == 1)
{
//<1>若栈空，则返回false
if (s->top1 == -1)
{
printf("栈空！\n");
return false;
}
//<2>将当前栈顶元素赋值给e
*e = s->data[s->top1];
//<3>栈顶指针前移
s->top1--;
//两步可以合并为一步：
//*e = s->data[s->top1--];先将栈顶元素出栈，再将栈顶指针前移
}
//[2]若给二号栈出栈，进行二号栈的出栈操作
else if (stacknumber == 2)
{
//<1>若栈空，则返回false
if (s->top2 == MAXSIZE)
{
printf("栈空！\n");
return false;
}
//<2>将当前栈顶元素赋值给e
*e = s->data[s->top2];
//<3>栈顶指针后移
s->top2++;
//两步可以合并为一步：
//*e = s->data[s->top1++];先将栈顶元素出栈，再将栈顶指针前移
}
else
{
return false;//错误的栈编号！
}
return true;
}
4.核心操作的整体实现
//共享栈
//为了最大限度的节省空间，让两个同类型的栈共享同一快存储空间
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100//两栈的最大容量
typedef int SElemType;//栈中元素的类型
#define bool int
#define true 1
#define false 0
//1.共享栈的结构定义
typedef struct StackNode
{
SElemType data[MAXSIZE];
int top1;//栈1的栈顶指针(从数组的0开始)
int top2;//栈2的栈顶指针（从数组的n-1开始）
}DoubleStack;
//DoubleStack:用来定义栈的结构
//共享栈的初始化操作
void InitStack(DoubleStack* s)
{
s->top1 = -1; // 初始化一号栈的栈顶指针
s->top2 = MAXSIZE; // 初始化二号栈的栈顶指针
}
//2.共享栈的入栈操作
//注意：要传入栈的结构体指针，即&s，以及要入栈的元素，要入栈的栈号
bool Push(DoubleStack * s, SElemType e,int stacknumber)
{
//[1]判断两个栈是否栈满
if (s->top1 + 1 == s->top2)
{
printf("栈满！\n");
return false;
}
//[2]若给一号栈入栈，进行一号栈的入栈操作
if(stacknumber == 1)
{
//<1>栈顶指针后移
s->top1++;
//<2>为当前栈顶空间赋值
s->data[s->top1] = e;
//两步可以合并为一步：
//s->data[++s->top1];先移动栈顶指针，再赋值
return true;
}
//[3]若给二号栈入栈，进行二号栈的入栈操作
else if (stacknumber == 2)
{
//<1>栈顶指针前移
s->top2--;
//<2>为当前栈顶空间赋值
s->data[s->top2] = e;
//两步可以合并为一步：
//s->data[--s->top2];先移动栈顶指针，再赋值
return true;
}
else
{
return false;//错误的栈编号！
}
}
//3.共享栈的出栈操作
bool Pop(DoubleStack* s, SElemType* e, int stacknumber)
{
//[1]若给一号栈出栈，进行一号栈的出栈操作
if (stacknumber == 1)
{
//<1>若栈空，则返回false
if (s->top1 == -1)
{
printf("栈空！\n");
return false;
}
//<2>将当前栈顶元素赋值给e
*e = s->data[s->top1];
//<2>栈顶指针前移
s->top1--;
//两步可以合并为一步：
//*e = s->data[s->top1--];先将栈顶元素出栈，再将栈顶指针前移
}
//[2]若给二号栈出栈，进行二号栈的出栈操作
else if (stacknumber == 2)
{
//<1>若栈空，则返回false
if (s->top2 == MAXSIZE)
{
printf("栈空！\n");
return false;
}
//<2>将当前栈顶元素赋值给e
*e = s->data[s->top2];
//<2>栈顶指针后移
s->top2++;
//两步可以合并为一步：
//*e = s->data[s->top1++];先将栈顶元素出栈，再将栈顶指针前移
}
else
{
return false;//错误的栈编号！
}
return true;
}
int main()
{
DoubleStack s1; // 声明一个共享栈
InitStack(&s1); // 初始化共享栈
// 测试用例
Push(&s1, 10, 1);
Push(&s1, 20, 2);
SElemType e;
Pop(&s1, &e, 1);
printf("栈1出栈元素：%d\n", e);
Pop(&s1, &e, 2);
printf("栈2出栈元素：%d\n", e);
return 0;
}
