数据结构基础第4讲 队列
内容
考点一： 队列概念
代码不考
1.队列的定义
考点二：顺序队列的定义
考点三顺序队列的性质与操作
4要素：
考点四：循环队列的定义
由于顺序队列会存在假溢出问题，引入循环队列。
假溢出：
描述：
考点五：循环队列的操作
-
判断空满：
-
性质：
考频75%
元素个数求法：
-
rear < front
f-r 为空的个数
元素个数为：
\([n-(f-r)] \% n = (r-f+n) \% n\)
-
rear > front
\(r-f\) 为元素个数
元素个数为：
\((r-f)\%n\)
为了形式统一将情况二写成：
\(\begin{matrix} (r-f)\%n &=(r-f) \%n + n \%n \\ &=(r-f+n)\%n \end{matrix}\)
-
-
环形队列实现的三种方式
-
队首指针始终指向队头元素，队尾指针始终指向队尾元素的下一个位置
-
队首指针始终指向队头元素的前一个位置，队尾指针始终指向队尾元素
-
队首指针始终指向队头元素，队尾指针始终指向队尾元素[需要加入len表示元素个数]
- 初始化 f=0；rear = MaxSize-1
空 ；\((r+1)\%==front\)
满：\((r+1)\%MaxSize\)
例题4：
例题5：
属于第二种情况
- 元素个数：\(len=(rear-front+QueueSize)\%QueueSize\)
- 由于
- \[len=QueueSize-1<QueueSize \]
- 所以
- \[len\%QueueSize=len \]
- 将上式子带入元素个数得
- \[\begin{align} len\%QS &= (r-f+QS)\%QS \\ &= r\%QS-f\%QS+QS\%QS \end{align} \]
- \[\begin{align}f\%QS&=f\\&=(r-len+QS)\%QS\end{align} \]
-
若题目未明确是第几种，按第一或第二考虑
考点七：链队列的定义
- 入队出队：
- 链队的4要素：
-
实现队列的方式
- 分别给出头尾指针 最佳方案
- 单链表：带尾指针的单循环链表
- 双链表：给头指针或尾指针的双循环链表
考点八：链队列的操作
-
初始化
-
销毁
-
判空
-
进队
考虑情况：
- 原队列为空
- 原队列非空
-
出队
考虑情况：
- 原队列为空
- 原队列只有一格节点
- 其他情况
\(\divideontimes\)不管啥题就选 队首/队尾均可以
考点九：双端队列
输出受限：
输入受限：
