数据结构与算法-队列
# 数据结构与算法-队列
# 1. 队列的一个使用场景
银行排队的案例:
# 2. 队列介绍
- 队列是一个有序列表,可以用数组或是
链表
来实现。 - 遵循
先入先出
的原则。即:先存入队列的数据,要先取出。后存入的要后取出 - 示意图:(使用数组模拟队列示意图)
分析上图:rear是队列尾部,front队列的头部,
- 队列1是没有数据时候,rear、front都为-1
- 队列2是加完数据后的图,rear变为3,front不变;可以看出加数据是从队列尾部加入
- 队列3是取出了2个数据后的图,rear不变,front变为2;可以看出取数据是从队列的头部取出
# 3. 数组模拟队列
队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理,因此需要两个变量 front及 rear分别记录队列前后端的下标,front 会随着数据输出而改变,而 rear则是随着数据输入而改变,如图所示:
# 思路分析
当我们将数据存入队列时称为”addQueue”,addQueue 的处理需要有两个步骤:
- 将尾指针往后移:rear+1 , 当front == rear 【空】
- 若尾指针 rear 小于队列的最大下标 maxSize-1,则将数据存入 rear所指的数组元素中,否则无法存入数据。
rear == maxSize - 1
[队列满]
# 代码实现
- 出队列操作getQueue
- 显示队列的情况showQueue
- 查看队列头元素headQueue
- 退出系统exit将
原来的队列的查看队列头元素的代码写完.
# 4. 优化
对前面的数组模拟队列的优化,充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)
分析说明:
rear == front [空]
测试示意图:
课堂练习:
同学们完成环形数组模拟的队列的输出
(cq.rear + cq.maxSize – cq.front) % cq.maxSize
上次更新: 2023/04/12, 14:35:21