博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
循环队列
阅读量:4217 次
发布时间:2019-05-26

本文共 644 字,大约阅读时间需要 2 分钟。

设计循环队列的原因:
队列的顺序存储结构称为顺序队列,顺序队列实际上是运算受限的顺序表,和顺序表一样,顺序队列也是必须用一个向量空间来存放当前队列中的元素。

入队,出队操作原理:

由于队列的队头和队尾的位置是变化的,因而要设两个指针和分别指示队头和队尾元素在队列中的位置,它们的初始值地队列初始化时均应置为0。入队时将新元素插入所指的位置,然后将加1。出队时,删去所指的元素,然后将加1并返回被删元素。

杜绝“假上溢”:

和栈类似,队列中亦有上溢和下溢现象。此外,顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中,头尾指针只增加不减小,致使被删除元素的 空间永远无法重新利用。因此,尽管队列中实际的元素个数远远小于向量空间的规模,但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。

为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量,存储在其中的队列称为循环队列(Circular Queue)。在循环队列中进行出队、入队操作时,头尾指针仍要加1,朝前移动。只不过当头尾指针指向向量上界(QueueSize-1)时,其加1操作的结果是指向向量的下界0。


判断循环队列是否为空(rear=front


判断循环队列是否为满(解决这个问题有两个办法:一是增加一个参数,用来记录数组中当前元素的个数;第二个办法是,少用一个存储空间,也就是数组的最后一个存数空间不用,当(rear+1)%maxsiz=front时,队列满;)。

转载地址:http://yutmi.baihongyu.com/

你可能感兴趣的文章
LINUX时间管理
查看>>
定时器的使用
查看>>
为Android加入busybox工具
查看>>
使用技巧busybox
查看>>
如何查看与/dev/input目录下的event对应的设备
查看>>
bootloader-bootable解析
查看>>
bootloader (LK)&&android lk bootloader中相关修改指南
查看>>
SD卡驱动分析--基于高通平台
查看>>
SD Card 驱动流程分析
查看>>
Linux之debugfs介绍
查看>>
关于sd卡中一些概念的理解
查看>>
sd卡驱动分析之相关硬件操作和总结
查看>>
linux dd命令解析
查看>>
S3C2440上touchscreen触摸屏驱动
查看>>
USB History Viewing
查看>>
怎样做可靠的分布式锁,Redlock 真的可行么?
查看>>
[图文] Seata AT 模式分布式事务源码分析
查看>>
pm 源码分析
查看>>
Sending the User to Another App
查看>>
kmsg_dump
查看>>