資料結構與演算法 第三章 堆疊和佇列 徐熊健.

Presentation on theme: "資料結構與演算法 第三章 堆疊和佇列 徐熊健."— Presentation transcript:

1 資料結構與演算法 第三章 堆疊和佇列 徐熊健

2 大 綱 3.1 堆疊 3.2 堆疊的基本運算 3.3 佇列 3.4 佇列的基本運算 3.5 環狀佇列 3.6 老鼠走迷宮
大　　綱 3.1 　堆疊 3.2 　堆疊的基本運算 3.3 　佇列 3.4　 佇列的基本運算 3.5　 環狀佇列 3.6 　老鼠走迷宮 3.7 　運算式的轉換和求值

3 堆疊和佇列 堆疊擁有的共同特性就是—先行進入者將較後離去（first in last out, 或簡稱FILO）、或後來進入者可先行離去（last in first out, 或簡稱LIFO）。 佇列共同特性在於—先行進入者將率先離去（first in first out, 或簡稱FIFO）。

4 3.1 　堆疊 (a)描繪了依循增加(push)甲，乙，丙，丁，至堆疊Ｓ的邏 輯圖示。 (b)描繪了依循取出(pop)堆疊Ｓ內元素的邏輯圖示。

5 程序呼叫之範例一

6 堆疊解決堆疊程序呼叫時流程轉移的過程 堆疊保證了程序呼叫時流程轉移的正確性
在Ａ程序中呼叫 (call)程序B，遂將返回位址＃push入堆疊中，流程轉至B。 在程序Ｂ中呼叫程序C，將返回位址△push入堆疊中，流程轉至C。 空堆疊 程序C執行結束，pop出堆疊頂端元素△，做為流程轉移的目的地（返回B）。 程序Ｂ執行結束，pop出堆疊頂端元素＃做為流程轉移目的地（返回A）。 堆疊保證了程序呼叫時流程轉移的正確性

7 程序呼叫之範例二

8 堆疊的操作過程 空堆疊 push＃， 呼叫B push△呼叫C push＊呼叫D pop出＊ 流程跳至＊ pop出△ 流程跳至△ pop出⊙
流程跳至⊙ pop出＃ 流程跳至＃ push ⊙ 呼叫D push ● 呼叫D pop出● 流程跳至●

9 3.2 堆疊的基本運算 程式3-1 堆疊的宣告 1 #define maxsize 5; 2 int stack[maxsize];
3.2 堆疊的基本運算 程式3-1 堆疊的宣告 1 #define maxsize 5; 2 int stack[maxsize]; 3 int top= -1; 第2行中宣告了大小為5個整數的陣列，將之做為堆疊使用，命名成stack； 第3行宣告的top整數，將當成堆疊stack頂端元素在陣列中的註標，宣告成-1表示目前為一空堆疊，沒有任何頂端元素。

10 Push 運算 程式3-2 1 void push(int element) 2 { if (IsFull( )) StackFull();
3 else Stack[++top]=element; 4 }

11 Pop 運算 程式3-3 1 int pop() 2 { if (IsEmpty()) 3 { StackEmpty();
4 return -1; 5 } 6 return Stack[top--]; 7 }

12 IsFull運算及IsEmpty運算 程式3-4 IsFull運算 1 int IsFull( )
2 { if(top == maxsize-1) return 1; 3 else return 0; 4 } 陣列Stack中[0]~[maxsize-1]的位置皆放滿元素），來決定是否堆疊已滿？若滿了傳回1，否則傳回0。 程式3-5 IsEmpty運算 1 int IsEmpty() 2 { if ( top == -1) return 1; 3 else return 0; 4 }

13 3.3　佇 列 佇列 (queue) 是一個有序串列，為達成先進先出FIFO的效果，所有加入的動作皆在固定的一端進行，而所有刪除的動作則在另一端進行。 若Q = (ai, ai+1, … , aj) 為一佇列，我們稱ai為前端 (front) 元素，aj為後端 (rear) 元素 資料的加入乃在Q的後端進行，資料的刪除則由Q的前端進行，如此即可形成先進先出的資料結構。

14 佇列的邏輯圖示及其基本運算 依序增加元素進入佇列中 刪除佇列中的元素

15 3.4 佇列的基本運算 程式3-7 佇列的宣告 程式3-8 addQ運算 1 #define maxsize 10;
3.4　佇列的基本運算 程式3-7 佇列的宣告 1 #define maxsize 10; 2 int Queue[maxsize]; 3 int front = -1; 4 int rear = -1; 程式3-8 addQ運算 1 void addQ(int element) 2 { if (IsQFull()) QueueFull (); 3 else Queue [++rear]= element; 4 }

16 deleteQ 運算 程式3-9 1 int deleteQ() 2 { if (IsQEmpty()) 3 { QueueEmpty(); 4 return 0; 5 } 6 else return Queue[++front]; 7 } 第6行則當Queue 不是空的時候，傳回Queue[++front]，正是自該Queue中刪去的元素值，而且front註標也調整至正確的位置

17 IsQEmpty運算及IsQFull運算
1 int IsQEmpty() 2 { if (rear == front) return 1; 3 return 0 ; 4 } 程式3-11 IsQFull運算 1 int IsQFull() 2 { if (rear == maxsize-1) return 1; 3 return 0; 4 }

18 … 3.5 環狀佇列 線性的陣列因陣列元素位置與註標之對應關係，使其不方便模擬佇列的增加、刪除的消長現象，而用過的空位無法再行利用；
3.5　環狀佇列 線性的陣列因陣列元素位置與註標之對應關係，使其不方便模擬佇列的增加、刪除的消長現象，而用過的空位無法再行利用； 不過若將線性的陣列折繞成環狀 (circular) 陣列，就可再次使用到空出的空間。 假設n = 5，利用mod(i) 將循序的數列i轉變為呈環狀計數的數列： 於是原程式的++rear或++front，須分別改為++rear%n和++front%n，其中n為佇列的大小即可有環狀計的註標。 i 1 2 3 4 5 6 7 8 9 10 11 12 … mod(i)

19 範例3-5 rear front (a)空佇列 10 (b) addQ(10) rear front (c) addQ(20) rear
30 10 (d) addQ(30) rear front 20 30 10 (e) addQ(40) rear front 40 20 30 10 (f) addQ(50)，但佇列已滿 rear front 40 (h) deleteQ() 30 40 front (i) addQ(60) rear 30 40 front 60 (j) addQ(70) rear 30 40 front 60 70 (g) deleteQ() 20 30 40 front

20 程式3-12 環狀佇列 1 #define maxsize 10; 2 int CQueue[maxsize];
程式3-12 　環狀佇列 1 #define maxsize 10; 2 int CQueue[maxsize]; 3 int front = 0; 4 int rear = 0; 5 6 void addCQ(int element) 7 { if (IsCQFull()) CQueueFull (); 8 else CQueue [++rear%maxsize] = element; 9 } 10 front所指的位置為特意保留的空位；Queue[(front+1)% maxsize]為環狀佇列Queue的前端元素，Queue[rear % maxsize]為環狀佇列Queue的後端元素

21 程式3-12 環狀佇列(續) 11 int deleteCQ() 12 { if (IsCQEmpty())
程式3-12 　環狀佇列(續) 11 int deleteCQ() 12 { if (IsCQEmpty()) 13 { CQueueEmpty(); 14 return 0; 15 } 16 else return CQueue[++front%maxsize]; 17 } 18 19 int IsCQEmpty() 20 { if (rear == front) return 1; 21 return 0 ; 22 } 23 24 int IsQFull() 25 { if ((rear+1)%n == front) return 1; 26 return 0; 27 }

22 3.6 老鼠走迷宮 老鼠走迷宮是個有趣的心理實驗，把老鼠放入迷宮中，老鼠可靠單純的嚐試錯誤 (trial and error) 法，即找到出口。這種嚐試錯誤的策略並不考慮運算時間是否經濟，但對走迷宮這類毫無線索的問題，依然是個可行的策略，我們或稱之為「窮舉」 (enumeration) 的策略。 我們可用電腦程式模擬老鼠走迷宮的過程，採用的策略即為嚐試錯誤法，但是曾經走錯的路我們不應再次嚐試，雖然實際上老鼠不見得記得住曾走錯的路，但電腦在記憶方面可高明得多。事實上用來「記住窮舉過程中已走過的路徑」最好的資料結構就是堆疊 。

23 3.6 老鼠走迷宮(續) 首先應先設想必需的資料結構： 迷宮的表示（用二維陣列如何？隔牆、通路如何區隔？）
路徑的表示（用表示迷宮二維陣列的註標如何？） 走過的路徑（用另一個與迷宮二維陣列一樣大小的二維陣列，記錄是否走過如何？） 遭遇錯誤後的移動（利用堆疊記得從何而來？） 各位應養成思考問題時，同時溶入資料結構考量的能力。

24 3.6 老鼠走迷宮(續) 演算法3-1老鼠走迷宮 輸入：迷宮，以二維陣列maze表示。 輸出：從入口至出口的路徑。
1 (i,j,dir)=(1,1,E) 2 push ((i,j,dir)) 3 while (堆疊仍有資料) do 4 { (i,j,dir) = pop() 5 while (在(i,j)處仍有路可走) do 6 { (u,v) = 自(i,j)欲嚐試的下一步座標 7 if ((u == m)&&(v == p)) 8 { 成功找到出口，輸出路徑，可以停止 } 9 if ((!maze[u][v])&&(!mark[u][v])) 10 //(u,v)可以走，且不常走過 11 { mark[u][v] = 1; 12 dir = 下個可能嚐試的方向 13 push((i,j,dir)) 14 i=u; j=v, dir=N 15 } 16 } 17 }

25 3.6 老鼠走迷宮(續) 程式3-13路徑資料的結構化宣告 1 #define possible_direction 8
2 struct offset 3 { int dx,dy; 4 }; 5 enum directions {N,NE,E,SE,S,SW,W,NW}; 6 struct offset move[possible_direction]; 7 struct position 8 { int x,y; 9 directions dir; 10};

26 3.6 老鼠走迷宮 程式3-14老鼠走迷宮（上接程式3-13） 1 int m,p,top;
2 void push (struct position data) 3 { if (top == (m*p-1)) StackFull(); 4 else Stack[++top] = data; 5 } 6 struct position pop() 7 { if (top == -1) StackEmpty(); 8 else return Stack[top--]; 9 } 10 void path(int m, int p) 11 { struct position Stack [m*p]; 12 struct position step; 13 int i,j,u,v; 14 directions d; 15 step.x=step.y=1; step.dir=E; 16 push(step); 17 while (堆疊內有元素) 18 { step=pop(); 19 i=step.x ; j=step.y ; d=step.dir ;

27 3.6 老鼠走迷宮(續) 20 while (d<NW) 21 { // (i,j)處仍有可移動的選擇
22 u=i+move[d].dx ; v=j+move[d].dy; 23 if ((u==m) && (v==p)) 24 { // 輸出(u,v),(i,j)，再將stack內的所有元素 pop輸出，則構成一條由出口至入口的路徑 return; 27 } 28 if ((!maze[u][v]) && (!mask[u][v])) 29 { mask [u][v]=1; step.x=i ; step.y=j ; step.dir=d+1; push(step); i=u ; j=v ; d=N 33 } 34 else d++ ; 35 } 36 } //j輸出：”此迷宮無出路”之訊息 37 }

28 3.7　運算式的轉換和求值 在電腦中處理算術運算式 (arithmetic expression) ，需要堆疊的協助，在本節中即介紹兩者之間的關係。

29 算術運算式 在程式語言中，算術運算式經常被引用來計算希望的結果，例如下面的指定敘述 (assignment statement) ： X = A+(B-C)*D 等號右邊即為一算術運算式；一個算術運算式包括了運算子 (operator) 如：+, －, *, /, …等；和運算元 (operand) 如上式的A, B, C和D。除此之外，運算式的計算得依據運算子的優先順序 (priority) ，方得算出正確的結果。

30 3.7.1 算術運算式 數學上運算子的優先順序如表3-1所示 表3-1 運算子的優先順序（以C語言為例） 優先順序 運算子 1
算術運算式 數學上運算子的優先順序如表3-1所示 表3-1 運算子的優先順序（以C語言為例） 優先順序 運算子 1 負號、! (邏輯否定) 2 *、/、% 3 +、- 4 <、<=、>=、> 5 ==、!= 6 && 7 ||

31 算術運算式(續) 運算子依表3-1的優先順序（值愈小，優先順序愈高），將其對應的運算元加以計算；相同順序的運算子，則依由左至右的順序進行計算；若有括號內者應先計算（先內層後外層）。於是上式與下式是一樣的運算式： X=(A+((B-C)*D) 若沒有好的演算法，決定運算的先後順序，對電腦而言依然因難。在下一節中我們會介紹後序 (postfix) 運算表示式，利用之配合堆疊，即可順利地解決運算式求值 (evaluation) 的問題。

32 3.7.2後序運算式表示法 傳統的算術運算式將運算元放在運算子的中間，遂稱之為中序運算表示式 (infix notation) 。
而後序運算表示法 (postfix notation) 則將運算子放在對應運算元之後； 類似地，前序運算表示法 (prefix notation) 則將運算子放在對應運算元之前。 這裡的運算元指的是二元運算子 (binary operator) ；單元運算子 (unary operator) 如：負號、否定、…的並不在此討論。

33 3.7.2 後序運算式表示法(續) 範例3-10列出幾個運算式的不同表示法。 中序表示 後序表示 前序表示 B-C BC- -BC
3.7.2　後序運算式表示法(續) 範例3-10列出幾個運算式的不同表示法。 中序表示 後序表示 前序表示 B-C BC- -BC (B-C)*D BC-D* *-BCD A+(B-C)*D ABC-D*+ +A*-BCD 範例3-10

34 (A+((B-C)*D)) ABC-D*+ (A+((B-C)*D)) +A*-BCD
3.7.2　後序運算式表示法(續) 事實上只需加上適當的括號，我們可以輕易地轉換運算式的不同表示法，請見範例3-11 範例3-11 將中序運算式A+(B-C)*D加上適當的括號： (A+((B-C)*D)) 把運算元挪放到對應右括號的左邊，再去掉括號，即形成其後序運算式： (A+((B-C)*D)) ABC-D*+ 把運算元挪放到對應左括號的右邊，再去掉括號，即形成其前序運算式： (A+((B-C)*D)) +A*-BCD

35 第一次： A+X1*D （X1存放B-C的結果）
3.7.2　後序運算式表示法(續) 試想若編輯器中只存放中序運算式，而只會自左向右檢查式中的優先順序，則編輯器須多次解讀此中序運算式： A+(B-C)*D 第一次： A+X1*D （X1存放B-C的結果） 第二次： A+X2 （X2存放X1*D的結果） 第三次： X3 （X3存放A+X2的結果） 這種「遂次自左向右挑出順序最高者執行」方法的效率是很差的。

36 X1=B-C、X2=(B-C)*D、X3=A+(B-C)*D；
3.7.2　後序運算式表示法(續) 範例3-12 以A+(B-C)*D為例，令 X1=B-C、X2=(B-C)*D、X3=A+(B-C)*D； 則其後序運算式ABC-D*+的求值運算，只須運用堆疊S，並自左向右查看後序運算式一次即可完成，其中遇見運算元就直接push 入堆疊中，遇見運算子則pop堆疊兩次，取得的運算元即以該運算子做計算，結果再push 入堆疊中，直至後序運算式的每一元素皆看完為止。

37 3.7.2 後序運算式表示法(續) 演算法3-2後序運算式的求值運算 輸入：後序運算式e 輸出：計算出後序運算式e的值
3.7.2　後序運算式表示法(續) 演算法3-2後序運算式的求值運算 輸入：後序運算式e 輸出：計算出後序運算式e的值 1 n = passing(e, token); 2 for (i=0; i<n; i++) 3 if (token[i]為運算元) push(token[i]); 4 else 5 { pop出token[i]此運算子所需的運算元; 6 計算出token[i]此運算的值，令為x; 7 push(x); 8 }

38 3.7.3 中序運算式轉為後序運算式 我們先觀察下圖3-21的例子，不難發現兩者運算元出現的順序都一樣； 中序運算法：A+(B-C)*D
3.7.3　中序運算式轉為後序運算式 我們先觀察下圖3-21的例子，不難發現兩者運算元出現的順序都一樣； 中序運算法：A+(B-C)*D 後序運算式：ABC-D*+ 圖3-21 事實上在範例3-11中，我們已經知道中序轉後序、或中序轉前序的轉換過程，只須更動運算子的位置，運算元的順序並無任何更動。 至於計算順序的決定，我們可看出一些規則，如： B-C先運算乃因其在括號內； + 的位置在 * 後，乃因 + 的執行順序低於 * 由此可知在中序轉後序時，中序運算式中 * 雖比 + 後看到，但要先輸出，可見我們需要一個堆疊—存放後到但先出的運算子。原則上目前遇到的運算子x應先push入堆疊中，因為x能否輸出的決定得由x之後的運算子來決定；而x進入堆疊前，則可決定x之前的運算子是否可輸出了。

39 3.7.3 中序運算式轉為後序運算式(續) 演算法3-3中序運算式轉後序運算式 輸入：中序運算式e 輸出：對應輸入之後序運算法
3.7.3　中序運算式轉為後序運算式(續) 演算法3-3中序運算式轉後序運算式 輸入：中序運算式e 輸出：對應輸入之後序運算法 1 n = passing(e, token); 2 push(“#”); 3 for (i=0; i<n; i++) 4 { s = token(i); 5 if (s是一運算元) output(s); 6 else if (s == ”)”) 7 //將堆疊中第一個 ( 之前的運算子皆pop出並印出之 8 while ((x=pop())!=”(”) output(x); 9 else 10 { while (p(s)<=q(Stack[top]) 11 { x = pop(); output(x); 13 } 14 push(s); 15 } 16 } 17 while (Stack[top]!=”#”) 18 { x = pop(); 19 output(x); 20 }