一文搞懂共享栈zag666的博客-

共享栈的概念

共享栈：两个栈共享同一片存储空间，这片存储空间不单独属于任何一个栈，某个栈需要的多一点，它就可能得到更多的存储空间；
两个栈的栈底在这片存储空间的两端，当元素入栈时，两个栈的栈顶指针相向而行。

忘记栈的概念的朋友可以回顾一下：

栈是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。栈顶的当前位置是动态的，对栈顶当前位置的标记称为栈顶指针。当栈中没有数据元素时，称之为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。

共享栈的实现

• 这里为什么用int top[2]={-1,maxsize};而不用int top1=-1,top2=maxSize;呢？

为了体现这两个栈底指针是属于一个共享栈的，我们习惯于用一个长度为2的数组表示它们，这样显得代码的可读性更强一点。

• 什么时候为栈空状态呢？

• 共享栈怎么入栈呢？

S1入栈：指针右移一个位置，即stack[++top[0]]=x;
S2入栈：指针左移一个位置，即stack[--top[0]]=x;

• 什么时候栈满呢？
  两个栈顶指针重合时，表示共享栈已经满了
  

用两个栈模拟队列

注意栈和队列的本质区别：栈先进后出，队列先进先出。因此务必要注意下图的规则：

注意：如果要把栈S1的元素导入到栈S2，必须一次性全部导入，不然就会出错。

基本操作我们分为：初始化栈、入栈、出栈、取栈顶元素，具体实现代码如下：(此处参考)

 #include<stdio.h>  #define SharedStackMax 100 typedef char SharedStackType; typedef struct SharedStack{      SharedStackType data[SharedStackMax];      size_t top1;      size_t top2; }SharedStack; void SharedStackInit(SharedStack*stack) { if(stack==NULL) { return; }      stack->top1=0;      stack->top2=SharedStackMax; } void SharedStackPush1(SharedStack*stack,SharedStackType value) { if(stack==NULL) { return; } if(stack->top1==stack->top2) { return; }      stack->data[stack->top1++]=value; return; } void SharedStackPush2(SharedStack*stack,SharedStackType value) { if(stack==NULL) { return; } if(stack->top2==stack->top1) { return; }                                                                             stack->data[--stack->top2]=value; } int SharedStackTop1(SharedStack*stack,SharedStackType*value) { if(stack==NULL||value==NULL) { return 0; } if(stack->top1==0) { return 0; } *value=stack->data[top1-1]; return 1; } int SharedStackTop2(SharedStack*stack,SharedStackType*value) { if(stack==NULL||value==NULL) { return 0; } if(stack->top2==SharedStackMax) { return 0; } *value=stack->data[stack->top2]; return 1; } void SharedStackPop1(SharedStack*stack) { if(stack==NULL) { return; } if(stack->top1==0) { return; }      stack->top1--; } void SharedStackPop2(SharedStack*stack) { if(stack==NULL) { return; } if(stack->top2==SharedStackMax) { return; }      stack->top2++; }