Queue & stack

Size: px

Start display at page:

Download "Queue & stack"

涎明溥
6 years ago
Views:

1 STACKS & QUEUES Prof. Michael Tsai 2012/3/6

2 2 Stack Stack 是蝦密碗糕? 一串有順序的列表又叫 Ordered List 有什麼特別的地方? 頂 (Top) 底 (Bottom) 永遠從頂部拿與放拿 : Pop 放 : Push 看一個例子所以先放進去的, 會?? 出來?

3 3 Stack 所以是一個先進後出 (First-In-Last-Out, FILO) 的資料結構或是後進先出 (Last-In-First-Out, LIFO) 那麼, 支援那些動作呢? 各動作又需要什麼參數? 請同學們列舉 : 做一個 Stack 放 (Push) 拿 (Pop) 是不是空的? 是不是滿了? 最上面的元素 ( 不 pop 出來 ) 總共有幾個元素

4 4 例子一 : 系統堆疊被程式拿來儲存呼叫 function 的相關資訊放什麼? 叫做 activation record 或 stack frame return address: 呼叫 function 的下一個指令應該去的地方 previous frame pointer: 指到前一個 stack frame 在 stack 裡面的位置 ( 底 ) local variables 看一個例子. 適不適用 recursive call? Stack overflow? sp fp Previous frame pointer Return address Local variables Previous frame pointer Return address

5 5 怎麼 implement 一個 stack? 請同學上來舉例說明先試試看使用大家都會的 array 除了 array 以外, 還需要哪些東西? 紀錄頂部的 index 怎麼 implement 這些 operations? Push Pop 是不是空? 是不是滿? 最上面的元素 ( 不 pop 出來 ) 總共有幾個元素

6 6 Code struct ArrayStack { int top; int capacity; int *array; } struct ArrayStack *CreateStack() { struct ArrayStack *S = malloc(sizeof(struct ArrayStack)); if (!S) return NULL; S->capacity=4; S->top=-1; S->array=(int*)malloc(S->capacity*sizeof(int)) if (!S->array) return NULL; return S; }

7 7 Code void Push(struct ArrayStack*S, int data) { if (IsFullStack(S)) printf( Stack OverFlow ); else S->array[++S->top]=data; } int Pop(struct ArrayStack*S) { if (IsEmptyStack(S)) { printf( Stack is Empty ); return 0; } else return (S->array[S->top--]); }

8 8 滿了怎麼辦? array=(int*)malloc(s->capacity*sizeof(int)); 如果裡面有超過 capacity 個元素, 就滿了. T_T 如何把 stack 變大? 複習 : realloc 做什麼用的? realloc 做了什麼? ( 假設原本大小 n, 新的大小 m) 1. 在記憶體某個地方開一塊新的記憶體, 大小為 m( 比較大 ) 2. 把放在舊的記憶體的東西搬到新的記憶體去 ( 需花 n 的時間 ) 3. 然後把新的記憶體位址回傳給你 realloc 相關決定 : 要 realloc 成多大? realloc 完畢有沒有什麼要改的地方?

9 來一點複雜度分析方法一 : 當滿了以後, 每次 push 就把 array 大小增加 1, 每次 pop 就把 array 大小減少 1 小名詞 : Amortized Analysis 把 n 個動作的執行時間一起考慮, 看平均起來它們總共要花多少時間執行及一個動作平均要花多少時間, 這樣的分析方法叫做 Amortized Analysis ( 下學期 algorithm 會教到 )

9 9 來一點複雜度分析方法一 : 當滿了以後, 每次 push 就把 array 大小增加 1, 每次 pop 就把 array 大小減少 1 小名詞 : Amortized Analysis 把 n 個動作的執行時間一起考慮, 看平均起來它們總共要花多少時間執行及一個動作平均要花多少時間, 這樣的分析方法叫做 Amortized Analysis ( 下學期 algorithm 會教到 ) 問題 : push n 次的時間複雜度為多少? ( 假設一開始是空的 ) 假設 : Push 一個 element 是 O(1),Allocate 一個 element 是 O(1), 移動一個 element 是 O(1) 第一次 Push ( 花 constant 時間 ) 第二次 Push ( 花 constant 時間 + 花 1 的時間把舊記憶體的東西搬到新記憶體 ) 第三次 Push ( 花 constant 時間 + 花 2 的時間把舊記憶體的東西搬到新記憶體 ) 第四次 Push ( 花 constant 時間 + 花 3 的時間把舊記憶體的東西搬到新記憶體 ) 第 n 次 Push ( 花 constant 時間 + 花 n-1 的時間把舊記憶體的東西搬到新記憶體 ) (n-1)=(n-1)(1+(n-1))/2=o(n 2 )

10 10 來一點複雜度分析方法二 : 如果每次都 realloc 成原本的兩倍大 capacity 存現在的 stack 大小問題 : push n 次的時間複雜度為多少? 第一次 Push ( 花 constant 時間 ) 第二次 Push ( 花 constant 時間 + 花 1 的時間把舊記憶體的東西搬到新記憶體 ) 第三次 Push ( 花 constant 時間 + 花 2 的時間把舊記憶體的東西搬到新記憶體 ) 第四次 Push ( 花 constant 時間 ) 第五次 Push ( 花 constant 時間 + 花 4 的時間把舊記憶體的東西搬到新記憶體 ) 第九次 Push ( 花 constant 時間 + 花 8 的時間把舊記憶體的東西搬到新記憶體 ) 做了 n 次 push 以後, 花多少時間?

11 來一點複雜度分析 Constant time 的部分共 n ( 因為有 n 個 O(1)) 剩下把舊的記憶體裡面的資料搬到新的記憶體裡面去的時間 1 + 2 + 4 + + 2 log 2 n 1 + 2 + 4 + + 2 log 2 n = 1 2log 2 n 1 2 1 所以總共 n 個

11 11 來一點複雜度分析 Constant time 的部分共 n ( 因為有 n 個 O(1)) 剩下把舊的記憶體裡面的資料搬到新的記憶體裡面去的時間 log 2 n log 2 n = 1 2log 2 n 所以總共 n 個 push 花 O(n) 的時間! 平均起來一個 push 花 O(1) 的時間! = O(n) 詳細的程式碼請看課本 Ch4 P77 & P79 (Karumanchi) < 動腦時間 : 回家作業 > 如果每次增加為原本 capacity 的 c 倍, c>1, 那麼複雜度會有變化嗎? 為什麼? 答案 : 不會

12 12 Queue Queue 是蝦密咚咚? 也是 Ordered List 5 4 尾 (Rear) 和 Stack 有什麼不一樣? 1 0 頭 (Front) 從尾 (Rear) 放, 從頭 (Front) 拿拿 : Delete, or DeQueue 放 : Add, or EnQueue 所以先放進去的, 會?? 出來?

13 13 Queue 先放進去的, 會先出來所以是 First-In-First-Out (FIFO) 那麼, 支援那些動作呢? 各動作又需要什麼參數? 請同學們列舉 : 做一個 Queue 放 (EnQueue) 拿 (DeQueue) 是不是空的? 是不是滿了? ( 其他的 : 最前面的元素是什麼, 總共有幾個元素 )

14 14 舉一個例子 Job scheduling 如果沒有使用 priority 的概念的話先來的 job 就先做 FIFO 的概念問題 : 程式要求作業系統做一個 job, 作業系統要照來的順序決定誰先使用資源. 作法 : 程式發出要求的時候, 就放入 queue 中資源空出來了, 就從 queue 拿出一個 job 來做結果 : FIFO < 動腦時間 > 如果放入一個 stack 會怎麼樣?

15 15 那麼, 怎麼 implement queue 呢? 一樣使用 array 要記得頭跟尾的在 array 裡面的位置 (index) 但是這次有點問題滿了! 但是前面的空間沒有用到! 怎麼解決? 頭尾

16 16 解決方式 : 頭尾相接頭課本叫它 Circular Array Implementation 這樣就可以保證 queue 儲存的 element 數目最多可以跟 array 大小一樣什麼時候是空? 什麼時候是滿? ( 能不能分辨空和滿?) 尾

17 17 那麼, 如果要使用動態大小呢? 一樣使用 realloc 來要到一塊更大的記憶體然後還有什麼工作要做? realloc 之後的樣子 : 看起來不太對尾頭請一位同學上來講解怎麼修正 ( 答案請看 Karumanchi 課本 P101 的 ReSizeQueue() 怎麼寫的 )

18 18 接下來講一些應用 : 計算機問題迷宮問題 ( 回家自己看 )

19 19 應用一 : 計算機不是普通的計算機題目 : 如果打入一串如 1+2*3-5/(4+5)/5 的算式, 請寫一個演算法來算出這串算式的結果. 怎麼寫呢? 好複雜 T_T

20 20 先來看看算式長什麼樣子 1+2*3-5/(4+5)/5 裡面有 : Operand 1, 2, 3, 5, 4, 5, etc. Operator + * - / 括號 (,) 特色 1: 左到右 (left-to-right associativity) 特色 2: 一般這種寫法叫做 infix (operator 夾在 operand 中間 ) 先後順序要 operator 去比大小例如乘除是大, 加減是小, 那麼就先乘除後加減

21 21 別種寫法 : postfix 把 operator 放到兩個 operands 的後面例如 2+3* * + a*b+5? (1+2)*7? a*b/c? (a/(b-c+d))*(e-a)*c? a/b-c+d*? e-a*c?

22 22 Postfix 有什麼好處? 沒有括號用 stack 幫忙就可以很容易地算出結果! 例子 : 6 2 / * + 從左邊讀過去讀到 6, 放 6 進 stack (stack: 6) 讀到 2, 放 2 進 stack (stack: 6 2) 讀到 /, 取兩個 operands (6 和 2), 算 6/2, 然後答案放回去 stack (stack: 3) 讀到 3, 放 3 進 stack (stack: 3 3) 讀到 -, 取兩個 operands(3 和 3), 算 3-3, 然後答案放回去 stack (stack: 0) 依此類推.( 請同學上來繼續完成 )

23 23 剩下來的小問題 : infix to postfix 小問題 : 怎麼把 infix expression 轉成 postfix expression? 第一種方法 : ( 適合紙上談兵 ) 1. 把整個 expression 2. 把所有的 operator 都移到 operand 的後面去, 方便去除所有括號 3. 去除所有括號但是實作上要怎麼做呢? ( 不希望做兩次 )

24 24 又是一個可以利用 stack 解決的問題方法 : 1. 從左至右讀取 expression 2. 碰到 operand 就直接輸出 3. 碰到 operator 時比較 stack 頂上的 operator 和目前讀到的 operator 哪一個比較大 (precedence) 如果目前讀到的 operator 比較大, 就把 operator 放到 stack 裡如果一樣大或者現在讀到的 operator 比較小, 就一直把 stack 裡面的 operator 拿出來印出來, 一直到 stack 是空的或者現在的 operator 比 stack 頂的 operator 大為什麼可以這樣做? 裡面括號需要先印出, 但是卻是後讀到比較外面的先用 stack 記起來, FILO, 由內而外

25 25 例子一請一位同學來解說怎麼把 a+b*c 利用前述方法轉換成 postfix 那麼, 如果碰到括號怎麼辦?

26 26 括號括號內的有優先性因此當碰到右括號的時候, 就立刻把 stack 中的東西一直拿出來直到碰到左括號為止舉例 : a*(b+c) 輸出的內容, stack 內容 ( 最右邊為 top) a a, * a, *( ab, *( ab, *(+ abc, *(+ abc+*

27 27 還有一些小問題小問題 1: 左括號的大小到底是多少? 碰到左括號一定要放進去 stack 此時要是最大的左括號的下一個 operator 一定要可以放進去此時要是最小的結論 : 左括號有兩種大小在 stack 內的時候優先性為最小在 stack 內的時候優先性為最大其他 operator 的優先性則不管在 stack 內外都一樣

28 28 還有一些小問題 Q: 如何確保 stack 空的時候, 第一次碰到的 operator 可放進去? A: 在 stack 底部放入一個虛擬 operator 帶有最低的優先性 Q: 如何確保讀到 expression 最後的時候, 可以把 stack 裡面未取出的 operator 都拿出來? A: 字串最後可以加一個優先性最低的虛擬 operator

29 29 例題 a+(b*c/(d-f)+e) 用白板解說 ( 請同學? :P) 答案 : abc*df-/e++

30 30 最後來一個有趣的迷宮問題吧回家自己讀迷宮 : 0 是路, 1 是牆壁. 每一部可以往上下左右和四個斜角方向走一步. 問題 : 怎麼找出一條路從 (0,0) 走到 (7,7)? ( 不一定要最短 ) 提示 : 跟 stack 是朋友

31 31 走迷宮的時候, 人要怎麼走? 最重要的時候, 是碰到岔路的時候先記起來, 選其中一條走走看如果碰壁了 ( 一直沒有走到終點 ), 就退回最後一次碰到的岔路, 換另外一條岔路關鍵字 : 最後一次碰到的岔路 ( 不是最先碰到的 ) 所以是先進後出使用 stack 關鍵字 : 換另外一條岔路要記得上一次走過哪一條路了

32 32 一些細節 Q: 那麼, stack 裡面要存什麼呢? A: 岔路的地方的座標, 也就是 (row, col) 試過那些岔路了 ( 試到八個方向的哪個方向了 ) Q: 要怎麼預防繞圈圈? ( 永遠出不來 ) A: 標示所有已經走過的地方, 走過就不用再走了 < 注意 > 這是因為不用找最短的路

33 33 讓我們來寫 algorithm 把 (row_start, col_start, 第一個方向 ) 放入 stack while(stack 不是空的 ) { 從 stack 拿出一組岔路點 (row, col, dir) while( 還有別的 dir 還沒試 ) { 將 (row, col) 往 dir 方向移動, 得到 (row_n, col_n, dir). 如果 (row_n, col_n) 就是終點, 則結束如果 (row_n, col_n) 不是牆壁且沒有來過 { 標示 (row_n, col_n) 來過了把 (row, col, dir 的下一個方向 ) 放入 stack row=row_n; col=col_n; dir= 第一個方向 ; } } }

34 34 Today s Reading Assignments 1. Karumanchi ( 如果有空的話自己閱讀 4.7 or 5.7 上的問題, 看看自己觀念是否都懂了!) 2. 本份投影片上沒有講的部分

stack_and_queue

stack_and_queue Stacks and Queues Prof. Michael Tsai 2017/02/21 Stack Stack represents an ordered and linear list Stack of plates Taken from and placed onto the top Pop: take an element Push: place an element Example