Press "Enter" to skip to content

数据结构之队列

队列 Queue

队列也是一种线性数据结构; 相比数组,队列对应的操作是数组的子集

只能从一端 (队尾) 添加元素,只能从另一端 (队首) 取出元素


就像一个银行的柜台,从队尾进入元素,在队首有柜台处理,处理了就可以出队。

出队从队首出队,1然后2。
队列是一种先进先出的数据结构(先到先得); First In First Out (FIFO)

数组队列的复杂度分析

出队的操作是从数组头部取出元素,后面的元素都要往前移动一位 所以出队操作是O(n)的复杂度

循环队列

关于循环队列需明白以下几点:
1、循环队列是队列的顺序存储结构
2、循环队列用判断是否为空利用 front==tail
3、循环队列头指针front始终指向队列头元素,而尾指针tail始终指向队列尾元素的下一个位置
4、按照队列的定义,队头删除,队尾插入,在这里插入图片描述会导致队头之前可能有空余的内存空
5、循环队列通过浪费一个空间,利用(tail+1)%count ==front判断队列是否为满,以此解决队列空间浪费问题

假设我们的队列中来了五个元素,现在需要出队一个元素, front 指向的元素就是队首元素 ,那么a出队,此时front++就可以实现不需要将a后面的元素往前挪一位

为什么叫循环队列呢,根据上图可知 整个数组空间已经占满了 ,现在我们的tail就不能++了,但是由于队首的元素a、b挪出我们的数组之后,这个空间没有被后边的元素挤掉,所以对于我们的数组来说前面还有可以利用的空间,我们可以把数组看做一个环,现在这个数组中一共可以容纳八个元素,对应的索引是0~7,那么7之后的索引其实是0,更准确的说 tail的值应该是当前的索引+1求余整个数组的长度
tail=(tail+1)%count

另一种情况

此时如果再添加一个元素放在索引为1的位置,我们的tail需要++  tail就变成了2,而front也是2,tail==front 代表队列为空,但是此时数组不为空,这不是我们所希望的条件 ,所以判断数组是否为满的条件应该是 (tail+1)%count == front 表数组已经满了,这里其实是我们有意识的浪费一个空间来实现循环队列

关于数据结构的代码 个人的php实现都在github中:https://github.com/htmax/Play-with-Data-Structures

Leave a Reply

Your email address will not be published. Required fields are marked *