队列

一端插入,一端删除

线性表中表尾插入,表头删除

队列的顺序表结构

存储一个头指针front,一个尾指针rear,表长度Length。

缺点是在入队出队的过程中,头尾指针均会向表尾移动导致最终发生溢出(rear==MaxQSize)

真假溢出

真溢出是指顺序表完全占满,

假溢出指顺序表仍有空位(fromt!=0),但是rear==MaxQSize

解决假溢出

  • 将所有元素向表头移动(浪费时间)
  • 将存储空间头尾逻辑上连接在一起,变成循环表(具体实现使用模运算)

ps:模运算有某种“循环”的意义。

队列的链表结构

与顺序表结构相比,没有假溢出的问题,其他操作类似,不再赘述。