資料結構複習(六) : 堆疊 Stack

前面學了這麼久線性表，大家肯定都昏了吧!!今天來講線性表的應用，Stack & Queue，這兩種數據結構都是大家生活中常見的，非常常用到喔!!

堆疊可以被認為是有約束力的線性表，插入和刪除接操作於top頂點位置。現實生活中也常常能遇到堆疊的例子，例如餐廳的盤子疊，洗盤子時必定是從上面開始洗，放盤子也是從上面開始放，這種操作方式稱為後入先出(Last In First Out)，LIFO。

圖摘自<<數據結構>> (第二版) P.72 陈越、何钦铭

由於堆疊是一種線性表，因此可以區分為順序堆疊、鏈式堆疊，下面介紹堆疊常見方法:

1. Stack createStack(iny MaxSize)    //建立堆疊，大小為MaxSize
2. bool isFull(Stack S)              //是否已滿
3. bool Push(Stack S, ElementType X) //壓入堆疊
4. bool isEmpty(Stack S)             //是否為空
5. ElementType Pop(Stack S)          //彈出頂元素，如果為空，返回錯誤數

一、順序堆疊

先來看看結構:

typedef int Position;
typedef struct SNode * PtrToSNode;
struct SNode{
  ElementType *Data;    //大家還記得malloc那一章節嗎?(笑)
  Position Top;
  int MaxSize;
};
typedef PtrToSNode Stack; //只是取一個好聽的名字，本質上還是Struct SNode *

1. 建立空堆疊 (createStack) :

Stack createStack(int MaxSize){
  Stack S = (Stack)malloc(sizeof(struct SNode));
  S->Data = (ElementType *)malloc(sizeof(ElementType)*MaxSize);
  S->Top = -1;   //空堆疊 top=-1，top就是data的下標
  S->MaxSize=MaxSize;
}

2. 已滿/空 (isFull/isEmpty) :

bool isFull(Stack S) {
  if(S->Top == S->MaxSize-1)
     return true;
  else
     return false;
}
bool isEmpty(Stack S){
  return (S->Top == -1);
}

3. 壓入 (Push) :

bool Push(Stack S,ElementType X){
  if(isFull(S)){
    printf("已滿");
    return false;
  }else{
    S->Data[++(S->Top)]=X;  //++S->Top 等於 先S->Top++
    return true;
  }
}

4. 彈出 (Pop) :

ElementType Pop(Stack S){
  if(isEmpty(S)){
    printf("已空");
    return -1;   //約定-1為錯誤數
  }else{
    return S->Data[(S->Top)--];   //先S->Data 再 S->Top--
  }
}

二、鏈式堆疊

鏈式堆疊跟鏈表差不多，但沒有了最大節點數限制，新增刪除只能鏈表的"頭"進行，頭就是鏈式堆疊的Top，為了插入方便，頭時常會設計有空結點，表頭空結點後一個節點即是堆疊的頂節點，節點結構如下 :

typedef struct SNode * PtrToSNode;
struct SNode{
  ElementType Data;
  PtrToSNode Next;
};
typedef PtrToSNode Stack;

1. 建立 (createStack) & 是否為空(isEmpty):

//記得在頭建立空結點
Stack createStack (){
  Stack S;
  S=(Stack)malloc(sizeof(struct SNode));  //建立空結點
  S->Next = NULL;
  return S;
}
bool isEmpty(Stack S){
  return (S->Next == NULL);              //S->Next 沒東西代表為空
}

2. 壓入(Push) (可以實際畫畫看來正確觀念喔) :

bool Push(Stack S,ElementType x){
  PtrToSNode temp = (PtrToSNode)malloc(sizeof(struct SNode));
  temp->Data = x;
  temp->Next = S->Next;   //由於開頭是空結點，所以用S->Next取得表頭
  S->Next=temp;           //temp 押入表頭，S->Next 指向temp;
  return true;
}

3. 彈出(Pop) :

//彈出時記得檢查是否為空，Pop的操作順序恰恰與Push相反
ElementType Pop(Stack S){
  if(isEmpty(S)){
    printf("表是空的!!");
    return -1;
  }else{
    PtrToSNode temp = S->Next;         //temp為頭結點
    S->Next = temp -> Next;
    ElementType Num = temp -> Data;
    free(temp);
    return Num;
  }
}

寫到這裡你就能更完整的比較出"順序結構與鏈式結構的差異"，Stack 非常重要不論哪個考試都會考到，大家加油 !! 下一個章節會講到Queue 如何排隊。

完整程式碼:

1. 順序 :

2. 鏈式 :

參考資料 :

1. 《数据结构》（第2版），陈越、何钦铭、徐镜春、魏宝刚、杨枨 编著，高等教育出版社，2016年6月
2. https://www.icourse163.org/course/ZJU-93001

資料結構複習(五) : 線性表 — 順序結構

資料結構複習(七) : 隊列 Queue