棧與隊列

棧和隊列的相同點與不同點

相同點

操作位置：棧和隊列都只允許在端點處插入和刪除元素。

• 棧：在棧頂操作。
• 隊列：在隊首和隊尾操作。

線性數據結構：兩者都是線性結構，元素按一定順序排列。

不同點

• 操作規則：
  • 棧：後進先出（LIFO）。
  • 隊列：先進先出（FIFO）。

• 插入與刪除：
  • 棧：只在棧頂插入和刪除。
  • 隊列：在隊尾插入，在隊首刪除。

順序棧判空條件

條件：

S.top == S.base

• S.base 是棧底指針，指向棧底元素的位置。
• S.top 是棧頂指針，指向當前棧頂元素的下一個位置。
• 當兩者相等時，棧為空。

循環隊列的判空與判滿

• 少用一個存儲單元
  • 為避免隊列滿與空條件混淆，循環隊列通常保留一個空單元。
  • 有效容量：若隊列大小為 $m$，實際最多存儲 $m-1$ 個元素。

• 判別條件

隊空：

Q.front==Q.rear

隊首指針與隊尾指針相等時，隊列為空。 隊滿：

(Q.rear+1)%MAXSIZE==Q.front

當隊尾指針的下一個位置與隊首指針重合時，隊列為滿。

出入隊和出入棧的序列一致性

• 隊列
  • 規則：先進先出。
  • 序列特點：入隊序列與出隊序列始終一致。
• 棧
  • 規則：後進先出。
  • 序列特點：入棧序列與出棧序列可以不一致，因為元素出棧順序與入棧順序由操作決定。