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