我命由我不由天


  • 搜索
prometheus docker golang linux kubernetes

队列

发表于 2021-07-08 | 0 | 阅读次数 463

队列

只允许在一端进行插入操作,而另一端进行删除操作的线性表,队列是一种先进先出(FIFO)的线性表,允许插入的一端称为队尾,允许删除的一端称为队头

应用:

  1. 键盘进行各种字母或数字的输入,到显示器上如记事本软件上的输出
  2. 打字屏幕的输出

循环队列

队列顺序存储的不足

假设一个队列有n个元素,则顺序存储的队列需建立一个大于n的数组,并把队列的所有元素存储在数组的前n个单位,数组下标为0的一段即是队头。入队就是在队尾追加一个元素,不需要移动任何元素。出列是在队头,为保证队头(下标为0)的位置不为空,时间复杂度为O(n)。

如果不去限制队列的元素必须存储在数组的前n个单元这一条件,出队的性能就会大大增加。引入两个指针,front指针指向队头元素,rear指针指向队尾元素的下一个位置,这样当front等于rear时,此队列为空队列。

循环队列定义

队列的这种头尾相接的顺序存储结构称为循环队列

队列满的条件:(rear+1)%QueueSize == front

队列长度公式:(rear - front + QueueSize)%QueueSize

队列的链式存储结构及实现

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,简称为链队列。我们将队头指针指向链队列的头结点,而队尾指针指向终端结点。空队列时,front和rear都指向头结点。

入队操作

就是在链表尾部插入结点

出队操作

将头结点的后继结点出队,将头结点的后继改为它后面的结点,若链表除头结点外只剩下一个元素时,则需将rear指向头结点

总结

对于循环队列与链队列的比较:

  1. 时间上,它们的基本操作都是常数操作,即都为O(1),不过循环队列是事先申请好空间,使用期间不释放,而对于链队列,每次申请和释放结点也会存放在一些时间开销,如果入队出队频繁,则两者还是有细微差异
  2. 空间上,循环队列必须有一个固定的长度,所以就有了存储元素个数和空间浪费的问题,链队列不存在这个问题,尽管需要一个指针域,会产生一些空间上的开销,可以接受,在空间上更加灵活。
  3. 在确认队列长度最大值的情况下,建议使用循环队列,无法预估时,使用链队列
  • 本文作者: Dante
  • 本文链接: https://gaodongfei.com/archives/队列
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
leetcode-栈相关习题
es
  • 文章目录
  • 站点概览
Dante

Dante

119 日志
5 分类
5 标签
RSS
Creative Commons
0%
© 2023 Dante
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4
沪ICP备2020033702号