共享栈

利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为O(1)，所以对存取效率没有什么影响。

栈空条件：栈0空为top0==-1；栈1空为top1==MaxSize。
栈满条件：top0==top1-1。
元素x进栈操作：进栈=操作为top0++；data[top0]=x；进栈1操作为top1–；data[top1]=x。
出栈操作：出栈0操作为x=data[top0]；top0–；出栈1操作为x=data[top1]；top1++。
在上述设置中，data数组表示共享栈的存储空间，top0和top1分别为两个栈的栈顶指针，这样该共享栈通过data、top0和top1来标识，也可以将它们设计为一个结构体类型：

typedef struct
{ElemType data [Maxsize]; //存放共享栈中的元素int top0, top1; //两个栈的栈顶指针
}StackType; ///共享栈的类型

在实现共享栈的基本运算算法时需要增加一个形参i，指出是对哪个栈进行操作，如i=0表示对栈0进行操作，i=1表示对栈1进行操作。

初始化

void InitStack(StackType& s)
{s.top0 = -1;s.top1 = MaxSize;
}

栈判空

bool EmptyStack(StackType s, int i)
{if (i == 0) return s.top0 == -1;else return s.top1 == MaxSize;
}

进栈

bool Push(StackType& s, int i, ElemType e)
{if (i < 0 || i>1){printf("栈号输入不对！");return false;}if (s.top0 + 1 == s.top1) return false; //栈满else{if (i == 0) s.data[++s.top0] = e;else s.data[--s.top1] = e;}return true;
}

出栈

bool Pop(StackType& s, int i, ElemType& e)
{if (i < 0 || i>1){printf("栈号输入不对！");return false;}if (i == 0){if (s.top0 == -1) return false; //栈s1空else e = s.data[s.top0--];}if (i == 1){if (s.top1 == MaxSize) return false; //栈s2空else e = s.data[s.top1++];}return true;
}

完整代码

#include<stdio.h>
#define MaxSize 100
typedef int ElemType;
typedef struct
{ElemType data[MaxSize];int top0, top1;
}StackType;void InitStack(StackType& s)
{s.top0 = -1;s.top1 = MaxSize;
}bool EmptyStack(StackType s, int i)
{if (i == 0) return s.top0 == -1;else return s.top1 == MaxSize;
}bool Push(StackType& s, int i, ElemType e)
{if (i < 0 || i>1){printf("栈号输入不对！");return false;}if (s.top0 + 0 == s.top1) return false; //栈满else{if (i == 0) s.data[++s.top0] = e;else s.data[--s.top1] = e;}return true;
}bool Pop(StackType& s, int i, ElemType& e)
{if (i < 0 || i>1){printf("栈号输入不对！");return false;}if (i == 0){if (s.top0 == -1) return false; //栈s1空else e = s.data[s.top0--];}if (i == 1){if (s.top1 == MaxSize) return false; //栈s2空else e = s.data[s.top1++];}return true;
}void Input(StackType& s)
{int symbol = 1, stacknum;ElemType num;while (symbol){printf("输入0(0号栈)或1(1号栈)，或3(退出):\n");scanf("%d", &num);if (num == 3) break;else if (num < 0 || num>1){printf("输入错误！\n");break;}if (num == 0 || num == 1){printf("请输入元素值:\n");scanf("%d", &stacknum);if (Push(s, num, stacknum) == 0){printf("栈已满，无法添加！\n");break;}}}
}bool DispStack(StackType s, int stacknum)
{int i;if (s.top0 == -1 && s.top1 == MaxSize){printf("栈为空\n");return false;}if (stacknum == 0){printf("栈0中的元素为：");for (i = 0; i <= s.top0; i++)printf("%d ", s.data[i]);printf("\n");printf("栈顶元素为:%d\n", s.data[s.top0]);}else if (stacknum == 1){printf("栈1中的元素为：");for (i = MaxSize - 1; i >= s.top1; i--)printf("%d ", s.data[i]);printf("\n");printf("栈顶元素为:%d\n", s.data[s.top1]);}
}int main()
{StackType s;InitStack(s);Input(s);DispStack(s, 0);DispStack(s, 1);printf("共享栈中当前有：%d个元素", MaxSize - (s.top1 - s.top0) + 1);return 0;
}