数据结构-栈(3)

两栈共享空间

可以用一个数组来存储两个相同类型的栈。

数组有两个端点，两个栈有两个栈底，

让一个栈的栈底作为数组的开始端，下标为0处，

让另外一个栈的栈底作为数组的结束端，下标为n-1出。

两个栈如果增加元素，就是两个端点向中间延伸。

两个栈的栈底在数组两端， 新增元素，向中间考虑，即两个栈底的栈顶top1和 top2向中间靠拢， 只要top1和top2 不见面， 两个栈就可以一直使用。

当栈1为空时 top1 = -1

当栈2为空时 top2 = n

若栈2 是空栈， 栈1的top1 等于 n-1时， 就是栈1满了。

若栈1 是空栈， 栈2的的top2等于0时， 就是栈2满了。

两个栈见面时，也就是top1 和 top2之间差1时 ， 即top1+1 = top2 是栈满。

    //两栈共享空间结构
  typedef struct{
    SElemType data[MAXSIZE];
    //栈1栈顶指针
    int top1;
    //栈2栈顶指针
    int top2;
  }


  //两栈push方法
  Status Push(SqDoubleStack *S, SElemType *e, int stackNumber){
    //栈已满， 不能再push新元素
    if(S->top1+1 == S->top2){
      return ERROR;
    }
    //栈1有新元素进栈， 则先top1+1给数组元素赋值
    if(stackNumber == 1){
      S->data[++s->top1] = e;
    }else if(stackNumber == 2){
    //栈2有新元素进栈， 则先top2-1给数组元素赋值
      S->data[--S->top2] = e;
    }

    return ok;
  }
  
  //两栈pop方法 若栈不为空，则删除S的栈顶元素，用e返回其值， 并返回OK； 否则返回ERROR
    Status Pop(SqDoubleStack *S, SElemType *e, int stackNumber){
        
        if(stackNumber == 1){
            //栈1已经是空栈
            if(S->top1 == -1){
                return ERROR;
            }
            //栈1的栈顶元素出栈
            *e = S->data[S->top1--];
        }else if(stackNumber == 2){
            //栈2已经是空栈
            if(S->top2 == MAXSIZE){
                return ERROR;
            }
            //栈2的栈顶元素出栈
            *e = S->data[S->top2++];
        }   
        
        return OK;
    }