兩棧共享存儲(chǔ)空間

   兩棧共享空間就是指，當(dāng)其中一個(gè)棧的空間用光時(shí)，可以借用另外一個(gè)棧的空間，這樣就大大提高了空間的利用率。

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

   那么，我們?cè)撊绾尾僮鬟@個(gè)共享空間的棧呢？其中一個(gè)棧的top指針指向數(shù)組0處，另一個(gè)棧的top指針指向數(shù)組(n-1)處，n為數(shù)組長(zhǎng)度。當(dāng)top1 = -1， top2 = n時(shí)，意味著棧1和棧2都為空棧。當(dāng)有數(shù)據(jù)存放在棧1中時(shí)，那么top1++,如果有元素存放在棧2中，則top2--。那么如何開(kāi)辟兩棧共享空間這樣的結(jié)構(gòu)呢？很明顯需要一個(gè)數(shù)組，還需要兩個(gè)指針，一個(gè)指向數(shù)組的頂端作為棧1的棧頂指針，另一個(gè)指向數(shù)組的底端作為棧2的棧頂指針。代碼如下：

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

   那么如何實(shí)現(xiàn)元素的插入呢？首先你得確定插入的是棧1還是棧2，所以需要一個(gè)判斷棧1還是棧2的變量stackNumber。當(dāng)實(shí)現(xiàn)元素的插入時(shí)，首先得判斷棧是否為滿棧，如果滿棧，則插入失敗，因?yàn)橐呀?jīng)沒(méi)有空間放入新的元素了。什么時(shí)候是滿棧呢？當(dāng)指針top1和指針top2相差為1時(shí)，也就是兩個(gè)指針見(jiàn)面時(shí)，此時(shí)為滿棧。代碼如下：

top1 + 1 == top2;

如果不是滿棧，則可以繼續(xù)插入元素，此時(shí)，就是判斷是放入棧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)類似。想要?jiǎng)h除元素，首先要判斷是棧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;
}