循环队列与队列的链式结构

  • A+

队列就是一种受限的线性表

它规定先进先出

也就是说只能在表尾插入数据

在表头提出数据


下面实现队列的顺序存储结构

这里只实现最有价值的循环队列

也就是

循环队列与队列的链式结构
队尾下一位指针可以由数组的后面从新在指向数组的前面

只要数组的位置是空的

而队头指针也一样,也是可以不停向后,然后从头开始


_data数组用于保存数据

_front指向队头

_rear指向队尾的下一个空位

_maxLength可以保存数据的最大长度

两个构造函数初始化化队列为空(_front == _rear)

初始化数组的大小为保存数据长度+1

是因为要留一个空位来去判断队列是否已满

如果不留,那么队满也是_front == _rear

这样就冲突了

当然可以设置一个标志位


判断是否为空和是否为满

前面已经说过

如果队头和队尾指针同时指向同一个

那么就是为空

那么重点说说为满

前面也说过,留了一位用于判断队满情况

那么可以是

循环队列与队列的链式结构
也可以是

循环队列与队列的链式结构
也就是说rear指针可能比front大

也可能比它小

但它们在数组范围内只相差一位

共同的方法就是将rear+1后求余于数组的长度

那就是循环队列的rear的下一位了

这个在后面指针移动时都要用到


入队的话

①先判断一下队列有没有满

②没有满的话就插入数据

因为rear指针指向的是队尾的下一个

也就是空位置,所以直接插入就行了

③将尾指针后移一位,前面已经说过后移一位的方法


出队的话

①先判断一下队列是否为空

②不为空的话输出队头数据,front指向的数据

③队头指针向后移动一位


在队列不为空(front == rear)之前

循环清楚数据,将队列清空

并赋值头尾从0开始


这个重点说一下

分两种情况

①就是队尾rear指针大于队头指针front

循环队列与队列的链式结构
length = rear - front

②队尾rear指针小于队头指针front

循环队列与队列的链式结构
这种情况就分两段

length1 = 数组长度 - front

length2 = rear

length = length1 + length2

= rear - front + 数组长度

那么综合两个情况

可以总结出

队列的长度为:

(rear - front + 数组长度)% 数组长度


测试

结果

循环队列与队列的链式结构


队列的链式存储结构

与普通的链表差不多

只是只能在队头删除并取出元素

在队尾插入元素

这里就不详细说了

方法的实现说明可以参考前面线性表的链式结构


测试

结构
循环队列与队列的链式结构

  • 我的微信
  • 扫一扫加我微信
  • weinxin
  • 微信我的
  • 我微信扫一扫加
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: