數據結構基礎-棧和隊列

棧和隊列的邏輯結構與線性表相同，其特點在於運算有所限制(運算受限的線性表)，棧操作按照後進先出（LIFO）的規則，隊列按先進先出（FIFO）的規則。

棧

通過訪問它的一端來實現數據存儲與檢索的線性結構。

進行插入和刪除操作的一端稱為棧頂（Top），另一端稱為棧底（Bottom），不包含數據元素的棧，稱為空棧。

• 運算過程：

初始化棧->判斷棧是否為空->入棧（Push）->出棧（Pop）->讀取棧頂元素

初始化棧：創建一個空棧。

判斷棧是否為空：為空是返回true(真)，否則false（假）

入棧：將元素加入棧頂，並更新棧頂指針。

出棧：將棧頂元素刪除，並更新棧頂指針。

讀棧元素：返回棧頂元素的值，不更新指針。

• 存儲結構

順序存儲（順序棧）：

用一組地址連續的存儲單元依次存儲自棧頂到棧底的數據元素，同時指針指示棧頂元素的位置。這種存儲方式下，棧的空間容量是有限的，當元素入棧時，需要判斷是否棧滿，如棧滿，則不能入棧。

鏈式存儲（鏈棧）：

棧中元素的插入和刪除只在棧頂一端進行，因此不需要設置頭指針，鏈表的頭指針就是棧頂指針。

隊列

隊列是一種先進先出（FIFO）的線性表，它只允許在表的一端（隊尾）插入元素，在另一端（隊頭）刪除元素。

• 運算過程

初始化->判斷是否為空 ->入隊 ->出隊 -> 讀隊頭元素

初始化：創建一個空隊列（隊頭和隊尾指針在同一位置）。

判斷是否為空：為空是返回true(真)，否則false（假）

入隊：將元素加入隊尾（Rear），並更新隊尾指針。

出隊：將隊頭（Front）元素從隊列刪除，並更新隊頭指針。

讀隊頭元素：讀取隊頭元素的值，不更新隊頭指針。

• 存儲結構

順序存儲（順序隊列）：

用一組地址連續的存儲單元存儲隊列元素，隊列的操作是兩端進行的，因此設置隊頭指針和隊尾指針，分別指出隊頭和隊尾。

元素入隊時，修改隊尾指針。元素出隊時，修改隊頭指針。

由於順序隊列的存儲空間是預先設定的，因此隊尾指針會有一個上限值（下圖所示）。

元素入隊出隊以及指針修改過程

當隊尾指針達到上限時，只能通過修改隊尾指針來實現新元素的入隊。