第 3 章 堆疊與佇列

目次 3.1 堆疊和佇列基本觀念 3.2 堆疊的加入與刪除 3.3 佇列的加入與刪除 3.4 其它形式的佇列 3.5 多個堆疊和多個佇列 3.1 堆疊和佇列基本觀念 3.2 堆疊的加入與刪除 3.3 佇列的加入與刪除 3.4 其它形式的佇列 3.5 多個堆疊和多個佇列 3.6 堆疊與佇列的應用 3.7 如何計算後序表示式 3.8 動動腦時間 3.9 練習題解答

3.1 堆疊和佇列基本觀念 堆疊(Stack) 加入(push)與刪除(pop)於同一端 後進先出(LIFO) 例子：堆積木、蓋房子

3.1 堆疊和佇列基本觀念(con.t) 佇列(Queue) 加入與刪除於不同端(front & rear) 先進先出(FIFO) 例子：排隊買票、坐公車

3.2 堆疊的加入與刪除 3.2.1 堆疊加入函數(top的初始值為-1) 3.2 堆疊的加入與刪除 3.2.1 堆疊加入函數(top的初始值為-1) void push_func(int stack[], int MAX, int top) { if (top >= MAX-1) /* 當堆疊已滿，則顯示錯誤 */ printf("Stack is full !"); else { top++; printf( “\n\n Please enter item to insert: "); scanf( "%d", &stack[top]); }

3.2 堆疊的加入與刪除(con.t) 3.2.2 堆疊刪除函數 void pop_func(int stack[], int top) { if (top < 0) /* 當堆疊沒有資料存在，則顯示錯誤 */ printf(“\n\n No item, stack is empty !\n"); else { printf("\n\n Item %d deleted\n", stack[top]); top --; }

3.3 佇列的加入與刪除 3.3.1 佇列加入函數(front、rear的初始值分別為0、-1) 3.3 佇列的加入與刪除 3.3.1 佇列加入函數(front、rear的初始值分別為0、-1) void enqueue_func(int q[], int MAX, int rear) { if (rear >= MAX-1) /* 當佇列已滿，則顯示錯誤 */ printf("\n\nQueue is full !\n"); else { rear++; printf("\n\n Please enter item to insert: "); scanf("%d",&q[rear]); }

3.3 佇列的加入與刪除(con.t) 3.3.2 佇列刪除函數 void dequeue_func(int q[], int front, int rear) { if (front > rear) /* 當資料沒有資料存在，則顯示錯誤 */ printf("\n\n No item, queue is empty !\n"); else { printf("\n\n Item %d deleted\n", q[front]); front++; }

3.3 佇列的加入與刪除(con.t) 問題 環狀佇列 佇列前端還有空位，但要加入元素卻發現此佇列已滿 圖3-2 環狀佇列 1 2 3 4 1 2 3 4 5 6 7 8 N-1 N-2 圖3-2 環狀佇列

3.3 佇列的加入與刪除(con.t) 3.3.3 環狀佇列加入函數(front、rear的初始值均為MAX-1) { void enqueue_func(int cq[], int MAX, int front, int rear) { rear = (rear + 1) % MAX; if (front == rear) { if (rear == 0) rear = MAX–1 ; /* 退回原位 */ else rear = rear–1 ; /* 退回原位 */ printf("\n\nQueue is full!\n"); } else { printf("\n\n Please enter item to insert: "); scanf("%d",&cq[rear]);

3.3 佇列的加入與刪除(con.t) 3.3.4 環狀佇列刪除函數 void dequeue_func(int cq[], int MAX, int front, int rear) { if (front == rear) printf("\n\n Queue is empty !\n"); else { front = (front + 1) % MAX; printf("\n\n Item %d deleted\n", cq[front]); }

3.4 其它形式的佇列 雙向佇列(deque) 優先權佇列(priority queue) Double-ended queue 3.4 其它形式的佇列 雙向佇列(deque) Double-ended queue 佇列的兩端皆可加入和刪除 Ex：循序輸入五筆資料(1、2、3、4、5) 優先權佇列(priority queue) 每筆資料是依照優先權的高低放在佇列的適當位置 優先權高，所在的位置愈前面(愈快被執行) Ex：Heap

3.5 多個堆疊與多個佇列 與單一堆疊和佇列的觀念大致相同 多個堆疊的加入、刪除也是在同一端 多個佇列的加入是在後端、刪除是在前端 3.5 多個堆疊與多個佇列 與單一堆疊和佇列的觀念大致相同 多個堆疊的加入、刪除也是在同一端 多個佇列的加入是在後端、刪除是在前端 Ex：公司將硬碟空間分割成多個部份給員工來使用 多個佇列的形狀圖 多個堆疊的形狀圖

3.5 多個堆疊與多個佇列(con.t) 3.5.1 多個堆疊加入函數 (課本圖3.3) void push_func (int MS[ ], int t[ ], int b[ ], int i ) { if (t[i-1] == b[i]) printf(“stack is full !!!”); else MS[++t[i-1]] = x; }

3.5 多個堆疊與多個佇列(con.t) 3.5.2 多個堆疊刪除函數 { if (t[i-1] == b[i-1]){ void pop_func (int MS[ ], int t[ ], int b[ ], int i, int x) { if (t[i-1] == b[i-1]){ printf(“stack is empty !!”); return 0; } else{ x = MS[t[i-1]--] ; print(“%d is deleted !!!”, x);

3.5 多個堆疊與多個佇列(con.t) 3.5.3 多個佇列加入函數 (課本圖3.4) void enqueue_func (int MQ[ ], int f[ ], int r[ ], int i, int x) { if (r[i-1] == f[i]) printf(“queue is full !!!”); else MQ[++r[i-1]] = x; }

3.5 多個堆疊與多個佇列(con.t) 3.5.4 多個堆疊刪除函數 { if (r[i-1] == f[i-1]){ void dequeue_func (int MQ[ ], int f[ ], int r[ ], int i, int x) { if (r[i-1] == f[i-1]){ printf(“queue is empty !!”); return 0; } else{ x = MQ[f[i-1]++] ; print(“%d is deleted !!!”, x);

3.6 堆疊與佇列的應用 堆疊的應用 佇列的應用 副程式的呼叫 (subroutine calls) 中序表示式 → 後序表示式 3.6 堆疊與佇列的應用 堆疊的應用 副程式的呼叫 (subroutine calls) 中序表示式 → 後序表示式 佇列的應用 作業系統的工作安排(job scheduling)

3.6 堆疊與佇列的應用(con.t) 中序表示式 後序表示式 「運算子」(operator)置於「運算元」(operand)的中間 Ex：A*B / C 後序表示式 「運算子」置於「運算元」的後面 Ex：AB * C /

3.6 堆疊與佇列的應用(con.t) 一般運算子的運算優先順序如下： 運算子 優先順序(數字愈大，優先順序愈高) * , / , % 5 運算子 優先順序(數字愈大，優先順序愈高) * , / , % 5 + (加), - (減) 4 <, <= , > , >= 3 && 2 || 1

3.6 堆疊與佇列的應用(con.t) 運用堆疊的觀念 符號 in-stack priority in-coming priority ) – – * , / , % 2 2 + (加), - (減) 1 1 ( 0 3

3.6 堆疊與佇列的應用(con.t) void infix_to_postfix(char infix_q[], int rear) { int top = 0, ctr; char stack_t[MAX]; /* 用以儲存還不必輸出的運算子 */ stack_t[top] = '#'; /* 於堆疊最底下加入#為結束符號 */ for(ctr = 0; ctr <= rear; ctr++) { switch(infix_q[ctr]) { /* 輸入為)，則內輸出堆疊內運算子，直到堆疊內為( */ case ')': while(stack_t[top] != '(') printf("%c", stack_t[top--]); top--; break; /* 輸入為#，則將堆疊內還未輸出的運算子輸出 */ case '#': while(stack_t[top] != '#')

3.6 堆疊與佇列的應用(con.t) /* 輸入為運算子，若小於TOP在堆疊中所指運算子，則將堆疊所指運算子輸 case '(': case '^': case '*': case '/': case '+': case '-': while(compare(stack_t[top], infix_q[ctr])) printf("%c", stack_t[top--]); stack_t[++top] = infix_q[ctr]; break; /* 輸入為運算元，則直接輸出 */ default : printf("%c", infix_q[ctr]); }

3.6 堆疊與佇列的應用(con.t) /* 比較兩運算子優先權，若輸入運算子小於堆疊中運算子，則傳值為1，否則為0 */ int compare(char stack_o, char infix_o) { int index_s = 0, index_i = 0; while(stack_priority[index_s] != stack_o) index_s++; while(infix_priority[index_i] != infix_o) index_i++; return index_s/2 >= index_i/2 ? 1 : 0; }

3.7 如何計算後序表示式 步驟 1：先將後序表示式以一字串表示 步驟 2：每次取出一個token，若 3.7 如何計算後序表示式 步驟 1：先將後序表示式以一字串表示 步驟 2：每次取出一個token，若 token為運算元，則將它push至堆疊中 token為運算子，則從堆疊中pop出二個運算元，並做適當的運算 token為’0’，則跳到步驟四 步驟 3：將步驟2的結果再push至堆疊，並繼續執行 步驟2。 步驟 4：彈出堆疊的資料，此資料即為後序表示法計 算的結果