栈与队列

栈和队列的相同点与不同点

相同点

操作位置：栈和队列都只允许在端点处插入和删除元素。

• 栈：在栈顶操作。
• 队列：在队首和队尾操作。

线性数据结构：两者都是线性结构，元素按一定顺序排列。

不同点

• 操作规则：
  • 栈：后进先出（LIFO）。
  • 队列：先进先出（FIFO）。

• 插入与删除：
  • 栈：只在栈顶插入和删除。
  • 队列：在队尾插入，在队首删除。

顺序栈判空条件

条件：

S.top == S.base

• S.base 是栈底指针，指向栈底元素的位置。
• S.top 是栈顶指针，指向当前栈顶元素的下一个位置。
• 当两者相等时，栈为空。

循环队列的判空与判满

• 少用一个存储单元
  • 为避免队列满与空条件混淆，循环队列通常保留一个空单元。
  • 有效容量：若队列大小为 $m$，实际最多存储 $m-1$ 个元素。

• 判别条件

队空

Q.front==Q.rear

队首指针与队尾指针相等时，队列为空。

队满

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

当队尾指针的下一个位置与队首指针重合时，队列为满。

出入队和出入栈的序列一致性

• 队列
  • 规则：先进先出。
  • 序列特点：入队序列与出队序列始终一致。
• 栈
  • 规则：后进先出。
  • 序列特点：入栈序列与出栈序列可以不一致，因为元素出栈顺序与入栈顺序由操作决定。