兩棧共享存儲空間

   兩棧共享空間就是指，當其中一個棧的空間用光時，可以借用另外一個棧的空間，這樣就大大提高了空間的利用率。

   一個數組有兩個端點，一個起始端點，另一個是數組末尾。而兩個棧有兩個棧底，我們就將其中一個棧底作為數組的起始端點，另一個棧底作為數組的末端。兩個棧如果增加元素，就向中間延伸。

   那么，我們該如何操作這個共享空間的棧呢？其中一個棧的top指針指向數組0處，另一個棧的top指針指向數組(n-1)處，n為數組長度。當top1 = -1， top2 = n時，意味著棧1和棧2都為空棧。當有數據存放在棧1中時，那么top1++,如果有元素存放在棧2中，則top2--。那么如何開辟兩棧共享空間這樣的結構呢？很明顯需要一個數組，還需要兩個指針，一個指向數組的頂端作為棧1的棧頂指針，另一個指向數組的底端作為棧2的棧頂指針。代碼如下：

typedef struct{
    
    SElemType data[MAXSIZE];
    int top1;     //棧1的棧頂指針 
    int top2;     //棧2的棧頂指針
}SqDoubleStack;

   那么如何實現元素的插入呢？首先你得確定插入的是棧1還是棧2，所以需要一個判斷棧1還是棧2的變量stackNumber。當實現元素的插入時，首先得判斷棧是否為滿棧，如果滿棧，則插入失敗，因為已經沒有空間放入新的元素了。什么時候是滿棧呢？當指針top1和指針top2相差為1時，也就是兩個指針見面時，此時為滿棧。代碼如下：

top1 + 1 == top2;

如果不是滿棧，則可以繼續插入元素，此時，就是判斷是放入棧1還是棧2。如果是放入棧1，則

s->data[++s->top1] = e;

如果是放入棧2，則

s->data[--S->top2] = e;

完整代碼如下：

Status Push ( SqDoubleStack *S, ElemType e, int stackNumber )
{
    if ( top1 + 1 == top2 )
        return ERROR;
    
    if ( stackNumber == 1 )
        S->data[++S->top1] = e;
    if ( stackNumber == 2 )
        S->data[--S->top2] = e;
        
    return OK;

}

   同樣的，元素的刪除也就是元素的彈出(POP)操作，跟元素的彈入(PUSH)類似。想要刪除元素，首先要判斷是棧1的元素還是棧2的元素，如果是棧1的元素，接著要判斷棧1是否為空棧，如果為空棧，則刪除失敗，如果不為空棧，則

--S->top1;

如果是棧2的元素，要判斷棧2是否為空棧，如果不為空棧，則

++S->top2;

完整代碼如下：

Status ( SqDoubleStack *S, ElemType *e, int stackNumber )
{
    if ( stackNumber == 1 ){
    
        if ( S->top1 == -1 )
            return ERROR;
        
        *e = S->data[S->top1--];
        
    }
    
    if ( stackNumber == 2 ){
    
        if ( S->top2 == MAXSIZE )
            return ERROR;
            
        *e = S->data[S->top2++];
  
    }

    return OK;
}