Chapter 2 堆疊 - Ian-Liu-1990/Data-Structure GitHub Wiki

１. 堆疊: FILO，插入與刪除都在同一邊

  • 定義 : 有序儲存資料結構，資料操作有先進後出的特色，插入與刪除都在同一邊
  • 應用 :
    1. 活動紀錄 : 區塊結構之程式語言，紀錄執行期環境需要使用的活動紀錄，包括區域變數，動態配置記憶體，靜態和動態連結
    2. 中斷處理 : 紀錄被中斷程式狀態，返回位置，旗標號等
    3. 遞迴程式
    4. 回溯演算法 : 以堆疊紀錄滿一步狀態，不通再折返回上一步
    5. 中序式，前序式和後序式三者轉換 : 後序式求值計算

關鍵Code

  1. 初始化，宣告為Global的
const int N = 100
int stack[100];
int sp;

void creatStack()
{
  sp = -1;
}
  1. 檢查滿
Boolean IsStackFull()
{
 if(sp == N-1)
   return 1;
 else
   return 0;
}
  1. 檢查空
Boolean IsStackEmpty()
{
  if(sp < 0)
    return 1;
  else
    return 0;
}
  1. Insert
int push(int a[], int d) //假設a陣列大小10，top預設-1，top可儲存Index:0~9
{
    if (IsStackFull()){
        printf("Is Full!")
        return 0;
    }
    
    sp = sp + 1;
    a[sp] = d;
}
  1. Pop
int pop(int a[])
{
   int temp = 0;
   if (IsStackEmpty){
     printf("Is Empty");
     return temp;
   }
   
   temp = a[sp]; // pop表示位置有值"與queue不同"，需要先取值，才能指標向下!!!
   sp = sp -1;
   return temp;
}

２. 堆疊應用