Chapter 3 堆疊與佇列 ( Stacks and Queues )

學習目標 在學習本章之後，讀者們要能夠瞭解： 1.堆疊與佇列的資料型態。 2.堆疊與佇列的演算法與資料結構。 3.在電腦程式中如何模擬堆疊與佇列。

堆疊與佇列

什麼是堆疊 這樣的方式也叫做先進後出 最先進入的最後出來，最後進去的最先出來。

什麼是佇列 也稱為先進先出。

堆疊與佇列的資料結構 堆疊是A ， B ， C進；C ， B ， A出，稱為先進後出。 佇列是A ， B ， C進；A ， B ， C出，稱為先進先出。

堆疊的應用 副程式的呼叫   處理遞迴式呼叫叫   算術式之轉換   二元樹的追蹤   中斷處理 (Intrrupt Handing)   迷宮問題  

佇列的應用 作業系統的工作排序 用於印表機或作業系統的Spooling 計算機的模擬(Simulation) 資料通訊

堆疊(Stack)

定義 一群同質元素的組合，即有序串列(Ordered List) 所有的加入（Insertion;push）和刪除(Deletion;pop)動作均在頂端(Top)進行 具有後進先出(Last-In-First-Out；簡稱LIFO)的特性

特性 後進先出(LIFO， Last In First Out)的有序數列 加入與刪除資料只在頂端(top)進行 加入資料稱為push， 刪除資料資料稱為pop

字串特性的判別 假設我們想寫一個程式，以任意的字串為輸入，然後判定該字串是否順著念和逆著念結果都一樣。如何用堆疊來判別字串是否具有上述的特性，先將字串推進堆疊中，下次從堆疊中逐字推出時會得到倒著念的字串；若是從堆疊中逐字推出再推進另一個堆疊中，然後從堆疊再逐字推出會得到順著念的字串。只要將兩個字串逐字比對，就可判別原字串是否順著念和倒著念都能得到同樣的結果。由電腦來執行這一連串的操作，速度會很快。

用堆疊來判別字串的特性

加法器 加法器可以求取兩個整數相加之後的結果，當然，在程式語言中只要用「+」的運算元就能得到同樣的效果；不過，在這個例子裡頭，我們要用軟體來模擬硬體加法器 (Adder) 的操作。輸入的兩個整數各放到一個堆疊中，然後逐位數地推出相加，由於有進位的問題，所以一旦有進位，加法器會把1推入堆疊S中，下次逐位數相加時，必須再加上進位的值，也就是由堆疊S推出來的數值。因此，SUM=Digit1+Digit2+進位1，若有進位，則令進位2=1。

加法器的原理

堆疊的基本運作 CREATE(S)：建立空的堆疊。 PUSH(data, S)：將資料加入堆疊的頂端。 POP(S)：傳回堆疊頂端的資料，並將該筆資料自堆疊中刪除。 TOP(S)：傳回堆疊頂端的資料，但不將該筆資料自堆疊中刪除。 EMPTY(S)：若堆疊內已無任何資料，就傳回真值(True)，否則為假值(False)。 FULL(S)：若堆疊內已滿，就傳回真值(True)，否則為假值(False)。

構造與相關的操作

堆疊的表示法 陣列 鏈結串列 基本運作必須具備下列功能： 產生堆疊結構：宣告一個陣列或鏈結串列結構。 將資料放入堆疊(Push動作)：更改Ｔop指標後，將資料存入堆疊；使用陣列時，必須判斷堆疊是否已滿。 刪除資料(Pop動作)：若堆疊不是空的，將頂端資料取出，並更改Top指標。 判斷堆疊是否滿溢：使用陣列時，判斷Top指標是否等於N-1。 判斷堆疊是否是空的：Top值小於0或指向NULL。

鏈結串列製作堆疊

陣列模擬堆疊 以一維陣列S(1 To n)表示一個堆疊 top表示最上層的索引值 當搬入時top+1 當搬出時top-1 如果是負的表示這一個堆疊空無一物

陣列圖解 建立一個陣列，top表示最上層的索引值,我們有必要知道最上層的值為何，方便於堆入(push)資料或是彈出(pop)資料： 當搬入時top+1，當搬出時top-1；如果是負的表示這一個堆疊空無一物。 索引 1 2 3 值 註標(top = -1) Ex：輸入(push)ABC，輸出(pop)CBA 放入A、B、C 輸入A 索引 1 2 3 值 A 註標(top = -1) top = 0

輸入B 索引 1 2 3 值 A B 註標 top = 1 輸入C 索引 1 2 3 值 A B C 註標 top = 2

接著輸出C、B、A 輸出C 索引 1 2 3 值 A B 註標 top = 1 輸出B 索引 1 2 3 值 A 註標 top = 0

輸出A 索引 1 2 3 值 註標(top= -1) top為負，表示空無一物。

堆疊的演算法與程式

堆疊的陣列宣告 C語言程式碼如下： #define N 100 /* N 為堆疊大小 */ int stack[N]; /* 陣列stack當作堆疊 */ int top= -1; /* top表頂端之位置 */

push操作 檢查堆疊是否已滿，若已滿則加入失敗。 否則將堆疊頂端之指標top 值加1 ，即top 上移一格，新資料在加入目前top所指之陣列元素位置中。

演算法：虛擬碼 Procedure push(int stack[ ] , int element) { index top; if (top ＞＝stack的範圍) 　顯示堆疊已滿的錯誤訊息; else top ＝ top＋1; stack[ top ]=element; }

C語言：程式碼(一) void push (int Stack[ ] , int MaxSize , int top , int item ) { if ( top ＞＝MaxSize－1 ) printf(“堆疊滿了…”) ; else Stack [+ +top ]＝item ; }

C語言：程式碼(二) void push(int d) /*加入資料於堆疊內*/ { if(top == N-1) printf("堆疊滿了\n"); /* 注意堆疊大小 */ exit(1); /* 加入失敗，執行結束 */ } /* end if */ stack[++top]=d; }

pop操作 檢查堆疊是否空了，若是空堆疊則刪除失敗。 否則傳回頂端資料後將top 值減1 ，即top 向下移一格。

演算法：虛擬碼 Procedure pop(int stack[ ]) { index top; if (top 己到堆疊底端) 　顯示錯誤訊息; else x=堆疊的頂端元素; top ＝ top－1; 傳回 x; }

C語言：程式碼(一) void pop (int Stack[ ] , int top ) { if ( top < 0 ) printf(“堆疊空了，無任何資料可刪…”) ; else print(“%d 從堆疊被刪除了” , Stack [ top ] ) ; x ＝ stack [top - - ]; }

C語言：程式碼(二) int pop() { if(top == -1) /* 注意空堆疊情形*/ { printf("堆疊空了\n"); exit(1); /*刪除失敗，執行結束 */ } return(stack[top--]);

範例 寫一個具有push壓(input)，彈(pop)的程式： #include <stdio.h> struct node                 // 宣告一個結構 { int number; struct node *next; }; void showmain(); struct node *push(struct node *); struct node *pop(struct node *);

void main() { struct node *top = NULL; do{ showmain();           // 列印表單 switch (getche()) { case '1': top = push(top);            // 壓入 break; case '2': top = pop(top);            // 彈出 case '3': exit(0); default: printf("\nIt is wrong,pleace input again\n"); } }while (1);

void showmain() { printf("<1>push a value\n"); printf("<2>pop a value\n"); printf("<3>exit\n"); } struct node *push(struct node *top) { struct node *New; New = (struct node *)malloc(sizeof(struct node));        // 新節點 printf("pleace input a number"); scanf("%d",&(New->number));                                   // 輸入值 New->next = top;                                                         // 將新節點的next指向top top = New;                                         // 再將top指向New return (top);                                       // 傳回top }

struct node *pop(struct node *top) { struct node *freenode; if (top != NULL)                      // 當top為NULL表示沒有值,不可彈出 { printf("\nThe pop number is %d\n",top->number); freenode = top;                  // 紀錄需要釋放的節點 top = top ->next;               // top彈出之後top要往回一格 free (freenode);                 // 釋放記憶體 return (top);                      // 回傳top } else { printf("\nNo Node\n"); return (NULL); }