对线性表予以限制,就得到了后进先出的数据结构——栈
有一种限制的线性表,它遵循先进先出的性质,这就是队列
队列是一种特殊的线性表,与线性表的不同之处体现在对数据的增和删操作上
队列的特点是先进先出:
- 先进——队列的数据新增操作只能在末端进行,不允许在队列的中间某个节点后新增数据
- 先出——队列的数据删除操作只能在始端进行,不允许在队列的中间某个节点后删除数据
队列存在两种存储方式,即顺序队列和链式队列
- 顺序队列——依赖数组来实现,其中的数据在内存中也是顺序存储
- 链式队列——依赖链表来实现,其中的数据依赖每个节点的指针互联,在内存中并不是顺序存储链式队列,实际上就是只能尾进头出的线性表的单链表
队列从对头(front)删除元素,从队尾(rear)插入元素
对于一个顺序队列的数组,设置一个front指针来指向队头,并设置一个rear指针指向队尾,不断进行插入删除操作时,头尾两个指针都会不断向后移动。
front指针删除数据的操作引发了时间复杂度过高的问题,该如何解决呢?
可以通过移动指针的方式来删除数据
两个简单粗暴的解决”假溢出“方法:
- 不惜消耗O(n)的时间复杂度去移动数据
- 开辟足够大的内存空间确保数组不会越界
数组越界问题可以通过队列的一个特殊变种来解决,叫做循环队列。
循环队列进行新增数据元素操作时,首先判断队列是否为满
如果不满,则可以将新元素赋值给队尾,然后让rear指针向后移动一个位置
如果已经排到队列最后的位置,则rear指针重新指向头部
循环队列进行删除操作时,即出队列操作,需要判断队列是否为空
然后将队头元素赋值给返回值,front指针向后移一个位置
如果已经排到队列最后的位置,就把front指针重新指向到头部
设置一个标志变量flag
链式队列是一个单链表,同时增加了front指针和rear指针
链式队列通常会增加一个头结点,并另front指针指向头结点
头结点不存储数据,只是用来辅助标识
链式队列进行新增数据操作时,将拥有数值X的新节点s赋值给原队尾节点的后继,即rear.next
然后把当前的s设置为队尾节点,指针rear指向s
当链式队列进行删除数据操作时,实际删除的是头结点的后继节点
出队列的操作,需要找到头结点的后继,这就是要删除的节点
接着让头结点指向要删除节点的后继
如果这个链表出去头结点外只剩一个元素,那么删除仅剩的一个元素后
rear指针就变成了野指针了,这时需要让rear指针指向头结点
是为了防止队列为空时,front和rear指针变成野指针
已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围,从编号为k的人报数,数到m的那个人出列,他的下一个人又从1开始报数,数到m的那个人又出列,以此规律重复下去,直到圆桌周围的人全部出列,这个问题的输入变量就是n和m,即n个人和数到m的出列的人,输出的结果,就是n个人出列的顺序。
队列的基本原理和队列对于数据的增删查的操作
队列继承了线性表的优点与不足,是加了限制的线性表
队列的增和删的操作只能在这个线性表的头和尾进行
时间复杂度上:
- 循环队列和链式队列的新增、删除操作都为O(1)
- 在查找操作中,队列只能通过全局遍历的方式进行,需要O(n)的时间复杂度
空间性能上:
- 循环队列必须有一个固定的长度,因此存在存储元素数量和空间的浪费问题
- 链式队列更为灵活一些
在可以确定队列长度最大值时,建议使用循环队列
无法确定队列长度时,应考虑使用链式队列
队列具有先进先出的特点
在面对数据处理顺序非常敏感的问题时,队列是个不错的技术选型
谢谢!