循環(huán)隊列：
上一次介紹了隊列的基本概念、性質(zhì)和操作，本次介紹循環(huán)隊列。
用一個數(shù)組，加分別指向隊首，隊尾的指針，實現(xiàn)循環(huán)隊列。
初始時：隊首和隊尾指向相同
元素入隊時，入隊一個元素尾指針+1
元素入隊時，入隊一個元素尾指針+1
當(dāng)尾指針指向數(shù)組最后一個元素，頭指針未指向第一個元素時，實際上前面還有空的空間可以存儲元素，稱為“假溢出”
此時，可以將頭指針指向前面空的元素，繼續(xù)存儲，這樣就實現(xiàn)了數(shù)組空間的循環(huán)利用。
如上圖，當(dāng)1位置也存儲了元素后，隊列不能再存儲元素，頭指針和尾指針指向相同的位置，這樣就和隊列空的判斷條件一樣，無法判斷是隊列滿還是隊列空，如下圖所示：
一般情況下，采取少存一個元素，來區(qū)別隊列滿還是空。另外一種方式，在程序中置一個標(biāo)志位，用標(biāo)志位來區(qū)別隊列滿和空的狀態(tài)。
? ? ? 由上面的分析得知，循環(huán)隊列元素出隊和入隊時，頭指針和尾指針都加1。
循環(huán)隊列的基本操作：
1、判斷隊列空 ?head == tail?
2、入隊位置計算 tail=(tail+1)% N? N表示數(shù)組元素的長度
3、出隊位置計算 head=(head+1)% N
4、判斷隊列滿 ?(tail+1) % N =tail
5、求隊列長度 (tail-head+N) % N
? ? ? 出隊和入隊位置計算為以及求隊列長度為什么都%N？當(dāng)head和tail為7時，加1%N=0，就是第一個元素，tail-head<0也需要+N%N保證位置為正。
循環(huán)隊列的C++代碼實現(xiàn)：
#include <iostream>
using namespace std;
const int N=6;? //隊列長度
int a[N];? ? ? //隊列數(shù)組
int head;? //頭指針的位置
int tail;? //尾指針的位置
void init();? //初始化
void add(int x); //隊列入隊
int out();? ? ? //隊列出隊
bool iffull();? //判斷隊列滿
bool ifempty();? //判斷隊列為空
int alen();? ? ? //求當(dāng)前隊列的長度
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;
}
? 信息學(xué)奧賽循環(huán)隊列相關(guān)題目：
1、設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是l-n,其頭指針和尾指針分別為f和r，則其元素個數(shù)為（）
A.r-f， ?B.r-f+1 ?C.(r-f) % n+1 ?D.（r-f+n）% n
2、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)rear和front的值分別為0和3，則當(dāng)隊列刪除一個元素，再加兩個元素后，rear和front的值分別是（） ?
?A.1和5 B.2和4 C.4和2 D.5和1
3、循環(huán)隊列中rear和font的值是15和32，隊列長度是60，則隊列中的元素有（）?
?A.42 ?B.16 C.17 D 43
