課程內容#
佇列#
- FIFO（First In First Out）、LILO。類似排隊，區分先來後到
- 也是順序結構，需要連續存儲空間（不過也可以用鏈表實現）
結構定義#
- 需要連續的存儲空間
- 容量
- 隊首、隊尾
- + 元素個數：用來判斷佇列是否已滿，方便循環佇列解決假溢出問題
- 數據類型
結構操作#
- 出隊
- head - 1
- count - 1
- 入隊
- tail + 1
- count + 1
- ❗假溢出
- 不能存元素了
- 實際上可能還沒有滿：出隊操作使佇列頭部有空位
- 解決方案：循環佇列
- tail 走到頭了再回到佇列前面
- 使用取餘運算確定位置：(tail + 1) % length
- 擴容：遇到真溢出時，詳見代碼演示
堆疊#
- FILO（First In Last Out）、LIFO。類比裝書的箱子，一頭是堵死的
- 也是順序結構
結構定義#
- 需要連續的存儲空間（有大小限制）
- 容量
- 堆疊頂指針【top】：對於空堆疊，top = -1，為 0 可不合適
- 數據類型
結構操作#
- 出堆疊：top - 1 // 需要判空
- 入堆疊：top + 1，存值 // 需要判滿
應用#
-
-
DFS 和 BFS 詳見《面試筆試演算法上》 - 6 搜索專題
-
單調堆疊、單調佇列自行學習
隨堂練習#
LC-20： 有效的括號#
- 關鍵在於思維：大問題轉小問題
- 問題簡化成只有一種括號，怎麼做？可以不使用堆疊完成嗎？
- 思路：只需要記錄左括號數量和右括號數量
- 在任意位置，左數 >= 右數
- 在最後位置，左數 == 右數
-
- 其實可以只用一個數 top 記錄，遇到左括號 + 1，遇到右括號 - 1
- 在任意位置，top >= 0
- 在最後位置，top == 0
- 這個 + 1、-1 操作，可以聯想到堆疊的入堆疊、出堆疊嗎？
- 一次括號匹配相當於入堆疊出堆疊一次
- 括號裡的括號相當於完全包含關係
- 也有分治思想
- 堆疊：可以處理具有完全包含關係的問題
- 代碼
- 可參考《面試筆試演算法上》- 5 STL “容器” 的使用與練習 - HZOJ-378 講解
- C 語言中，則先實現數據結構 - 堆疊，再用堆疊解決問題
代碼演示#
佇列#
部分結果
-
-
定義 tail 有兩種方式
- ①指向最後一個元素的地址
- ②指向最後一個元素的下一個地址（本代碼的選擇）
-
使用循環佇列，已經不存在假溢出的現象
-
但對於真溢出怎麼辦呢？👇
+ 擴容#
針對循環佇列的擴容
-
3 種動態開辟內存的方法【malloc、calloc、realloc】，使用哪一種？
-
🆒malloc、calloc 都可以，但是
-
❗ 之前使用的 realloc 不好使了
- 循環佇列的尾可能不在頭的後面，而是尾和頭重合了
- 舉例：當佇列已滿時，head、tail（這裡 tail 定義為尾部元素的後一位）在如下位置，此時擴容一倍，擴容後佇列的 push 和 pop 會怎麼樣呢？
-
- 此時從 head→tail 之間插入了很多空值，因為 realloc 是把值按原順序搬過去，而擴容部分還沒有值
- 那麼，不管是從 head 到 tail 出隊 [中間夾雜了很多空值]，還是從 tail 入隊 [tail 位置存在未出隊的元素]，都存在問題！
-
而用 malloc 開辟空間後，把原佇列從 head 到 tail 按順序遷移，即手動將 head 調整為索引 0，如下，關鍵在於頭尾指針的調整！
-
-
代碼
-
- 關鍵在於調整指針為正常順序
-
堆疊#
-
-
-
-
第 72 行，pop 操作只需要 top - 1 即可
-
第 109 行，printf 裡若有待執行命令而不是簡單的取值時，需注意順序
- 其調用順序，與系統堆疊的設計有關
- 參考printf 函數參數從右至左壓堆疊-CSDN；printf 壓堆疊出堆疊-CSDN
- 這種從右至左的方式不會隨著編譯器、機器的不同而不同
- 涉及底層，先不深究
- 【結論】 printf 的參數有待執行的命令時，盡量分開寫
-
第 106 行，在出堆疊前需先判空，否則 top = -1 會帶來問題
- 首次出堆疊結果，已安全
-
-
❓應該在調用 empty 和 top 前，確定堆疊是否存在，而不在函數裡寫判 NULL 操作
- 而其他操作基本都有判 NULL 操作，主要和方便程序拆分有關，不用細究
- 都寫判 NULL 操作也可
附加知識點#
- 系統堆疊
- 也是堆疊，大小：8MB
- 遞歸時，使用的就是系統堆疊
