數據結構學習筆記＜2＞堆疊

一、堆疊的抽象數據類型描述#

類型名：堆疊（Stack）
數據對象集：一個有 0 個或多個元素的有窮線性表
操作集：長度為 MaxSize 的堆疊 S∈Stack, 堆疊元素 item∈ElementType

1. 生成空堆疊，其最大長度為 MaxSize;
Stack CreateStack(int MaxSize);
2. 判斷堆疊 S 是否已滿
int IsFull(Stack S, int MaxSize);
3. 將元素 item 壓入堆疊
void Push(Stack S, ElementType item);
4. 判斷堆疊 S 是否已空
int IsEmpty(Stack S);
5. 刪除並返回棧頂元素
ElementType Pop(Stack S);

二、棧的順序存儲實現#

1. 定義#

棧的順序存儲結構通常由一個一維數組和一個記錄棧頂元素位置的變量組成

#define MaxSize <儲存數據元素的最大個數>
typedef struct SNode *Stack;//定義SNode的結構指針可以用Stack
struct SNode {
    ElementType Data[MaxSize];//一維數組
    int Top;//記錄棧頂元素
};

Stack PtrS 既定義了一個指向 SNode 的結構體指針 PtrS

2. 操作#

(1) 入棧操作 (Push)#

Top 值加一，儲存元素 item 在棧頂

void Push(Stack PtrS, ElementType item) {
    if (PtrS->Top == MaxSize-1) {//堆疊全部放滿了
        printf("堆疊滿");
        return;
    } else {    //堆疊未滿，執行入棧操作
        PtrS->Data[++(PtrS->Top)] = item;//Top值先增加，然後儲存
        return;
    }
}

(2) 出棧操作 (Pop)#

將元素彈出，Top 值減一

ElementType Pop(Stack PtrS) {
    if(PtrS->Top == -1) {//堆疊為空
        printf("堆疊空");
        return ERROR;//ERROR是ElementType的特殊值，表示錯誤。
    } else 
        return (PtrS->Data[(PtrS->Top)--]) //先把棧頂元素返回，再將Top減一
}

三、棧的鏈式存儲實現#

1. 定義#

棧的鏈式存儲結構實際上就是一個單鏈表，叫做鏈棧，插入和刪除操作只能在鏈棧的棧頂進行。棧頂指針 Top 應在鏈表的頭部！

typedef struct SNode *Stack;
struct SNode {
    ElementType Data;//當前數據
    struct SNode* Next;//指向下一個Snode的指針
};

2. 操作#

(1) 堆疊初始化（CreateStack）#

構建一個堆疊的頭結點，返回指針

Stack CreateStack() {
    Stack S;
    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

(2) 判斷堆疊是否為空（IsEmpty）#

判斷堆疊 S 是否為空，若為空函數返回 1，否則返回 0

int IsEmpty(Stack S) {
    return (S->Next == NULL);//若後面沒節點，則為空
}

(3) 將元素 item 壓入堆疊 (Push)#

先創建一個新結點的結構指針 TmpCell，分配空間，然後將數據賦值為 item，Next 指針賦值為原先的 S 的 Next 指針。再將 S 的 Next 指針指向 TmpCell。

void Push(ElementType item, Stack S) {
    Stack TmpCell;
    TmpCell = (Stack) malloc(sizeof(struct SNode));
    TmpCell->Data = item;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
}

(4) 刪除並返回堆疊 S 的棧頂元素 (Pop)#

先暫存當前結點 (S) ，將 FirstCell 賦值為 S 的 Next 指針，再將 S 的 Next 指針賦值為下一個的地址，既讓 S 的 Next 指針直接指向第二個結點。然後將 FirstCell 內的數據取出並釋放動態分配的內存，返回該數據。

ElementType Pop(Stack S) {
    Stack FirstCell;
    ElementType TopElem;
    if(IsEmpty(S)) {//若為空
        printf("堆疊空");
        return NULL;
    } else {
        FirstCell = S->Next;//先把指向下一個結點的指針存起來
        S->Next = FirstCell->Next;
        TopElem = FirstCell->Data;
        free(FirstCell);
        return TopElem;
    }
}

四、堆疊應用（表達式求值）#

中綴表達式如何轉換為後綴表達式？
從頭到尾讀取中綴表達式的每個對象，對不同對象按照不同情況處理

1. 運算數：直接輸出。#

2. 左括號：壓入堆疊。#

3. 右括號：將棧頂的運算符彈出並輸出，直到遇到左括號（出棧，不輸出）#

4. 運算符：優先級大於棧頂運算符時，將其壓入棧中；優先級小於等於棧頂運算符時，將棧頂運算符彈出並輸出，再比較新的棧頂運算符，直到該運算符大於棧頂運算符優先級位置，然後將該運算符壓入棧中。#

5. 若各對象處理完畢，則將堆疊中存留的運算符一併輸出。#

堆疊的其他應用：函數調用與遞歸實現、深度優先搜索、回溯算法等……