队列
只允许在一端进行插入操作,而另一端进行删除操作的线性表,队列是一种先进先出(FIFO)的线性表,允许插入的一端称为队尾,允许删除的一端称为队头
应用:
- 键盘进行各种字母或数字的输入,到显示器上如记事本软件上的输出
- 打字屏幕的输出
循环队列
队列顺序存储的不足
假设一个队列有n个元素,则顺序存储的队列需建立一个大于n的数组,并把队列的所有元素存储在数组的前n个单位,数组下标为0的一段即是队头。入队就是在队尾追加一个元素,不需要移动任何元素。出列是在队头,为保证队头(下标为0)的位置不为空,时间复杂度为O(n)。
如果不去限制队列的元素必须存储在数组的前n个单元这一条件,出队的性能就会大大增加。引入两个指针,front指针指向队头元素,rear指针指向队尾元素的下一个位置,这样当front等于rear时,此队列为空队列。
循环队列定义
队列的这种头尾相接的顺序存储结构称为循环队列
队列满的条件:(rear+1)%QueueSize == front
队列长度公式:(rear - front + QueueSize)%QueueSize
队列的链式存储结构及实现
队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,简称为链队列。我们将队头指针指向链队列的头结点,而队尾指针指向终端结点。空队列时,front和rear都指向头结点。
入队操作
就是在链表尾部插入结点
出队操作
将头结点的后继结点出队,将头结点的后继改为它后面的结点,若链表除头结点外只剩下一个元素时,则需将rear指向头结点
总结
对于循环队列与链队列的比较:
- 时间上,它们的基本操作都是常数操作,即都为O(1),不过循环队列是事先申请好空间,使用期间不释放,而对于链队列,每次申请和释放结点也会存放在一些时间开销,如果入队出队频繁,则两者还是有细微差异
- 空间上,循环队列必须有一个固定的长度,所以就有了存储元素个数和空间浪费的问题,链队列不存在这个问题,尽管需要一个指针域,会产生一些空间上的开销,可以接受,在空间上更加灵活。
- 在确认队列长度最大值的情况下,建议使用循环队列,无法预估时,使用链队列