408数据结构考点：循环队列

Answer 1

在数据结构学习中，同学们常会遇到循环队列这一概念。本文整理了部分难点，并提供了原创解题方法与例题。

首先，介绍开闭区间模型。整数域[公式]内的所有整数集合可用开闭区间表示，即[公式]。将此模型应用到队列上，队列元素下标形成区间，其中队头指针front位于左端点，队尾指针rear位于右端点。

具体区间类型如下：闭区间型（front指向队头元素位置，rear指向队尾元素位置）；左闭右开区间型（front指向队头元素位置，rear指向队尾元素位置的后一个位置）；左开右闭区间型（front指向队头元素位置的前一个位置，rear指向队尾元素位置）；开区间型（front指向队头元素位置的前一个位置，rear指向队尾元素位置的后一个位置）。

真题常考察闭区间型和左闭右开区间型。例如，队列front指向队头元素位置，rear指向队尾元素位置后一个位置，若队列初始为空，front=0，求rear位置。显然，本题为左闭右开区间型，初始时[公式]，故rear=0。

再如，front指向队头元素位置，rear指向队尾元素位置，若队列初始为空，front=0，求rear位置。此题为闭区间型，初始时[公式]，故rear=-1。

循环队列则是将顺序表空间视为首尾相接的圆环，队列因此被称为循环队列(circular queue)。区分队空与队满有三种方法。

历年真题中，重点考察的是左闭右开区间型+空一法、左闭右开区间型+计数法、左闭右开区间型+标记法等构造方法。以2011年第3题为例，已知循环队列存储在一维数组[公式]，队列非空时，front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个元素存储在[公式]处，则front和rear的初始值为（ ）。答案为B。

2014年第3题，循环队列使用一维数组A[0..M-1]存储，end1指向队头元素，end2指向队尾元素的后一个位置。队列两端均可进行入队和出队操作，最多容纳M-1个元素。初始为空，判断队空和队满的条件中正确的是（ ）。解答为A。此题采用左闭右开区间型和空一法。