stack_and_queue

Size: px

Start display at page:

Download "stack_and_queue"

厄孓秋
6 years ago
Views:

1 Stacks and Queues Prof. Michael Tsai 2017/02/21

2 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 à First in,???? Out A: Last Therefore, Stack is a First-In-Last-Out (FILO) or Last-In-First-Out (LIFO) data structure Top Bottom

3 Stack Operations So, what operations can be supported by a stack? What parameters do they need? Initialize a stack Push an element Pop an element Is it empty? Is it full? 3

4 Stack Usage Example: System Stack A program uses a stack to store information about the calling function. What are stored? Activation record or stack frame return address: where the calling function s next instruction is located. previous frame pointer: the location of the last stack frame (in the stack) local variables Example Recursive call? Stack overflow? sp fp Previous frame pointer Return address Local variables Previous frame pointer Return address 4

5 Stack Usage Example: Is it Palindrome? If a word looks the same forward and backward. Examples: Noon, civic, racecar, madam Was it a cat I saw Q: how do we use a stack to check if a string is a palindrome?

7 Stack Usage Example: Balanced parentheses Q: how do we use a stack to check if a string has balanced parentheses (each ( is matched with a ) in the string.)? Think about it!

9 How to implement a stack? First version: using array What else do we need except the array to store the data? A variable to record the index of the top element. How to implement these operations? Push Pop Empty? Full? Number of current elements? 9

10 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; 10

11 int IsEmptyStack(struct ArrayStack *S) { return (S->top==-1); } int IsFullStack(struct ArrayStack *S) { } return (S->top==S->capacity-1); 11

12 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--]); } 12

13 What if it is full? array=(int*)malloc(s->capacity*sizeof(int)); If we have more than capacity elements, then it is full! How do we enlarge the stack? Hint: realloc() to the rescue! realloc() can: (assume original size = n, new size = m) 1. Allocate a new chunk of memory, sized m (larger) 2. Move the content of the memory at the original location to the new location 3. Give you the address of the new memory Q: How large should you realloc()? 13

14 Monitor Stack 14

15 Queue What is a queue? Queue is also an ordered and linear list But, Add from the rear, take from the Front Delete, or DeQueue: take an element Add, or EnQueue: add an element First-In-????-Out? A: First Out Rear 0 Front 15

16 Queue So, what operations can be supported by a queue? What parameters do they need? Initialize a queue Add an element (EnQueue) Take an element (DeQueue) Is it empty? Is it full? 16

17 How do we implement a queue? Let s use array again Record front and back of the queue in the array (indices) But, here comes a problem: Front Back The queue is full! But space is wasted. How to solve this problem? 17

18 Solution: circular array Front Back The end of the array is assumed connected to the start of the array This makes sure that the number of elements which can be stored by a queue is the same as the size of the array When is the queue empty? When is the queue full? Can we tell them apart?! 18

19 What if it is actually full? We use realloc() to obtain a large chunk of memory. Then, other work to be done? It does not look right after realloc(). realloc from size to 2*size 0 size-1 2*size Back Front How do we fix this? 19

20 What s Next? Before next lecture (week 3), read the assigned sections in the textbook. (there will be related in-class activities)

21 Applications of Stack & Queue (Reading assignment!)

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

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

24 先來看看算式長什麼樣子 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 去比大小例如乘除是大, 加減是小, 那麼就先乘除後加減 24

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

26 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) 依此類推.( 請同學上來繼續完成 J) 26

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

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

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

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

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

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

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

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

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

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

37 讓我們來寫 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= 第一個方向 ; } } } 37

Queue & stack

Queue & stack STACKS & QUEUES Prof. Michael Tsai 2012/3/6 2 Stack Stack 是蝦密碗糕? 一串有順序的列表又叫 Ordered List 有什麼特別的地方? 53 4 1 0 頂 (Top) 底 (Bottom) 永遠從頂部拿與放拿 : Pop 放 : Push 看一個例子所以先放進去的, 會?? 出來? 3 Stack 所以是一個先進後出 (First-In-Last-Out,