Chap2 Stack & Queue
Stack 堆疊（Stack） 採用後插入者先刪除(LIFO, Last In First Out)的規則 資料插入和刪除的動作只發生在堆疊的頂端（Top） Stack結構 自助餐廳裡餐盤由桌面往上一個一個疊放的方式就是一個
Stack基本運作 1. 產生堆疊結構 2.將資料放入堆疊（Push） 利用程式語言的宣告（Declaration）指令，將堆疊宣告成陣列（假設陣列之大小為 N 並且資料從第 0 個索引開始存放）或鏈結串列(Linked List) 結構。 2.將資料放入堆疊（Push） 更改 Top 指標後，將資料存入堆疊，但必須 先判斷堆疊是否已滿（使用陣列時） 。
Stack基本運作 3.刪除資料（Pop）: 4.判斷堆疊是否滿溢： 5.判斷堆疊是否是空的： 若堆疊不是空的，則將頂端資料取出，並更改 Top 指標值。 4.判斷堆疊是否滿溢： 判斷 Top 指標是否等於 N ━ 1？（使用陣列時）。 5.判斷堆疊是否是空的： Top 值小於 0 （陣列） 或 Top 指向 NULL （鏈結串列）。
Stack的應用 副程式的呼叫(Subroutine Call) 用Stack儲存Return Address(即呼叫副程式的下一行指令的位址) 將算式運算式從中序表示式(infix)轉換為後序(postfix)或前序(prefix)表示式 A*B/C (infix) AB*C/ (postfix)
Queue 佇列（Queue） 採先插入者先刪除(FIFO , First In First Out)規則 資料的插入刪除分別發生在佇列的兩端， 插入的一端稱為尾端（Rear） 刪除的一端稱為前（首）端（Front） 常見的佇列 搭公車時大排長龍準備上車時 買票的人隊伍 高速公路收費站前大排長龍等待繳費的車陣
Queue 佇列的表示法 陣列是屬於循序配置(Sequential Allocation) 鏈結串列則是屬於動態配置( Dynamic Allocation）
Queue基本運作 1.產生佇列結構： 2.將資料加入佇列： 3.從佇列刪除一個元素： 宣告一個陣列結構或鏈結串列結構，並設定成空佇列，即Front = Rear = -1 或 Front = Rear = NULL(=0)。 2.將資料加入佇列： 若佇列未滿溢，則改變Rear指標後將資料存入佇列之Rear位置。 3.從佇列刪除一個元素： 若非空佇列，則改變 Front 指標後將 Front 所指到之佇列元素刪除。
Queue基本運作 4.判斷佇列是否滿溢： 5.判斷是否為空佇列： 當 Rear = N-1 時，表示佇列滿溢(Overflow)。（假設陣列之大小為 N ，並且資料從第 0 個索引開始存放） 5.判斷是否為空佇列： 當 Front = Rear 時，為空佇列。
3種常見的變形佇列 環狀佇列（Circular Queue） 優先佇列（Priority Queue） 每一個佇列中的元素，我們都賦予一個代表優先權的數字，最大的數字就有最高的優先權。 應用 CPU 的工作排程(Job Schedule, Task Schedule) 作為輸出入工作緩衝區： SPOOLING，是先將輸入資料寫在磁碟上，再輸入電腦處理，處理 後的資料先寫在磁碟上，再由印表機印出。 用於電腦模擬（Computer Simulation）方面 在模擬中經常有時間導向（time - driven）或事件導向（event - driven）的輸入訊號，由於訊號到達的時間不一定，也是用佇列來安排。 雙向佇列（Double Ended Queue）