数据结构-共享栈

1.概念 

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

2.栈的基本操作

2.1 栈空

什么时候栈为空？

0号栈：top0 == -1
1号栈：top1 == MaxSize

  //判断是否栈空 
  int IsEmpty(SharedStack s){
 	//是否栈空 
 	if(s.top0 == -1 && s.top1 == MaxSize){
 		return 0;
	 }
	 return 1;
  } 

 

2.2 栈满：

两个栈顶指针重合时，表示共享栈已经满了

top1 = top0 + 1;

//判断是否栈满  
int IsStackFull(SharedStack s,ElemType *x){
 	//是否栈满 
 	if(s.top0+1 == s.top1){
 		return 0;
	 }
	 return 1;
 }

2.3 进栈

0号栈：先栈顶指针加一，再元素进栈：  tack[++top[0]]=x;
1号栈：先栈顶指针减一，再元素进栈： tack[--top[0]]=x;

  //0号栈入栈 
 void SharedStackPush1(SharedStack *stack,ElemType value)
 {
     if(stack->top0+1 == stack->top1)
     {
     	printf("栈已经满了\n");
         return;
     }
     
     ++stack->top0;
     stack->data[stack->top0] = value;
     return;
 }
  //1号栈入栈 
 void SharedStackPush2(SharedStack *stack,ElemType value)
 {
     if(stack->top0+1 == stack->top1)
     {
     	printf("栈已经满了\n");
         return;
     }
     
     --stack->top1;
     stack->data[stack->top1] = value;
     return;
 }

2.4 出栈

0号栈：先取出栈顶元素，栈顶指针减一
1号栈：先取出栈顶元素，栈顶元素加一

  //0号栈出栈 
 void SharedStackPop1(SharedStack *stack,ElemType *value)
 {
     if(stack->top0 == -1)
     {
     	printf("栈已经空了\n");
         return;
     }
     
     *value =  stack->data[stack->top0];
     --stack->top0;
     return;
 }
  //1号栈出栈 
 void SharedStackPop2(SharedStack *stack,ElemType *value)
 {
     if(stack->top1 == MaxSize)
     {
     	printf("栈已经空了\n");
         return;
     }
     
     *value =  stack->data[stack->top1];
     ++stack->top1;
     return;
 }