數據結構課件第4章棧與隊列匯報人:目錄01棧的定義與特性02棧的基本操作03隊列的定義與特性04隊列的基本操作05棧與隊列的應用場景棧的定義與特性PARTONE棧的概念棧頂與棧底后進先出原則棧遵循后進先出（LIFO）原則，最后進入的數據項將最先被移除。棧有明確的棧頂和棧底，數據項的添加和移除僅發生在棧頂。棧的限制性操作棧的操作僅限于棧頂，包括入棧（push）和出棧（pop），保證了數據的有序性。棧的特性棧的操作遵循后進先出原則，最后入棧的元素會最先出棧。后進先出（LIFO）棧只允許在一端進行插入（push）和刪除（pop）操作，保證了數據的有序性。限制性訪問棧的抽象數據類型創建一個空棧，用于存放數據元素，初始狀態棧頂指針指向-1。棧的初始化向棧中添加元素，新元素被放置在棧頂，并更新棧頂指針。棧的入棧操作從棧中移除棧頂元素，并返回該元素，同時更新棧頂指針。棧的出棧操作查看棧頂元素而不移除它，常用于獲取棧頂數據進行處理。棧的查詢操作棧的存儲結構棧的順序存儲結構使用連續的內存空間來存儲數據元素，如數組實現的棧。順序存儲結構01鏈式存儲結構通過指針將分散的內存塊連接起來，實現棧的動態存儲，如鏈表實現的棧。鏈式存儲結構02棧的基本操作PARTTWO入棧操作入棧是將一個元素添加到棧頂的過程，類似于在一堆書上放上另一本書。入棧的定義通過修改棧頂指針來實現入棧，通常棧頂指針向上移動一位，然后將新元素放到棧頂位置。入棧的實現棧未滿時，新元素才能入棧；若棧已滿，則無法進行入棧操作。入棧的條件出棧操作定義與重要性出棧是棧操作的核心之一，它允許從棧頂移除元素，保持后進先出的順序。操作步驟出棧錯誤處理如果嘗試從空棧中出棧，應返回錯誤或異常，以避免程序崩潰。出棧操作涉及檢查棧是否為空，然后移除棧頂元素，并更新棧頂指針。出棧的實例例如，在函數調用中，返回地址的出棧操作確保了正確的執行流程。查看棧頂元素棧頂元素是棧中最后一個被添加的元素，位于棧的最頂端。棧頂元素的定義在編程中，查看棧頂元素常用于檢查數據結構的狀態，例如在解析表達式時確定下一個操作符。查看棧頂元素的應用查看棧頂元素不移除它，僅用于獲取信息，如在函數調用中獲取當前活動記錄。查看棧頂元素的操作棧的其他操作遍歷棧中的元素，通常需要借助輔助數據結構，如隊列，以實現非破壞性遍歷。棧的遍歷清空棧的操作通常涉及將棧中的所有元素彈出，直到棧為空。棧的清空復制一個棧，可以通過創建一個新棧，然后依次將原棧中的元素壓入新棧中來實現。棧的復制比較兩個棧是否相等，需要逐個比較棧頂到棧底的元素是否完全相同。棧的比較01020304隊列的定義與特性PARTTHREE隊列的概念隊列遵循FIFO原則，先入隊的元素會先出隊，類似于現實生活中的排隊等候。先進先出原則01、隊列主要有兩種操作：入隊（enqueue）和出隊（dequeue），分別對應添加和移除元素。隊列的操作02、隊列的特性隊列遵循FIFO原則，即先入隊的元素先出隊，類似于現實生活中的排隊等候。先進先出原則01隊列的大小不是固定的，它可以動態地根據入隊和出隊操作進行調整。動態變化的大小02隊列只允許在兩端進行操作，一端為隊尾（入隊），另一端為隊首（出隊）。限制性訪問03當隊列為空時，無法進行出隊操作，而當隊列滿時，無法進行入隊操作。無元素時的特殊狀態04隊列的抽象數據類型隊列的操作隊列的操作包括入隊（enqueue）、出隊（dequeue）、查看隊首（front）和檢查隊列是否為空（isEmpty）。隊列的屬性隊列具有先進先出（FIFO）的特性，即最早進入隊列的元素將最先被移除。隊列的存儲結構隊列的順序存儲結構通常使用數組實現，通過頭尾指針來標識隊列的前端和后端。順序存儲結構鏈式存儲結構使用鏈表來實現隊列，每個節點包含數據和指向下一個節點的指針。鏈式存儲結構循環隊列是一種特殊的順序隊列，當數組末尾被訪問后，指針會回到數組的開始位置，形成循環。循環隊列雙端隊列允許在隊列的兩端進行插入和刪除操作，是一種更為靈活的隊列結構。雙端隊列隊列的基本操作PARTFOUR入隊操作01定義入隊操作入隊操作是在隊列的尾部添加一個元素，通常稱為enqueue。02入隊的條件隊列未滿時，新元素可以被加入隊列尾部，否則需等待或返回錯誤。03入隊的步驟首先檢查隊列是否已滿，若未滿則將新元素置于尾指針指向的位置，并更新尾指針。出隊操作出隊操作首先檢查隊列是否為空，然后移除隊列前端的元素，并返回該元素。移除隊首元素在移除隊首元素后，需要更新隊列的頭指針，指向下一個元素，以保持隊列狀態的正確性。更新隊列狀態查看隊首元素隊首元素是隊列中第一個進入隊列的元素，它在隊列操作中具有特殊意義。隊首元素的定義查看隊首元素的操作不會移除該元素，僅用于獲取信息，如在售票系統中查看當前排隊人數。查看隊首元素的操作在多個領域如計算機網絡、操作系統中，查看隊首元素用于決定下一個處理的對象。隊首元素的應用場景隊列的其他操作循環隊列通過數組實現，使用模運算來處理隊尾指針的循環，提高空間利用率。循環隊列的實現優先隊列允許插入元素時指定優先級，出隊時總是優先級最高的元素先出隊。優先隊列的應用棧與隊列的應用場景PARTFIVE棧的應用實例在計算數學表達式時，如中綴表達式轉后綴表達式，棧用于臨時存儲運算符和操作數。表達式求值程序中的函數調用棧用于管理函數調用順序和局部變量，確保函數執行完畢后返回到正確的調用點。函數調用管理利用棧的后進先出特性，瀏覽器可以實現后退到上一個訪問頁面的功能。瀏覽器的后退功能01、02、03、隊列的應用實例操作系統中，打印任務通常使用隊列管理，確保文檔按提交順序依次打印。打印任務管理銀行柜臺服務采用隊列系統，