导言
大家好，很高兴又和大家见面啦！！！
在上一篇内容中，我们介绍了如何通过C语言实现顺序栈，并且在介绍顺序栈的进栈操作时有提到过我们可以通过选择数组的首元素或者尾元素作为栈底，来进行栈的创建，以及栈的另一种形式——链栈。
根据前面的介绍，我们知道了顺序栈是通过静态数组进行实现的，既然是静态数组，那么它对应的空间大小就是不可被改变的。由于顺序栈的空间，当我们入栈的元素个数超过顺序栈的空间大小时，就会造成栈溢出的问题，我们为了避免出现栈溢出的情况，我们可以通过两种方式来进行栈的创建：
在今天的内容中我们将来详细介绍一下应该如何通过C语言来实现共享栈；
一、共享栈
为了解决栈溢出的问题，当我们选择通过申请一个足够大的空间时，势必就会造成内容空间的浪费，为了合理的解决这个问题，我们则可以根据栈在创建时的栈底选择不同，在同一个空间上创建两个栈，这个空间就被称为共享栈，如下图所示：
从图中可以看到在共享栈中，一个栈的栈底选择的是数组的首元素，一个栈的栈底选择的是数组的尾元素，它们对应的下标一个是0，一个是MaxSize-1。
1.1 共享栈的初始化
根据共享栈的结构，我们在初始化时，可以分别初始化为-1和MaxSize，也可以初始化为0和MaxSize-1，如下所示：
#define MaxSize 10
typedef struct SqStack {
int data[MaxSize];
int top_a;
int top_b;
}SqStack;
void InitStack(SqStack* S) {
assert(S);
S->top_a = -1;
S->top_b = MaxSize;
}
这里为了方便演示，我是定义的一个整型共享栈，站内能存储的是整型数据类型的数据元素。在初始化阶段，我这里是将其初始化为-1和MaxSize，当然也可以初始化为0和MaxSize-1，这里我就不演示了，大家可以自行下去尝试一下。
1.2 共享栈的判空
完成初始化后，我们要对其进行判空操作的话则是同时判断两个栈顶指针的值，如下所示：
bool EmptyStack(SqStack S) {
if (S.top_a == -1 && S.top_b == MaxSize)
return true;
return false;
}
在初始化阶段我们是通过assert来进行问题反馈，因此可以对函数的返回类型设置为void，在进行判空操作时，我们是通过函数的返回值来进行判断，所以这里通过分支语句来对不同的返回值做出对应的提示；
1.3 共享栈的入栈
当我要对共享栈进行入栈操作时，可以有多种实现方式：
- 对两个栈同时进行入栈操作；
- 对两个栈依次进行入栈操作；
这里我给大家演示一下对两个栈依次进行入栈操作应该如何实现，如下所示：
int Push(SqStack* S, int x, char flag) {
if (!S)
return 3;
if(S->top_a + 1 == S->top_b)
return 0;
if (flag == 'a') {
S->data[++S->top_a] = x;
}
else if (flag == 'b') {
S->data[--S->top_b] = x;
}
else
return 2;
return 1;
}
为了更加直观的收到函数的反馈，这里我们可以通过将函数的返回值以0,1,2,3这三个值来进行反馈，主函数中通过分支语句来判断返回值，以此给出不同的反馈，下面我们就来介绍一下这些返回值的作用；
1.3.1 空指针
1.3.2 满栈
相比于单个的顺序栈，共享栈在进行入栈前对满栈的判断则是两个栈顶元素相邻，如下所示：
1.3.3 入栈空间错误
为了能更加精准的将元素存入对应的栈空间内，这里我们是通过一个标志变量来执行，当标志为’a’时，说明我们此时要存入的是栈a，当标志为’b’时，说明我们此时要存入的是栈b，但是当标志为其它内容时，我们需要给用户提示，说明输入空间有误，如下所示：
1.3.4 正常入栈
当我们传参正确、栈未满且空间都正确时，此时函数返回值为1，这样我们可以一直进行输入，知道满栈为止，如下所示：
1.3.5 小结
对于共享栈的入栈操作我们就介绍完了，通过这里演示的代码我们可以看到，此时咱们算法是有很强的健壮性的，可以根据不同的问题给出不同的反馈。
当然，在实际操作中肯定不会像我这样去进行编写代码，我们需要根据具体的情况来对代码进行相应的调整，这里我们只要保证操作的逻辑没有发生改变就行。
1.4 共享栈的查找
对于共享栈而言，我们要查找栈顶指针的话也是需要指明查找的对象，因此，我们可以依然可以通过标志变量进行指定，如下所示：
int GetTop(SqStack S, char flag,int* x) {
assert(x);
if (flag == 'a') {
if (S.top_a != -1)
*x = S.data[S.top_a];
return S.top_a;
}
else if (flag == 'b') {
if (S.top_b != MaxSize)
*x = S.data[S.top_b];
return S.top_b;
}
else
return MaxSize + 1;
}
由于查找栈顶后，我们还需要将栈顶元素带回到主函数中，因此存储数据的变量我们选择的是通过传址的方式进行传参，并通过指针接收，这里我们可以直接通过assert断言来对指针x进行判空操作；
相比于正常的顺序栈而言，共享栈在进行栈顶查找时，我们通过标志变量来判断查找的对象，并通过判断查找对象的栈顶指针的位置来决定是否将该位置存储的值带回；
对应的主函数中，我们则可以根据函数对应的返回值来给出对应的反馈，如下所示：
printf("请输入要查询的栈空间<a/b>:>");
scanf("%c", &flag);
int top = GetTop(S, flag, &x);
switch (top) {
case -1:
printf("栈%c为空栈\n", flag);
break;
case MaxSize:
printf("栈%c为空栈\n", flag);
break;
case MaxSize + 1:
printf("共享栈中没有栈%c\n", flag);
break;
default:
printf("栈%c的栈顶为%d，栈顶元素为%d\n", flag, top, x);
break;
}
在共享栈中栈a的栈顶指针的取值范围是-1～MaxSize-1，栈b的栈顶指针的取值范围是MaxSize～0，因此返回值为-1与返回值为MaxSize以及返回值为MaxSize+1这三种情况都是唯一的，所以我们在switch语句中只需要将这三者单独罗列出来即可，对其它的情况我们只需要正常打印就行；
1.5 共享栈的出栈
共享栈的出栈操作与入栈操作同理，都是需要根据指定出栈对象来完成出栈操作，因此，我们在出栈操作中同样需要增设一个标志变量来制定出栈的对象，如下所示：
int Pop(SqStack* S, char flag, int* x) {
assert(S && x);
if (flag == 'a') {
if (S->top_a != -1)
*x = S->data[S->top_a--];
return S->top_a;
}
else if (flag == 'b') {
if (S->top_b != MaxSize)
*x = S->data[S->top_b++];
return S->top_b;
}
else
return MaxSize + 1;
}
这里我是通过仿照查找栈顶指针的操作编写的代码，根据函数的返回值，我们在主函数中就可以编写以下代码：
printf("请输入需要出栈的栈空间<a/b>:>");
scanf("%c", &flag);
top = Pop(&S, flag, &x);
switch (top) {
case -1:
printf("栈%c为空栈\n", flag);
break;
case MaxSize:
printf("栈%c为空栈\n", flag);
break;
case MaxSize + 1:
printf("共享栈中没有栈%c\n", flag);
break;
default:
printf("栈%c的已完成栈顶元素%d的出栈，此时的栈顶为%d\n", flag, x, top);
break;
}
可以看到，此时我们只是对代码进行了一些小改动，反馈逻辑与栈顶指针的查找的反馈逻辑是一致的；
1.6 共享栈的销毁
共享栈的销毁我们则是通过在出栈的基础上加上一个循环，将所有的元素全部进行出栈即可，对应的代码如下所示：
int des = 2;
while (des) {
printf("请输入需要出栈的栈空间<a/b>:>");
scanf("%c", &flag);
top = Pop(&S, flag, &x);
switch (top) {
case -1:
printf("栈%c为空栈\n", flag);
des--;
break;
case MaxSize:
printf("栈%c为空栈\n", flag);
des--;
break;
case MaxSize + 1:
printf("共享栈中没有栈%c\n", flag);
break;
default:
printf("栈%c的已完成栈顶元素%d的出栈，此时的栈顶为%d\n", flag, x, top);
break;
}
getchar();
}
printf("共享栈S已完成销毁\n");
我这里的代码执行的销毁是手动进行元素的出栈，有兴趣的朋友也可以将其改为自动进行销毁操作。
从循环的判断条件我们可以看到，此时除非两个栈都为空栈时，循环才会停止否则就会一直运行；在完成所有的元素弹出后，栈的空间回收我们只需要等待程序运行结束后自动回收即可。
二、共享栈的实现演示
为了节约时间，这里我将最大的元素个数修改为4，下面我们在来看一下具体的操作演示：
#define MaxSize 4
typedef struct SqStack {
int data[MaxSize];
int top_a;
int top_b;
}SqStack;
void InitStack(SqStack* S) {
assert(S);
S->top_a = -1;
S->top_b = MaxSize;
}
bool EmptyStack(SqStack S) {
if (S.top_a == -1 && S.top_b == MaxSize)
return true;
return false;
}
int Push(SqStack* S, int x, char flag) {
if (!S)
return 3;
if(S->top_a + 1 == S->top_b)
return 0;
if (flag == 'a') {
S->data[++S->top_a] = x;
}
else if (flag == 'b') {
S->data[--S->top_b] = x;
}
else
return 2;
return 1;
}
int GetTop(SqStack S, char flag,int* x) {
assert(x);
if (flag == 'a') {
if (S.top_a != -1)
*x = S.data[S.top_a];
return S.top_a;
}
else if (flag == 'b') {
if (S.top_b != MaxSize)
*x = S.data[S.top_b];
return S.top_b;
}
else
return MaxSize + 1;
}
int Pop(SqStack* S, char flag, int* x) {
assert(S && x);
if (flag == 'a') {
if (S->top_a != -1)
*x = S->data[S->top_a--];
return S->top_a;
}
else if (flag == 'b') {
if (S->top_b != MaxSize)
*x = S->data[S->top_b++];
return S->top_b;
}
else
return MaxSize + 1;
}
int main() {
SqStack S;
InitStack(&S);
if (EmptyStack(S))
printf("共享栈为空栈\n");
else
printf("共享栈内有存入元素\n");
char flag = 0;
int x = 0;
int ret = 1;
while (ret == 1 || ret == 2) {
printf("请输入进行入栈的空间:>");
scanf("%c", &flag);
printf("请输入进行入栈的数据:>");
scanf("%d", &x);
ret = Push(&S, x, flag);
switch (ret)
{
case 0:
printf("共享栈已满栈\n");
break;
case 1:
break;
case 2:
printf("入栈的空间输入错误，请重新输入<a/b>\n");
break;
default:
printf("指针S为空指针\n");
break;
}
getchar();
}
printf("请输入要查询的栈空间<a/b>:>");
scanf("%c", &flag);
int top = GetTop(S, flag, &x);
switch (top) {
case -1:
printf("栈%c为空栈\n", flag);
break;
case MaxSize:
printf("栈%c为空栈\n", flag);
break;
case MaxSize + 1:
printf("共享栈中没有栈%c\n", flag);
break;
default:
printf("栈%c的栈顶为%d，栈顶元素为%d\n", flag, top, x);
break;
}
getchar();
int des = 2;
while (des) {
printf("请输入需要出栈的栈空间<a/b>:>");
scanf("%c", &flag);
top = Pop(&S, flag, &x);
switch (top) {
case -1:
printf("栈%c为空栈\n", flag);
des--;
break;
case MaxSize:
printf("栈%c为空栈\n", flag);
des--;
break;
case MaxSize + 1:
printf("共享栈中没有栈%c\n", flag);
break;
default:
printf("栈%c的已完成栈顶元素%d的出栈，此时的栈顶为%d\n", flag, x, top);
break;
}
getchar();
}
printf("共享栈S已完成销毁\n");
return 0;
}
结语
咱们今天的内容到这里就全部介绍完了，希望今天的内容能够帮助大家更好的理解共享栈以及对应的操作如何通过C语言来实现，在下一个篇章中，我将继续给大家介绍链栈的相关内容，大家记得关注哦！！！
最后感谢大家的翻阅，咱们下一篇再见！！！