循環隊列
隊列通常分為兩類：一是動態鏈式隊列(其核心思想為鏈表，只是少了鏈表的一些功能)，二是靜態(順序)隊列(其核心是用數組實現，准確一點講是由向量空間來實現，向量空間好比是開辟的一塊內存，由我們的指針來指向其地址)。順序隊列實際上是運算受限的順序表，由於隊列的隊頭和隊尾的位置是變化的，通常設置兩個指針front和rear分別指示隊頭元素和隊尾元素在向量空間中的位置，它們的初值在隊列初始化時均應置為0。由於入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法重新利用。當隊列中實際的元素個數遠遠小於向量空間的規模時，也可能由於尾指針已超越向量空間的上界而不能做入隊操作。這種“假上溢”現象常常造成內存資源的浪費，這時就產生了循環隊列(首尾相接)。循環隊列克服“假上溢”現象的方法是：將向量空間想象成一個首尾相連的圓環，將循環隊列存放在其中。循環隊列中，由於入隊時尾指針向前追趕頭指針；出隊時頭指針向前追趕尾指針，造成隊空和隊滿時頭尾指針均相等。因此，無法通過條件front==rear來判別隊列是"空"還是"滿"。針對這樣情況，有兩種解決方法：一是少用一個元素的空間。約定入隊前，測試尾指針在循環意義下加1後是否等於頭指針，若相等則認為隊滿（注意：rear所指的單元始終為空），；二是使用一個計數器記錄隊列中元素的總數（即隊列長度）。我們通常使用第一種方法，也就是少用一個元素的空間。
循環隊列相關操作思路
1.初始化： 造數組，設其數組長度為n=5(規定當數組中有n-1個元素時已滿)，初始化隊頭隊尾值都為0；
2.入隊
先判斷隊列是否已滿：（隊尾+1）%數組長度==隊頭 是否成立？即隊尾和隊頭緊挨著；
為隊尾的下一個元素賦值；
讓隊尾加1；
3.出隊
先判斷隊列是否為空：若隊首和隊尾相等，則該隊列一定為空（但隊首和隊尾值不一定為0，這個由初始化、入隊、出隊等相關操作後的數組下標位置決定）
保存一份要出隊的值；
讓隊頭加1；
實例說明
?<SPAN style="FONT-SIZE: 14px">#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Queue
{
int *pBase;//pBase指向數組名（通常靜態隊列都使用循環隊列）
int front;//數組下標，這裡規定從零開始
int rear;
}QUEUE;//QUEUE代表了struct Queue
void init(QUEUE *);//初始化
bool en_queue(QUEUE *,int);//入隊
bool full_queue(QUEUE *);//判斷循環隊列是否已滿
bool del_queue(QUEUE *,int *);//出隊
bool empty_queue(QUEUE *);//判斷循環隊列是否為空
bool traverse_queue(QUEUE *);//遍歷輸出
int length(QUEUE *);//求循環隊列的長度
int main()
{
QUEUE Q;
int val;
init(&Q);
en_queue(&Q,1);
en_queue(&Q,2);
en_queue(&Q,3);
en_queue(&Q,4);
traverse_queue(&Q);
if(del_queue(&Q,&val))
printf("出隊成功，出隊元素的值為：%d\n",val);
else
printf("出隊失敗！");
traverse_queue(&Q);
printf("隊列的長度為：%d\n",length(&Q));
return 0;
}
void init(QUEUE *pQ)
{
pQ->pBase=(int *)malloc(sizeof(int)*5);//造數組，設其數組長度為n=5（規定當數組中有n-1個元素時已滿），初始化時使Queue的成員front、rear的值都為0
if(NULL==pQ->pBase)
{
printf("動態內存分配失敗！\n");
exit(-1);
}
pQ->front=0;
pQ->rear=0;
}
bool full_queue(QUEUE *pQ)
{
if((pQ->rear+1)%5==pQ->front)
return true;
else
return false;
}
bool en_queue(QUEUE *pQ,int val)
{
if(full_queue(pQ))
{
printf("隊列已滿，入隊失敗！\n");
return false;
}
pQ->pBase[pQ->rear]=val;
pQ->rear=(pQ->rear+1)%5;//隊尾加1
return true;
}
bool del_queue(QUEUE *pQ,int *pVal)
{
if(empty_queue(pQ))
return false;
*pVal=pQ->pBase[pQ->front];
pQ->front=(pQ->front+1)%5;
return true;
}
bool empty_queue(QUEUE *pQ)
{
if(pQ->rear==pQ->front)//因為隊列不為空時，rear和front肯定不相等
return true;
else
return false;
}
bool traverse_queue(QUEUE *pQ)
{
int i=pQ->front;
if(empty_queue(pQ))
{
printf("隊列為空，遍歷失敗！\n");
return false;
}
printf("隊列元素有：");
while(i!=pQ->rear)
{
printf("%d ",pQ->pBase[i]);
i=(i+1)%5;
}
printf("\n");
return true;
}
int length(QUEUE *pQ)
{
int len=0;
int i=pQ->front;;
if(empty_queue(pQ))
return 0;//隊列為空，長度為0
while(i!=pQ->rear)
{
i=(i+1)%5;
++len;
}
return len;
}</SPAN>
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Queue
{
int *pBase;//pBase指向數組名（通常靜態隊列都使用循環隊列）
int front;//數組下標，這裡規定從零開始
int rear;
}QUEUE;//QUEUE代表了struct Queue
void init(QUEUE *);//初始化
bool en_queue(QUEUE *,int);//入隊
bool full_queue(QUEUE *);//判斷循環隊列是否已滿
bool del_queue(QUEUE *,int *);//出隊
bool empty_queue(QUEUE *);//判斷循環隊列是否為空
bool traverse_queue(QUEUE *);//遍歷輸出
int length(QUEUE *);//求循環隊列的長度
int main()
{
QUEUE Q;
int val;
init(&Q);
en_queue(&Q,1);
en_queue(&Q,2);
en_queue(&Q,3);
en_queue(&Q,4);
traverse_queue(&Q);
if(del_queue(&Q,&val))
printf("出隊成功，出隊元素的值為：%d\n",val);
else
printf("出隊失敗！");
traverse_queue(&Q);
printf("隊列的長度為：%d\n",length(&Q));
return 0;
}
void init(QUEUE *pQ)
{
pQ->pBase=(int *)malloc(sizeof(int)*5);//造數組，設其數組長度為n=5（規定當數組中有n-1個元素時已滿），初始化時使Queue的成員front、rear的值都為0
if(NULL==pQ->pBase)
{
printf("動態內存分配失敗！\n");
exit(-1);
}
pQ->front=0;
pQ->rear=0;
}
bool full_queue(QUEUE *pQ)
{
if((pQ->rear+1)%5==pQ->front)
return true;
else
return false;
}
bool en_queue(QUEUE *pQ,int val)
{
if(full_queue(pQ))
{
printf("隊列已滿，入隊失敗！\n");
return false;
}
pQ->pBase[pQ->rear]=val;
pQ->rear=(pQ->rear+1)%5;//隊尾加1
return true;
}
bool del_queue(QUEUE *pQ,int *pVal)
{
if(empty_queue(pQ))
return false;
*pVal=pQ->pBase[pQ->front];
pQ->front=(pQ->front+1)%5;
return true;
}
bool empty_queue(QUEUE *pQ)
{
if(pQ->rear==pQ->front)//因為隊列不為空時，rear和front肯定不相等
return true;
else
return false;
}
bool traverse_queue(QUEUE *pQ)
{
int i=pQ->front;
if(empty_queue(pQ))
{
printf("隊列為空，遍歷失敗！\n");
return false;
}
printf("隊列元素有：");
while(i!=pQ->rear)
{
printf("%d ",pQ->pBase[i]);
i=(i+1)%5;
}
printf("\n");
return true;
}
int length(QUEUE *pQ)
{
int len=0;
int i=pQ->front;;
if(empty_queue(pQ))
return 0;//隊列為空，長度為0
while(i!=pQ->rear)
{
i=(i+1)%5;
++len;
}
return len;
}
注意
1.指針只在入隊和出隊時移動，其它情況下不能移動。
2.隊列初始化：front和rear的值都是零；
3.隊列非空：front代表的是隊列的第一個元素，rear代表的是隊列的最後一個有效元素的下一個元素。
4.順序隊列和循環隊列最直觀的區別就是：循環隊列首尾相連形成一個圓環，而順序隊列不成環狀(通常會造成內存資源的浪費)。
5.隊列的應用非常廣泛，所有與時間有關的操作都可以用到隊列。
