（一）循環隊列
來源：程序員人生 發布時間：2015-03-23 08:22:41 閱讀次數：3489次
隊列可使用數組或鏈表實現，這里介紹1種使用數組實現的循環隊列。
所謂循環隊列，是指當尾指針超過數組索引界限時，通過取余運算返回數組起始端，只要保證尾指針和頭指針不相遇，就能夠繼續存儲元素。
首先設定隊列的大小，并建立隊列結構體：
#define MAXSIZE 100001
typedef struct {
int items[MAXSIZE];
int front;
int rear;
}Queue;
設頭指針和尾指針指向同1索引時隊列為空，起始時均在索引0處。
void initQueue(Queue *q){
q->front = q->rear = 0;
}
入隊操作是先檢查rear指針前進后是不是會和front指針相遇，如果會相遇則直接返回，并輸出毛?。宏犃幸褲M。
注意要對MAXSIZE取余，實現循環：
void AddQ(Queue *q, int item){
if ((q->rear + 1)%MAXSIZE == q->front)
{
// 為了辨別空隊列與滿隊列，必須保證rear和front不能再次碰面，因此要留出1個距離，提早判斷是不是添加后front=rear。
printf("隊列滿");
return;
}
q->rear = (q->rear + 1) % MAXSIZE;
*(q->items + q->rear) = item;
}
出隊操作是先檢查front和rear是不是相等，否則隊列為空，如果不空，則先將front后移，然后將front位置的元素返回：
int DeleteQ(Queue *q){
if (q->rear == q->front)
{
printf("隊列空");
return NULL;
}
q->front = (q->front + 1) % MAXSIZE;
return *(q->items + q->front);
}
注意入隊是先判斷后移是不是相遇來判斷是不是為滿再履行操作，操作方法為指針后移然后在指針處存入元素；出隊時是先判斷是不是相遇來判斷是不是為空，操作方法為指針后移然后在指針處存入元素。
在先移動指針再操作指針處元素、rear和front相等為空這兩個約定下，可以實現循環隊列。
完全代碼為：
#define MAXSIZE 100001
typedef struct {
int items[MAXSIZE];
int front;
int rear;
}Queue;
void initQueue(Queue *q){
q->front = q->rear = 0;
}
bool isEmpty(Queue *q){
return q->front == q->rear;
}
void AddQ(Queue *q, int item){
if ((q->rear + 1)%MAXSIZE == q->front)
{
// 為了辨別空隊列與滿隊列，必須保證rear和front不能再次碰面，因此要留出1個距離，提早判斷是不是添加后front=rear。
printf("隊列滿");
return;
}
q->rear = (q->rear + 1) % MAXSIZE;
*(q->items + q->rear) = item;
}
int DeleteQ(Queue *q){
if (q->rear == q->front)
{
printf("隊列空");
return NULL;
}
q->front = (q->front + 1) % MAXSIZE;
return *(q->items + q->front);
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
