数据结构与算法·其八
队列
一端插入,一端删除
线性表中表尾插入,表头删除
队列的顺序表结构
存储一个头指针front,一个尾指针rear,表长度Length。
缺点是在入队出队的过程中,头尾指针均会向表尾移动导致最终发生溢出(rear==MaxQSize)
真假溢出
真溢出是指顺序表完全占满,
假溢出指顺序表仍有空位(fromt!=0),但是rear==MaxQSize
解决假溢出
- 将所有元素向表头移动(浪费时间)
- 将存储空间头尾逻辑上连接在一起,变成循环表(具体实现使用模运算)
ps:模运算有某种“循环”的意义。
队列的链表结构
与顺序表结构相比,没有假溢出的问题,其他操作类似,不再赘述。