第三章棧與隊列-資料下載頁

【導讀】棧的數組表示可能棧滿。棧的單鏈表表示無棧滿問題。出棧在表頭進行刪除操作。不能，3出棧時，說明2和1都在棧里，而且2必須。則棧大小至少為多少？一個表達式由操作數、操作符。優先級高的先計算；優先級相同的自左向右計算；當使用括號時從最內層括號開始計算。前綴和中綴表達式求值需要兩個棧；后綴表達。式求值只需一個棧，相對簡單些。順序掃描后綴表達式每一項。若該項是操作數，則進棧。若是雙目運算符，則連續出棧兩個操作數X和Y，并將。當表達式的所有項都掃描并處理完后，棧頂存放的。就是最后的計算結果。

　　

【正文】 6 p5 p4 p3 p10 p9 尋找凸包 ? Grahamscan的基本思想 p0 p2 p1 p7 p8 p6 p5 p4 p3 p10 p9 尋找凸包 ? Grahamscan的基本思想 p0 p2 p1 p7 p6 p8 p5 p4 p3 p10 p9 尋找凸包 ? Grahamscan的基本思想 p0 p2 p1 p7 p6 p8 p5 p4 p3 p10 p9 尋找凸包 ? Grahamscan的基本思想 p0 p2 p1 p7 p6 p8 p5 p4 p3 p10 p9 尋找凸包 ? Grahamscan的基本思想 p0 p2 p1 p7 p6 p8 p5 p4 p3 p10 p9 尋找凸包 ? Grahamscan的基本思想 47 Grahamscan(Q) 1. 求 Q中 y坐標值最小的點 p0； 2. 按照與 p0極角 (逆時針方向 )大小排序 Q中其余點， 結果為 p1, p2, …, p m； 3. Push(p0, S)。 Push(p1, S)。 Push(p2, S)。 4. FOR i=3 TO m DO 5. While Nexttotop(S)、 Top(S)和 pi形成非左移動 Do 6. Pop(S)。 7. Push(pi, S)。 8. Rerurn S； O(nlogn) O(n) O(1) O(n) 總時間復雜度 O(nlogn) 循環為什么是 O(n) 最多 n次入棧， 那么出棧也是最多 n次 隊列 ? 定義 ? 隊列是只允許在一端刪除，在另一端插入的線性表 ? 允許刪除的一端叫做隊頭 (front)，允許插入的一端叫做隊尾 (rear)。 ? 特點：先進先出 ? 隊列的操作 ? 入隊 EnQueue() ? 出隊 DeQueue() ? 判斷是否為空 isEmpty() ? 隊列滿 isFull() 48 隊列 ? 隊列的數組表示 ? 入隊：在 rear 位置加入數據， rear = rear + 1 ? 出隊：在 front位置取出數據， front = front + 1 49 A B C D E F front rear 空隊列 A入隊 B、 C入隊 A出隊 B出隊 D、 E、 F入隊 ear rear rear front front 隊列 ? 隊列的數組表示 (循環隊列 ) ? 入隊：在 rear 處加入數據， rear=(rear+1)%SIZE ? 出隊：在 front處取出數據， front=(front+1)%SIZE ? 隊滿： (rear+1)%SIZE == front ? 隊空： rear == front 50 1 2 3 4 5 6 7 0 D E F G H A B C 空隊列 A入隊 B、 C、 D入隊 A、 B出隊 E、 F、 G、 H、 I入隊 rear front rear rear front I 隊列 ? 隊列的單鏈表表示 ? 隊列的數組表示可能隊列滿 ? 隊列的單鏈表表示無隊列滿問題 ? 入隊在表尾進行插入操作 ? 出隊在表頭進行刪除操作 51 A B C null front rear 打印二項展開式 (a+b)i 的系數 ? 楊輝三角形 52 1 1 i = 1 1 2 1 2 1 3 3 1 3 1 4 6 4 1 4 1 5 10 10 5 1 5 1 6 15 20 15 6 1 6 (a+b)1=a+b (a+b)2=a2+2ab+b2 (a+b)3=a3+3a2b+3ab2+b3 打印二項展開式 (a+b)i 的系數 ? 第 i行與第 i+1行關系 53 i = 2 i = 3 i = 4 0 1 3 3 1 0 1 4 6 4 1 0 1 2 1 0 0 1 1 0 打印二項展開式 (a+b)i 的系數 54 0 0 1 2 1 0 1 1 1 3 3 1 0 出隊列時與前一個出隊列的數相加，結果入隊列 0作為被加數時， 0入隊列，作為分隔符 隊列的應用：電路布線 ? 找最短路徑 ? 網格方式布線，布線不能有重疊，轉彎用直角 55 (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3) 起點 終點 已布線 隊列的應用：電路布線 ? 找最短路徑 56 (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3) 起點 終點 已布線 (1,1) (0,1) (1,0) (2,1) (2,0) (3,1) (3,0) (3,2) (3,3) front rear 已訪問 rear rear rear rear rear rear rear front front front front front front front front front null (1,1) (1,1) (1,1) (1,0) (2,1) (2,0) (3,1) (3,2)