循环队列问题总结

2022-08-22 08:27:13

循环队列问题总结

@(算法学习)

直接以2011年一道选择题为例分析循环队列如何简单思考。
(2011.3)已知循环队列存储在一维数组中A[0…n-1],且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空,且要求第一个进入队列的元素存储在A[0]处,则初始时front和rear的值分别为:B.
A.0,0 B.0, n-1 C.n-1,0 D.n-1,n-1

分析:最初我认为这类题目分析会较为复杂,记住结论才是最佳的解决方案,但实际上发现每道题都可以创新,根本不是识记可以解决的。而最佳的是动手分析,掌握基本的原则。在栈的下标问题中,有过简单的讨论:

http://blog.csdn.net/u011240016/article/details/52723593?locationNum=2&fps=1

这里也是一样,首先需要明确,队列是两头操纵,队尾进,队头出。还要小心进队时下标的更新方向,有时候就是特别奇怪,假定下标减为进队。

本题,我们从一般情况分析:

这里写图片描述

当进元素时,rear将后移,以便指向新的队尾元素。出队时,front后移,更新指向新的队头。

那么我们想,只有最初只有一个元素时:

这里写图片描述

反推,front不用动,但是rear要退一个位置,往哪退?按照循环,第一个元素位置可以直接到最后一个位置上,因此,如图所示。所以在数组中初态就是0,n-1.

有一个问题,为什么front初态不是在最后一个位置呢?因为为了操作的统一性,进队时,并不更新front,所以front初态在第一个元素的位置,即下标为0处。

  • 作者:DrCrypto
  • 原文链接:https://bingw.blog.csdn.net/article/details/53201922
    更新时间:2022-08-22 08:27:13