数据结构与算法-队列
展开全部
同样是线性表,队列也有类似线性表的各种操作,不同的就是插入数据只能在队尾进行,删除数据只能在队头进行。
线性表有顺序存储和链式存储,栈是线性表,所以有这两种存储方式。同样,队列作为一种特殊的线性表,也同样存在这两种存储方式。
我们假设一个队列有n个元素,则顺序存储的队列需建立一个大于n的数组,并把队列的所有元素存储在数组的前n个单元,数组下标为0的一端即是队头。所谓的入队列操作,其实就是在队尾追加一个元素,不需要移动任何元素,因此时间复杂度为 。
与栈不同的是,队列元素的出列是在队头,即下标为0的位置,那也就意味着,队列中的所有元素都得向前移动,以保证队列的队头,也就是下标为0的位置不为空,此时时间复杂度为 。
可有时想想,为什么出队列时一定要全部移动呢,如果不去限制队列的元素必须存储在数组的前n个单元这一条件,出队的性能就会大大增加。也就是说,队头不需要一定在下标为0的位置,
为了避免当只有一个元素时,队头和队尾重合使处理变得麻烦,所以引入两个指针,front指针指向队头元素,rear指针指向队尾元素的下一个位置,这样当front等于rear时,此队列不是还剩一个元素,而是空队列。
假设是长度为5的数组,初始状态,空队列列如图所示,front与rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4,front指针依然指向下标为0位置,而rear指针指向下标为4的位置。
出队a1、a2,则front指针指向下标为2的位置,rear不变,如图4-12-5的左图所示,再入队a5,此时front指针不变,rear指针移动到数组之外。嗯?数组之外,那将是哪里?如下图的右图所示。
假设这个队列的总个数不超过5个,但目前如果接着入队的话,因数组末尾元素已经占用,再向后加,就会产生数组越界的错误,可实际上,我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。
所以解决假溢出的办法就是后面满了,就再从头开始,也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。
如果将rear的指针指向下标为0的位置,那么就不会出现指针指向不明的问题了,如下图所示。
接着入队a6,将它放置于下标为0处,rear指针指向下标为1处,如下图的左图所示。若再入队a7,则rear指针就与front指针重合,同时指向下标为2的位置,如下图的右图所示。
由于rear可能比front大,也可能比front小,所以尽管它们只相差一个位置时就是满的情况,但也可能是相差整整一圈。
所以若队列的最大尺寸为QueueSize,那么队列满的条件是(rear+1)%QueueSize==front(取模“%”的目的就是为了整合rear与front大小为一圈问题)。比如上面这个例子,QueueSize=5,上图的左图中front=0,而rear=4,(4+1)%5=0,所以此时队列满。
再比如图下图中的,front=2而rear=1。(1+1)%5=2,所以此时队列也是满的。
而对于下图,front=2而rear=0,(0+1)%5=1,1≠2,所以此时队列并没有满。
另外,当rear>front时,此时队列的长度为rear-front。
但当rear<front时,,队列长度分为两段,一段是QueueSize-front,另一段是0+rear,加在一起,队列长度为rear-front+QueueSize。因此通用的计算队列满队公式为:
单是顺序存储,若不是循环队列,算法的时间性能是不高的,但循环队列又面临着数组可能会溢出的问题,所以我们还需要研究一下不需要担心队列长度的链式存储结构。
队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。为了操作上的方便,我们将队头指针指向链队列的头结点,而队尾指针指向终端结点。
空队列时,front和rear都指向头结点。
链队列的结构为:
初始化一个空队列
入队操作时,其实就是在链表尾部插入结点,如图所示。
出队操作时,就是头结点的后继结点出队,将头结点的后继改为它后面的结点,若链表除头结点外只剩一个元素时,则需将rear指向头结点,如图所示。
对于循环队列与链队列的比较,可以从两方面来考虑,从时间上,其实它们的基本操作都是常数时间,即都为O(1)的,不过循环队列是事先申请好空间,使用期间不释放,而对于链队列,每次申请和释放结点也会存在一些时间开销,如果入队出队频繁,则两者还是有细微差异。对于空间上来说,循环队列必须有一个固定的长度,所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题,尽管它需要一个指针域,会产生一些空间上的开销,但也可以接受。所以在空间上,链队列更加灵活。
总的来说,在可以确定队列长度最大值的情况下,建议用循环队列,如果你无法预估队列的长度时,则用链队列。
栈和队列也都可以通过链式存储结构来实现,实现原则上与线性表基本相同如图所示。
线性表有顺序存储和链式存储,栈是线性表,所以有这两种存储方式。同样,队列作为一种特殊的线性表,也同样存在这两种存储方式。
我们假设一个队列有n个元素,则顺序存储的队列需建立一个大于n的数组,并把队列的所有元素存储在数组的前n个单元,数组下标为0的一端即是队头。所谓的入队列操作,其实就是在队尾追加一个元素,不需要移动任何元素,因此时间复杂度为 。
与栈不同的是,队列元素的出列是在队头,即下标为0的位置,那也就意味着,队列中的所有元素都得向前移动,以保证队列的队头,也就是下标为0的位置不为空,此时时间复杂度为 。
可有时想想,为什么出队列时一定要全部移动呢,如果不去限制队列的元素必须存储在数组的前n个单元这一条件,出队的性能就会大大增加。也就是说,队头不需要一定在下标为0的位置,
为了避免当只有一个元素时,队头和队尾重合使处理变得麻烦,所以引入两个指针,front指针指向队头元素,rear指针指向队尾元素的下一个位置,这样当front等于rear时,此队列不是还剩一个元素,而是空队列。
假设是长度为5的数组,初始状态,空队列列如图所示,front与rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4,front指针依然指向下标为0位置,而rear指针指向下标为4的位置。
出队a1、a2,则front指针指向下标为2的位置,rear不变,如图4-12-5的左图所示,再入队a5,此时front指针不变,rear指针移动到数组之外。嗯?数组之外,那将是哪里?如下图的右图所示。
假设这个队列的总个数不超过5个,但目前如果接着入队的话,因数组末尾元素已经占用,再向后加,就会产生数组越界的错误,可实际上,我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。
所以解决假溢出的办法就是后面满了,就再从头开始,也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。
如果将rear的指针指向下标为0的位置,那么就不会出现指针指向不明的问题了,如下图所示。
接着入队a6,将它放置于下标为0处,rear指针指向下标为1处,如下图的左图所示。若再入队a7,则rear指针就与front指针重合,同时指向下标为2的位置,如下图的右图所示。
由于rear可能比front大,也可能比front小,所以尽管它们只相差一个位置时就是满的情况,但也可能是相差整整一圈。
所以若队列的最大尺寸为QueueSize,那么队列满的条件是(rear+1)%QueueSize==front(取模“%”的目的就是为了整合rear与front大小为一圈问题)。比如上面这个例子,QueueSize=5,上图的左图中front=0,而rear=4,(4+1)%5=0,所以此时队列满。
再比如图下图中的,front=2而rear=1。(1+1)%5=2,所以此时队列也是满的。
而对于下图,front=2而rear=0,(0+1)%5=1,1≠2,所以此时队列并没有满。
另外,当rear>front时,此时队列的长度为rear-front。
但当rear<front时,,队列长度分为两段,一段是QueueSize-front,另一段是0+rear,加在一起,队列长度为rear-front+QueueSize。因此通用的计算队列满队公式为:
单是顺序存储,若不是循环队列,算法的时间性能是不高的,但循环队列又面临着数组可能会溢出的问题,所以我们还需要研究一下不需要担心队列长度的链式存储结构。
队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。为了操作上的方便,我们将队头指针指向链队列的头结点,而队尾指针指向终端结点。
空队列时,front和rear都指向头结点。
链队列的结构为:
初始化一个空队列
入队操作时,其实就是在链表尾部插入结点,如图所示。
出队操作时,就是头结点的后继结点出队,将头结点的后继改为它后面的结点,若链表除头结点外只剩一个元素时,则需将rear指向头结点,如图所示。
对于循环队列与链队列的比较,可以从两方面来考虑,从时间上,其实它们的基本操作都是常数时间,即都为O(1)的,不过循环队列是事先申请好空间,使用期间不释放,而对于链队列,每次申请和释放结点也会存在一些时间开销,如果入队出队频繁,则两者还是有细微差异。对于空间上来说,循环队列必须有一个固定的长度,所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题,尽管它需要一个指针域,会产生一些空间上的开销,但也可以接受。所以在空间上,链队列更加灵活。
总的来说,在可以确定队列长度最大值的情况下,建议用循环队列,如果你无法预估队列的长度时,则用链队列。
栈和队列也都可以通过链式存储结构来实现,实现原则上与线性表基本相同如图所示。
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
迈杰
2024-11-30 广告
2024-11-30 广告
RNA-seq数据分析是转录组研究的核心,包括数据预处理、序列比对、定量分析、差异表达分析、功能注释和可视化等步骤。数据预处理主要是质量控制和去除低质量序列。序列比对使用HISAT2、STAR等工具将reads比对到参考基因组。定量分析评估...
点击进入详情页
本回答由迈杰提供
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询