循环队列：
上一次介绍了队列的基本概念、性质和操作，本次介绍循环队列。
用一个数组，加分别指向队首，队尾的指针，实现循环队列。
初始时：队首和队尾指向相同
元素入队时，入队一个元素尾指针+1
元素入队时，入队一个元素尾指针+1
当尾指针指向数组最后一个元素，头指针未指向第一个元素时，实际上前面还有空的空间可以存储元素，称为“假溢出”
此时，可以将头指针指向前面空的元素，继续存储，这样就实现了数组空间的循环利用。
如上图，当1位置也存储了元素后，队列不能再存储元素，头指针和尾指针指向相同的位置，这样就和队列空的判断条件一样，无法判断是队列满还是队列空，如下图所示：
一般情况下，采取少存一个元素，来区别队列满还是空。另外一种方式，在程序中置一个标志位，用标志位来区别队列满和空的状态。
由上面的分析得知，循环队列元素出队和入队时，头指针和尾指针都加1。
循环队列的基本操作：
1、判断队列空 head == tail
2、入队位置计算 tail=(tail+1)% N N表示数组元素的长度
3、出队位置计算 head=(head+1)% N
4、判断队列满 (tail+1) % N =tail
5、求队列长度 (tail-head+N) % N
出队和入队位置计算为以及求队列长度为什么都%N？当head和tail为7时，加1%N=0，就是第一个元素，tail-head<0也需要+N%N保证位置为正。
循环队列的C++代码实现：
#include <iostream>
using namespace std;
const int N=6; //队列长度
int a[N]; //队列数组
int head; //头指针的位置
int tail; //尾指针的位置
void init(); //初始化
void add(int x); //队列入队
int out(); //队列出队
bool iffull(); //判断队列满
bool ifempty(); //判断队列为空
int alen(); //求当前队列的长度
int main()
{
init();
add(11);
add(12);
add(13);
cout<<out()<<endl;
cout<<out()<<endl;
cout<<out()<<endl;
cout<<out()<<endl;
return 0;
}
int alen()
{
return (tail - head +N) % N;
}
bool ifempty()
{
return head == tail;
}
bool iffull()
{
return (tail+1) % N == front;
}
int out()
{
if (ifempty())
{
cout<<"队列已空，不能出队"<<endl;
return 0;
}
int x = a[head];
head = (head+1) % N;
return x;
}
void add(int x)
{
if (iffull())
{
cout<<"队列已满，不能加入"<<endl;
return ;
}
a[tail] = x;
tail = (tail+1) % N;
}
void init()
{
head =0;
tail =0;
}
信息学奥赛循环队列相关题目：
1、设循环队列中数组的下标范围是l-n,其头指针和尾指针分别为f和r，则其元素个数为（）
A.r-f， B.r-f+1 C.(r-f) % n+1 D.（r-f+n）% n
2、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3，则当队列删除一个元素，再加两个元素后，rear和front的值分别是（）
A.1和5 B.2和4 C.4和2 D.5和1
3、循环队列中rear和font的值是15和32，队列长度是60，则队列中的元素有（）
A.42 B.16 C.17 D 43
网友评论