03.堆疊與佇列( Stack and Queue )

上課內容精要！！

3.1 堆疊和佇列基本觀念

堆疊(Stack)

加入(push)與刪除(pop)於同一端。後進先出(LIFO)

例子：堆積木、蓋房子

佇列(Queue)

加入與刪除於不同端(front & rear)。先進先出(FIFO)

例子：排隊買票、坐公車

3.2 堆疊的加入與刪除

3.2.1 堆疊加入函數(top的初始值為-1)

3.2.2 堆疊刪除函數

3.3 佇列的加入與刪除

3.3.1 佇列加入函數(front、rear的初始值分別為0、-1)

3.3.2 佇列刪除函數

[ 問題 ] 佇列前端還有空位，但要加入元素卻發現此佇列已滿

[ 解決方式 ] 環狀佇列

3.3.3 環狀佇列加入函數(front、rear的初始值均為MAX-1)

3.3.4 環狀佇列刪除函數

3.4 堆疊與佇列的應用

堆疊的應用 ：副程式的呼叫 (subroutine calls)

中序表示式 → 後序表示式

佇列的應用 ： 作業系統的工作安排(job scheduling)

中序表示式 ：「運算子」(operator)置於「運算元」(operand)的中間

Ex： A*B / C

後序表示式 ：「運算子」置於「運算元」的後面

Ex：AB * C /

3.5 如何計算後序表示式

利用＜運算元堆疊法＞

3.6 老掉牙的應用問題

數獨遊戲 (個人經常給學生玩的數獨網站) http://oddest.nc.hcc.edu.tw/sumain.htm

Algorithm Gossip: 八個皇后

老鼠走迷官（一）

河內塔

(以上三個連結取自 良葛格學習筆記 - 困在技術撰稿人身體裡的小說家)