共享栈
共享栈：两个栈共享同一片存储空间，这片存储空间不单独属于任何一个栈，某个栈需要的多一点，它就可能得到更多的存储空间；
两个栈的栈底在这片存储空间的两端，当元素入栈时，两个栈的栈顶指针相向而行。
基本概念
栈是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。栈顶的当前位置是动态的，对栈顶当前位置的标记称为栈顶指针。当栈中没有数据元素时，称之为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。栈是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。栈顶的当前位置是动态的，对栈顶当前位置的标记称为栈顶指针。当栈中没有数据元素时，称之为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。
共享栈示意图
第一个栈从数组头开始存储，第二个栈从数组尾开始，两个栈向中间拓展。
当top1+1 == top2或者top1 == top2-1时，即staock overflow!.
与普通栈一样，共享栈出栈入栈的时间复杂度仍为O(1).
实验报告
当一个应用程序中需要使用多少个栈时，为了提高空间的使用效率，要让多个栈共享空间，这样既能减少预分配的空间过多造成的浪费，又能降低发生栈上溢产生错误中断的可能性，如上图所示，仅当两个栈相遇才会发生上溢
一、问题描述（标题黑体小四）
实现共享栈
二、实验目的
实现共享栈
三、实验设计
1.逻辑结构
逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构；集合、树和图是典型的非线性结构。数据的逻辑结构分类见图1-1。
- 集合结构中的数据元素之间除了 “同属于一个集合”的关系外，别无其他关系。
- 线性结构结构中的数据元素之间只存在一对一的关系。
- 树形结构结构中的数据元素之间存在一对多的关系。
- 图状结构或网状结构结构中的数据元素之间存在多对多的关系。
栈是特殊的线性表，它的逻辑结构和线性表相同，只是起操作规则受到了限制，因此，又称它是操作受限的线性表。共享栈也是栈，故逻辑结构为线性结构。
2.存储结构
存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。
- 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里，元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
- 链接存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针表示元素之间的逻辑关系。其优点是不会出现碎片现象，充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，并且只能实现顺序存取。
- 索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址）。其优点是检索速度快；缺点是增加了附加的索引表，会占用较多的存储空间。另外，在增加和删除数据时要修改索引表，因而会花费较多的时间。
- 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称为Hash存储。其优点是检索、增加和删除结点的操作都很快；缺点是如果散列函数不好可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。
可以采用顺序表，也可以采用链式表。本次实验用顺序表实现。故本次为顺序存储。
/---变量的定义---/
typedef int Selemtype;
#define Maxsize 100 //定义共享栈中元素的最大个数
#define TURE 1;
#define FALSE 0;
/---栈的顺序存储结构---/
typedef struct
{
Selemtype data[Maxsize]; //栈的大小
int top1; //第一个栈的栈顶
int top2; //第二个栈的栈顶
}ShareStack;
3.算法设计思想
两个栈共享一个存储空间，top1栈在指向空间的左端，依次向右入栈同时top1++，top2栈在指定空间的右端，依次向左入栈同时top2--，
栈满，既
S1入栈：指针右移一个位置，即stack[++top[0]]=x;
S2入栈：指针左移一个位置，即stack[--top[0]]=x;
当top1-1 = top2时 栈满
4.输入、输出设计
输入：入栈（数字+栈序）
结束入栈操作（F）
输出：出栈（栈内存储变量值）
四、主要代码
/---初始化---/
int InitStack(ShareStack *s)
{
s->top1 = 0;
s->top2 = Maxsize-1;
return TURE;
}
/---判断共享栈是否为空---/
int IsEmpty(ShareStack *s)
{
if(s->top1==0 && s->top2==Maxsize-1)
{
return TURE;
}
return FALSE;
}
/---入栈操作---/
int pushSStack(ShareStack *s,Selemtype x,int stackNum)
{
if(s->top1 == s->top2+1)
{
return FALSE;
}
switch(stackNum)
{
case 1:s->data[s->top1++] = x;break;
case 2:s->data[s->top2--] = x;break;
}
return TURE;
}
/---出栈操作---/
int PopSStack(ShareStack *s,Selemtype *x,int stackNum)
{
switch(stackNum)
{
case 1:
{
if(s->top1 == 0) return FALSE;
*x = s->data[--s->top1];
};break;
case 2:
{
if(s->top2==Maxsize-1) return FALSE;
*x = s->data[++s->top2];
};break;
}
return TURE;
}
五、程序运行结果截图
六、遇到的问题和解决方法
问题：栈空输出临界重复输出数值
解决方法：利用if语句进行先判断后打印操作
完整代码
点击查看代码
#include <stdio.h>
#include <stdlib.h>
#include "SStack.h" //自定义头文件 内部有共享栈的定义初始化 出入栈 判断栈空等函数
int main(){
ShareStack *s;
s = (ShareStack *)malloc(sizeof(ShareStack));
InitStack(s);
int n;
int SStackNum;
char c;
/*---判断栈空---*/
if(IsEmpty(s))
printf("栈空
");
else
printf("栈不空
");
printf("入栈
");
while(!(c = getchar() == 'F') )
{
printf("输入入栈数字和栈序（末尾加F：退出）：");
scanf("%d %d",&n,&SStackNum);
pushSStack(s,n,SStackNum);
}
printf("出栈
");
while(!(c = getchar() == 'F') )
{
printf("输入出栈序（末尾加F：退出）：");
scanf("%d",&SStackNum);
if(PopSStack(s,&n,SStackNum))
printf("%d
",n);
else
break;
}
/*---判断栈空---*/
if(IsEmpty(s))
printf("栈空");
else
printf("栈不空");
}