資料結構——棧

1、棧的定義

​ 棧就是隻能在一端插入和删除資料的連結清單，這個端就叫做棧頂（top），最後一個添加的資料第一個被删除。是以，這也叫後進先出（LAST IN FIRST OUT）連結清單或是先進後對外連結表（FIRST IN LAST OUT）。

棧儲存的圖像表示：

（圖檔來自百度：

https://baike.baidu.com/pic/%E6%A0%88/12808149/0/06493638860a850cb8998fc0?fr=lemma&ct=single#aid=0&pic=06493638860a850cb8998fc0

）

2、棧的基本操作

對于棧有兩種操作：

• 進棧指令（PUSH）：在棧中現有元素頂部添加一個元素，新加入的元素變為最頂端的元素。
• 出棧指令（POP）：取出棧頂元素，删除棧中的這個元素。

3、棧的基礎經典算法

1．進棧（PUSH）算法

①若TOP≥n時，則給出溢出資訊，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）；

②置TOP=TOP+1（棧指針加1，指向進棧位址）；

③S(TOP)=X，結束（X為新進棧的元素）；

2．退棧（POP）算法

①若TOP≤0，則給出下溢資訊，作出錯處理(退棧前先檢查是否已為空棧， 空則下溢；不空則作②)；

②X=S(TOP)，（退棧後的元素賦給X）：

③TOP=TOP-1，結束（棧指針減1，指向棧頂）。

順序棧的儲存實作

#include <iostream>
#define MAXSIZE 100        //定義最大空間
#define ElemType int        //定義資料類型
#define ERROR 0
#define TRUE 1 
#define OVERFLOW -1

using namespace std;

typedef struct SNode *Stack;
struct SNode{
    ElemType Data[MAXSIZE];        //定義棧的空間
    int top;    //訓示棧頂的位置 
};           

順序棧的入棧實作

void Push(Stack Ptrs, ElemType item){
    if(Ptrs->top == MAXSIZE-1)        //棧滿
        cout << "Data overflow";
    else{
        Ptrs->Data[++(Ptrs->top)] = item;        //先使top上移一位，再指派
        
        //也可以寫成
        //Ptrs->top++;
        //Ptrs->Data[Ptrs->top] = item;
    }
}           

順序棧的出棧實作

ElemType Pop(Stack Ptrs){
    if(Ptrs->top == -1){        //棧空
        cout << "No data";
        return ERROR;
    }
    else{
        return (Ptrs->Data[Ptrs->top--]);        //先抛出top的值，再使top-1
    }
}           

4、共享棧——一個數組存放兩個棧

​ 這是一種合理使用空間的方法，使數組空間不被浪費太多

共享棧的定義：

​ 利用棧底位置相對不變的特性，可以讓兩個順序棧共享一個一維資料空間，将兩個棧的棧底分别設定在共享空間的兩端，兩個棧頂向共享空間的中間延伸。

其圖示為：

（圖檔來自網絡，侵删）

共享棧的儲存實作

#include <iostream>
#define MAXSIZE 100        //定義最大空間
#define ElemType int        //定義資料類型
#define ERROR 0
#define TRUE 1 
#define OVERFLOW -1

using namespace std;
typedef struct DoubleStack DS
struct DoubleStack{
    ElemType Data[MAXSIZE];
    int top1;        //定義第一個棧的頭位置
    int top2;        //定義第二個棧的頭位置
};

DS->top1 = -1;
DS->top2 = MAXSIZE;            

共享棧的入棧實作

void Push(DS Ptrs, ElemType item, int flag){
    //flag用于區分棧1和棧2
    if(Ptrs->top1 - Ptrs->top2 == 1)        //棧滿
        cout << "Data overflow"; 
    if(flag == 1)        //向棧1輸入
        Ptrs->Data[++(Ptrs->top1)] = item;
    else if(flag == 2)        //向棧2輸入
        Ptrs->Data[--(Ptrs->top2)] = item;
}
           

共享棧的出棧實作

ElemType Pop(DS Ptrs, int flag){
    if(flag == 1){        //判斷為棧1
        if(Ptrs->top1 == -1){        //棧空
            cout << "No data";
            return nullptr;
        }
        else
            return Ptrs->Data[(Ptrs->top1)--];
    }
    else if(flag == 2){        //判斷為棧2
        if(Ptrs->top2 == MAXSIZE){        //棧空
            cout << "No data";
            return nullptr;
        }
        else
            return Ptrs->Data[(Ptrs->top1)++];
    }
}           

5、鍊式棧

鍊式棧不需要預先配置設定容量，也無需增加容量，但是需要連結清單的首位作為top（棧的頂端元素）

鍊式棧的儲存實作

#include <iostream>
#define MAXSIZE 100        //定義最大空間
#define ElemType int        //定義資料類型
#define ERROR 0
#define TRUE 1 
#define OVERFLOW -1

using namespace std;

typedef struct LinkStack *LS;
struct LinkStack{
    ElemType Data;        
    LinkStack *Next;
};           

建立一個空的鍊式棧

LS CreateStack(){
    LS s;
    s = new(LinkStack);        //申請空間
    s->Next = nullptr;
    return s;
}           

鍊式棧的入棧實作

void Push(ElemType X, LS s){
    LS ssr = s;
    ssr = new(LinkStack);
    ssr->Data = X;        //插入值X
    ssr->Next = s->Next;        //插入
    s->Next = ssr; 
}           

鍊式棧的出棧實作

ElemType Pop(LS s){
    LS FirstCell;
    ElemType Top;
    if(s->Next == nullptr)        //判斷是否為空棧
        cout << "No data";
    else{
        FirstCell = s->Next;
        s->Next = FirstCell->Next;
        Top = FirstCell->Data;;
        delete FirstCell;        //釋放空間，防止記憶體洩漏
        return Top;
    }
}           

6、棧的簡單應用

中綴表達式

基本政策：

​ 将中綴表達式轉化成字尾表達式，然後求值

将中綴表達式轉化成字尾表達式的方法：