數據結構導論(第三章棧）

一、棧

棧和隊列可看作是特 殊的線性表，它們是 運算受限的線性表

定義：棧是只能在表的一端（表尾）進行 插入和刪除的線性表

• 允許插入及刪除的一端（表尾）稱為棧頂(Top)； .
• 另一端（表頭）稱為棧底(Bottom)。 .
• 當表中沒有元素時稱為空棧
• 進棧——在棧頂插入一元素；
• 出棧——在棧頂刪除一元素

特點：後進先出

　　棧中元素按a1，a2，a3，…an的次序進棧，出棧的第一個元素應 為棧頂元素。換句話說，棧的修改是按後進先出的原則進行的。 因此，棧稱為後進先出線性表（LIFO）。

棧的用途：常用於暫時保存有待處理的數據。

棧的基本操作

• （1）初始化棧：InitStack(S);
• （2）判棧空：EmptyStack (S);
• （3）進棧：Push (S,x);
• （4）出棧：Pop (S);
• （5）取棧頂： GetTop(S);

棧的分類：按照順序結構存儲是順序棧、按照鏈式結果存儲是鏈棧

二、順序棧

順序棧—— 即棧的順序實現；

棧容量——棧中可存放的最大元素個數；

棧頂指針 top——指示當前棧頂元素在棧中的位置；

棧空——棧中無元素時，表示棧空；

棧滿——數組空間已被占滿時，稱棧滿；

下溢——當棧空時，再要求作出棧運算，則稱“下溢”；

上溢——當棧滿時，再要求作進棧運算，則稱“上溢”。

1、順序棧的類型定義

const int maxsize=6;
typedef struct seqstack {
　　DataType data[maxsize];
　　int top;
}SeqStk;

SeqStk *s ; 定義一順序棧s
約定棧的第1個元素存在data[1]中,則
s->top==0 代表順序棧s為空；
s->top==maxsize-1 代表順序棧s為滿

2、初始化：

int Initstack(SeqStk *stk){
    stk->top=0;
    return 1;
}

3、判棧空（棧空時返回值為1，否則返回值為0）

int EmptyStack(SeqStk *stk){
    if(stk->top= =0) return 1;
    else return 0;
}

4、進棧

int Push(SeqStk *stk, DataType x){
    /*數據元素x進順序棧sq*/
    if（stk->top==maxsize -1) /*判是否上溢*/
    { error(“棧滿”);return 0;} /*上溢*/
    else {
        stk->top++；/*修改棧頂指針，指向新棧頂*/
        stk->data[stk->top]=x; /*元素x插入新棧頂中*/
        return 1;
    }
    }
}

 5、出棧

int Pop(SeqStk *stk){
    /*順序棧sq的棧頂元素退棧*/
    if(stk->top==0) /*判是否下溢*/
    { error(“棧空”);return 0;} /*下溢*/
    else {
    stk->top-- ； /*修改棧頂指針，指向新棧頂*/
    return 1;
    }
}/*Pop*/

6、取棧頂元素

DataType GetTop(SeqStk *stk)
{
if(EmptyStack(stk))
return NULLData;
else
return stk->data[stk->top];
}

三、鏈棧

鏈棧的定義： 棧的鏈式存儲結構稱為鏈棧，它是運算受限的單鏈表， 插入和刪除操作僅限制在表頭位置上進行。棧頂指針就是鏈 表的頭指針

1、初始化

void InitStack(LkStk *LS)
{
　　LS=(LkStk *)malloc(sizeof(LkStk));
　　LS->next=NULL;
}

2、判棧空

int EmptyStack(LkStk *LS)
{
    if(LS->next= =NULL) return 1;
    else return 0;
}

3、進棧——在棧頂插入一元素x

void Push (LkStk *LS, DataType x){ 
    LkStk *temp;
    temp= (LkStk *) malloc (sizeof (LkStk));
    temp->data=x;
    temp->next=LS->next;
    LS->next=temp;
}

4、出棧——在棧頂刪除一元素，並返回

int Pop (LkStk *LS)
{
    LkStk *temp;
    if (!EmptyStack (LS))
    {
        temp=LS->next;
        LS->next=temp->next;
        free(temp);
        return 1;
    }
    else return 0;
}

5、取棧頂元素

DataType GetTop(LkStk *LS)
{
    if (!EmptyStack(LS))
    return LS->next->data;
    else
    return NULLData;
}