定义:
特殊的线性表。
特点:
1.先进先出;连结性。
2.作为一种特殊性的表,主要是在表前端进行删除操作,我们称删除的端为对头(front);只能在表的后端进行插入操作,我们称之为称插入的端为对尾。
为什么使用队列:
1.更好的异步处理数据和传输
2.频繁的向数据库插入数据或者频繁的想搜索引擎提交数据等用户操作情况
3.更好的处理慢的处理逻辑,有并发限制的处理逻辑。如发送邮件等批量处理操作
分类:
1.顺序对列
2.循环队列
顺序队列:
定义:静态分配或者动态申请一片连续的存储空间,并设置两个指针进行管理,一个是队头指针(front),一个是对尾指针(rear)。
特点:队尾rear增加1,队头删除增加1,随着队列的元素变化,队列所暂据的存储空间也在队列的结构所分配的存储空间移动。
分类:空队列,溢出
空队列:队列中不存在元素,对列增加(front)=队列删除(rear)
溢出:
1.下溢:当队列是空,做出队列运算的溢出现象。这属于正常现象,我们常用它来作为程序控制转移的条件。
2.真上溢:当队列已满,做队列的进栈运算所产生的溢出现象。这属于错误现象。
3.加上溢:
1.当入队和出队操作,头尾指针只加不减,导致被删除的空间没被重复使用。
2.当队列中实际的元素个数小于向量空间规模的模式,也可能由于尾针已经超越向量空间的上界而不能入队操作。
循环队列:
目的:实现空间的循环利用(在开发中,使用此类型居多)
定义:无论是删除还是插入,一旦队尾指针(rear)增加1或者对头指针减少增加1,超出了分配的空间,就让他指向起始向位置。
元素:队列中,元素的最大个数最大只能为maxsize-1
区别:当为空队列的时候,frnotallow=rear;同时队列已满。frnotallow=rear;
如何来鉴别这两种呢?当frnotallow=rear的时候为空队列;当(frnotallow=rear+1)%maxsize的时候为满队列