引入
我们之前说,队列我们一般使用的是链式存储结构,而不是顺序存储结构。我们今天就看看如何构造队列的顺序存储结构,然后看看顺序存储结构给队列带来了哪些问题。
想一想
我们假设,有一个队列
- 有 n 个元素
- 那么顺序存储结构就需要大于 n 的存储单元
- 数组下标 0 是头部,n 个元素存储在数组的前 n 个存储单元中。
(图片来自于鱼 C 工作室)
入队
- 0 号下标是队头
- 然后数据不断进来,不断移动队尾指针。
- 只需要将队尾指针+1即可
- 时间复杂度为 O ( 1 )
出队
- 因为0号下标是队头
- 0号到元素出去之后,后面所有的元素都要向前移动一位
- 就像是排队,第一个人搞定离开,后面的人依次向前走一步
- 这时候,时间复杂度度就是 O ( n ) 了
- 出队的效率就大打折扣!
因为出队效率太慢,我们就想
- 不去限制队头一定是 0 号下标
- 我们让队头指针也动起来
- 即0号的元素出去之后,队头指针移动到1号下标
- 循环往复,这样,出队就不用所有人都移动了
- 就好像排队,排在第一位的人搞定了,柜台向前移动,到第二个人面前
但是…上面这种情况会遇到这样的问题…
- 如果就像上面的,只有 5 个元素,下标只到 4
- 释放了前两个元素,那如果队列满了之后,再插入就会出错
所以,因为要解决上面的这种数据输入溢出的问题
- 如果后面满了,那就把尾指针从头开始,也就是收尾相连
- 队头和队尾的指针随着输入和输出不断移动
这样的话
- 一开始 front 和 rear 都指向同一个结点
- front 始终指向第一个队列中的结点
- rear 始终指向当前可插入的结点
当然,我们这里想的比较多,如果都清楚的话,就可以开始初始化一个循环队列了。
定义一个循环队列
1 | struct Queue{ |
定义队列比较简单
- 一个用于存储数据
- 两个灵活多变的头部和尾部
初始化一个循环队列
我们将刚才定义的循环队列结构体初始化
1 |
|
大概思路就是
- 因为顺序存储结构的队列是固定大小的,先动态生成固定大小的内存空间
- 然后让头指针和尾指针都归位到 0
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。