棧和隊列的邏輯結構與線性表相同,其特點在于運算有所限制(運算受限的線性表),棧操作按照後進先出(LIFO)的規則,隊列按先進先出(FIFO)的規則。
棧通過訪問它的一端來實現數據存儲與檢索的線性結構。
進行插入和删除操作的一端稱為棧頂(Top),另一端稱為棧底(Bottom),不包含數據元素的棧,稱為空棧。
初始化棧->判斷棧是否為空->入棧(Push)->出棧(Pop)->讀取棧頂元素
初始化棧:創建一個空棧。
判斷棧是否為空:為空是返回true(真),否則false(假)
入棧:将元素加入棧頂,并更新棧頂指針。
出棧:将棧頂元素删除,并更新棧頂指針。
讀棧元素:返回棧頂元素的值,不更新指針。
順序存儲(順序棧):
用一組地址連續的存儲單元依次存儲自棧頂到棧底的數據元素,同時指針指示棧頂元素的位置。這種存儲方式下,棧的空間容量是有限的,當元素入棧時,需要判斷是否棧滿,如棧滿,則不能入棧。
鍊式存儲(鍊棧):
棧中元素的插入和删除隻在棧頂一端進行,因此不需要設置頭指針,鍊表的頭指針就是棧頂指針。
隊列隊列是一種先進先出(FIFO)的線性表,它隻允許在表的一端(隊尾)插入元素,在另一端(隊頭)删除元素。
初始化->判斷是否為空 ->入隊 ->出隊 -> 讀隊頭元素
初始化:創建一個空隊列(隊頭和隊尾指針在同一位置)。
判斷是否為空:為空是返回true(真),否則false(假)
入隊:将元素加入隊尾(Rear),并更新隊尾指針。
出隊:将隊頭(Front)元素從隊列删除,并更新隊頭指針。
讀隊頭元素:讀取隊頭元素的值,不更新隊頭指針。
順序存儲(順序隊列):
用一組地址連續的存儲單元存儲隊列元素,隊列的操作是兩端進行的,因此設置隊頭指針和隊尾指針,分别指出隊頭和隊尾。
元素入隊時,修改隊尾指針。元素出隊時,修改隊頭指針。
由于順序隊列的存儲空間是預先設定的,因此隊尾指針會有一個上限值(下圖所示)。
元素入隊出隊以及指針修改過程
當隊尾指針達到上限時,隻能通過修改隊尾指針來實現新元素的入隊。
,更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!