第三章__堆疊和佇列
3.1、堆疊和佇列的定義和特點
3.1.1、堆疊的定義和特點
定義：
堆疊是是一種特殊的線性表，是限定在表尾進行插入或洗掉操作的線性表，又稱為后進先出的線性表，簡稱LIFO
相關概念：
- 表尾（即an端）稱為堆疊頂Top；表頭（即a1端）稱為堆疊底Base
- 插入元素到堆疊頂（即表尾）稱為入堆疊
- 從堆疊頂（即表尾）洗掉最后一個元素的操作，稱為出堆疊
入堆疊的操作示意圖
出堆疊示意圖
思考：a、b、c3個元素，入堆疊順序是a、b、c，則他們的出堆疊順序有幾種可能：
堆疊的相關概念：
- 定義：限定只能在表的一端進行插入和洗掉運算的線性表（只能在堆疊頂操作）
- 邏輯結構： 與同線性表相同，仍為一對一關系
- 存盤結構：用順序堆疊或鏈堆疊存盤均可，但以順序堆疊更常見
- 運算規則：只能在堆疊頂運算，且訪問結點時依照后進先出（LIFO）的原則
- 實作方式：關鍵是撰寫入堆疊和出堆疊函式，具體實作依順序或鏈堆疊的不同而不同，
堆疊與一般線性表的不同：
堆疊與一般線性表的區別：僅在于運算規則不同
3.1.2、佇列的定義和特點
- 佇列是一種先進先出（FIFO）的線性表，在表的一端插入（表尾），在另一端（表頭）洗掉
佇列相關概念：
- 定義：只能在表的一端進行插入運算，在表的另一端進行洗掉運算的線性表
- 邏輯結構：與同線性表相同，仍為一對一關系
- 存盤結構：順序隊或鏈隊，以回圈順序佇列更常見
- 運算規則：只能在隊首和隊尾運算，且訪問結點時依照先進先出的原則，
- 實作方式：關鍵時掌握入隊和出隊操作，具體實作依順序隊或鏈隊的不同而不同
3.2、案例引入
3.2.1、案例一：進制轉換
十進制整數N向其它進制數d（二、八、十六）的轉換是計算機實作計算的基本問題
- 轉換法則：除以d倒取余
- 原理為：n = (n div d) * d + n mod d ,其中div為整除運算，mod為求余運算
例：把十進制數1348= 轉換成八進制數為2504，
| N | N div 8 | N mod 8 |
|---|---|---|
| 1348 | 168 | 4 |
| 168 | 21 | 0 |
| 21 | 2 | 5 |
| 2 | 0 | 2 |
3.2.2、案例二：括號匹配的檢驗
- 假設運算式中允許包含兩種括號：圓括號和方括號
- 其嵌套的順序隨意，即：
- ([] ()) 或 [ ( [] [] ) ]為正確格式
- [ ( ] ) 或 （ [ () ) 或 ( ( ) ])為錯誤格式
3.2.3、案例三：運算式求值
運算式求值是程式設計語言編譯中的一個基本問題，在實作時也需要運用堆疊，
實作：我們會使用演算法——算符優先演算法（運算子優先級確定運算順序的運算式求值演算法）
- 運算式組成
- 運算元：常數、變數
- 運算子：算術運算子、關系運算子和邏輯運算子
- 界限符：左右括弧和運算式結束符
- 任何一個算術運算式都是由運算元（常數、變數）、算術運算子（+、-、*、/）和界限符（括號、運算式結束符 ’#‘、虛設的運算式起始符'#'）組成，
3.2.4、案例四：舞伴問題
假設在舞會上，男士和女士各自排成一隊，舞會開始時，依次從男隊和女隊的隊頭個出一人配成舞伴，如果兩隊初始人數不同，則較長的那一隊未配對者等待下一輪舞曲，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/514175.html
標籤：其他
上一篇：leetcode 220. Contains Duplicate III 存在重復元素 III(困難)
下一篇：leet Code [34. Find First and Last Position of Element in Sorted Array]