注：不足及錯(cuò)誤請(qǐng)指正
+qq1366963396討論
隊(duì)列（queue）是只允許在一端進(jìn)行插入操作合瓢，而在另一端進(jìn)行刪除操作的線(xiàn)性表埋凯。
是一種先進(jìn)先出的線(xiàn)性表点楼。
一.循環(huán)隊(duì)列
struct Queue
{
????int data[MAXSIZE];
????int front;//頭指針
????int rear;//尾指針
};
循環(huán)隊(duì)列
如果不是循環(huán)隊(duì)列，出列是在隊(duì)頭白对，那么后面所有元素都必須向前移動(dòng)掠廓，可是為什么又要全部移動(dòng)呢，隊(duì)頭可以不在下標(biāo)為0的位置呀甩恼，但是如果一直再往隊(duì)尾插入蟀瞧，會(huì)導(dǎo)致隊(duì)列假溢出沉颂，也就是數(shù)組越界，而前面還有空閑的地方悦污。所以铸屉，我們想到用循環(huán)隊(duì)列，即隊(duì)列的頭尾相接的順序存儲(chǔ)結(jié)構(gòu)塞关。
但是又有問(wèn)題了抬探，什么時(shí)候表示為隊(duì)滿(mǎn)呢，rear==front?可是隊(duì)空的時(shí)候也是rear==front呀帆赢。所以有以下兩種辦法：
*****設(shè)置標(biāo)志量flag，當(dāng)front==rear&&flag=0時(shí)隊(duì)列為空线梗，front==reat&&flag=1時(shí)隊(duì)列為滿(mǎn)椰于。
*****還有就是可以保留一個(gè)元素空間，也就是說(shuō)仪搔，當(dāng)隊(duì)列滿(mǎn)時(shí)數(shù)組中還有一個(gè)空閑單元瘾婿，例如上圖所示就認(rèn)為隊(duì)列已滿(mǎn)，重點(diǎn)討論第二種辦法烤咧。
//初始化空隊(duì)列
void InitQueue(Queue* Q)
{
????Q->front = 0;
????Q->rear = 0;
}
//判隊(duì)空
bool IsEmpty(Queue* Q)
{
????if (Q->front ==Q->rear)
????????return true;
????return false;
}
//判隊(duì)滿(mǎn)
bool IsFull(Queue* Q)
{
????if ((Q->rear + 1) % MAXSIZE == Q->front)
????????return true;
????return false;
}
//求隊(duì)列長(zhǎng)度
int QueueLength(Queue* Q)
{
????return????(Q->rear - Q->front + MAXSIZE)%MAXSIZE;
}
//入隊(duì)
bool EnQueue(Queue* Q, int data)
{
????if (IsFull(Q))//判隊(duì)滿(mǎn)
????????return false;
????Q->data[Q->rear] = data;
????Q->rear = (Q->rear + 1) % MAXSIZE;//front后移
????return true;
}
//出隊(duì)
int DeQueue(Queue* Q, int data)
{
????if (IsEmpty(Q))//判隊(duì)空
????????return NULL;
????data = Q->data[Q->front];
????Q->front = (Q->front++) % MAXSIZE;//front后移
????return data;
}
//建隊(duì)
void CreatQueue(Queue* Q)
{
????InitQueue(Q);
????int data = 0;
????int i = 1; //計(jì)數(shù)
????while (1)
????{
????????printf("請(qǐng)輸入隊(duì)列第%d個(gè)元素:", i);
????????scanf("%d", &data);
????????if (data==-1||IsFull(Q))//隊(duì)滿(mǎn)-1表示結(jié)束
????????????break;
????????EnQueue(Q, data);//入隊(duì)
????????i++;
????}
}
二.鏈?zhǔn)酱鎯?chǔ)隊(duì)列
struct QueueNode//節(jié)點(diǎn)結(jié)構(gòu)
{
????int data;
????QueueNode* next;
};
struct LinkQueue//隊(duì)列的鏈表結(jié)構(gòu)
{
????QueueNode* front;//隊(duì)頭指針
????QueueNode* rear;//隊(duì)尾指針
};
//初始化空隊(duì)
void InitQueue(LinkQueue* Q)
{
????Q->front =Q->rear =(QueueNode*)malloc(sizeof(QueueNode));//生成頭結(jié)點(diǎn)
????Q->front->next= NULL;//置空隊(duì)
????Q->rear->next = NULL;
}
//置空隊(duì)
void SetEmptyQueue(LinkQueue* Q)
{
????Q->front->next = NULL;
????Q->front = Q->rear;
}
//判隊(duì)空
bool IsEmpty(LinkQueue* Q)
{
????if (Q->front == Q->rear)
????????return true;
????return false;
}
//求隊(duì)列長(zhǎng)度
int LengthQueuue(LinkQueue* Q,int length)
{
????QueueNode* p = Q->front->next;
????while (p)
????{
????????length++;
????????p = p->next;
????}
????return length;
}
//入隊(duì)
void EnQueue(LinkQueue* Q, int data)
{
????QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));//申請(qǐng)新節(jié)點(diǎn)
????newNode->data = data;
????newNode->next = NULL;
????Q->rear->next = newNode;//尾節(jié)點(diǎn)指向新節(jié)點(diǎn)
????Q->rear = newNode;//新節(jié)點(diǎn)成為尾節(jié)點(diǎn)
}
//出隊(duì)
int DeQueue(LinkQueue* Q, int data)
{
????if (IsEmpty(Q))//判隊(duì)空
????????return NULL;
????QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode));//申請(qǐng)p存放隊(duì)頭節(jié)點(diǎn)
????p = Q->front->next;
????data = p->data;//取得刪除的隊(duì)頭節(jié)點(diǎn)值
????Q->front->next = p->next;//頭結(jié)點(diǎn)指向刪除節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
????if (Q->rear == p)//若隊(duì)頭是隊(duì)尾偏陪，刪除后將rear指向頭結(jié)點(diǎn)
????????Q->rear = Q->front;
????free(p);
????return data;
}
//建隊(duì)
void CreatQueue(LinkQueue* Q)
{
????int data = 0;
????int i = 0;
????while (1)
????{
????????printf("請(qǐng)輸入第%d個(gè)元素:", ++i);
????????scanf("%d", &data);
????????if (data==-1)//-1表示結(jié)束
????????????break;
????????EnQueue(Q, data);//入隊(duì)
????}
}
應(yīng)用：球鐘問(wèn)題（棧和隊(duì)列）
基本程序與上文一致
球鐘問(wèn)題描述：球鐘是一個(gè)利用球的移動(dòng)來(lái)記錄時(shí)間的簡(jiǎn)單裝置。他有三個(gè)可以容納若干球的指示器：分鐘指示器煮嫌，五分鐘指示器笛谦，小時(shí)指示器。若分鐘指示器中有兩個(gè)球昌阿，5分鐘指示器中有6個(gè)球饥脑，小時(shí)指示器中有5個(gè)球，則時(shí)間為5:32.
工作原理：每過(guò)一分鐘懦冰，球鐘就會(huì)從球隊(duì)列的隊(duì)首取出一個(gè)球放入分鐘指示器灶轰，分鐘指示器可最多容納四個(gè)球。當(dāng)放入第五個(gè)球時(shí)刷钢，在分鐘指示器的4個(gè)球就會(huì)按照他們被放入時(shí)的相反順序加入球隊(duì)列的隊(duì)尾笋颤。而第五個(gè)球就會(huì)進(jìn)入分鐘指示器。依此類(lèi)推内地，五分鐘指示器最多可放11個(gè)球伴澄，小時(shí)指示器最多可放11個(gè)球。當(dāng)小時(shí)指示器放入第12個(gè)球時(shí)瓤鼻，原來(lái)的11個(gè)球按照他們被放入時(shí)的相反順序加入球隊(duì)列的隊(duì)尾秉版，然后第12個(gè)球也回到隊(duì)尾。這時(shí)三個(gè)指示器均為空茬祷，回到初始狀態(tài)清焕，從而形成一個(gè)循環(huán)。因此，該球鐘表示的時(shí)間范圍時(shí)從00：00到11：59秸妥；
bool TrueBallQueue(LinkQueue* Q)//是否與原來(lái)狀態(tài)相同
{
????QueueNode* p = Q->front->next;
????for (int i = 1; i <= 27; i++)
????{
????????if (p->data != i)
????????????return false;
????????p = p->next;
????}
????return true;
}
//主程序
int main()
{
????Stack* mStack = (Stack*)malloc(sizeof(Stack));//分鐘棧
????Stack* fmStack = (Stack*)malloc(sizeof(Stack)); //五分鐘棧
????Stack*hStack = (Stack*)malloc(sizeof(Stack));//小時(shí)棧
????LinkQueue* ballQueue = (LinkQueue*)malloc(sizeof(LinkQueue));球隊(duì)列
????int data=0;
????int time = 0;//記錄計(jì)滿(mǎn)次數(shù)
????//隊(duì)列滚停，棧初始化
????InitStack(mStack);//分鐘棧
????InitStack(fmStack);//五分鐘棧
????InitStack(hStack);//小時(shí)棧
????InitQueue(ballQueue);//球隊(duì)列
????//給隊(duì)列裝球
????int i = 0;
????for (i = 1; i <= 27; i++)
????{
????????EnQueue(ballQueue,i);
????}
????while (1)//從球隊(duì)列出球進(jìn)入分鐘指示器
????{
????????data = DeQueue(ballQueue,data);//球出隊(duì)
????????if (mStack->top == 3)//分鐘是否計(jì)滿(mǎn)
????????{
????????????int i = 0;
????????????int temp;
????????????//分鐘指示器的球進(jìn)入球隊(duì)列
????????????for (i = 0; i < 4; i++)
????????????{
????????????????temp = PopStack(mStack);
????????????????EnQueue(ballQueue, temp);
????????????}
????????????if (fmStack->top == 10)//5分鐘指示器是否計(jì)滿(mǎn)
? ? ? ? ? ? {
????????????//計(jì)滿(mǎn)退棧
????????????????for (i = 0; i < 11; i++)
????????????????{
????????????????????temp = PopStack(fmStack);
????????????????????EnQueue(ballQueue, temp);
????????????????}
????????????????if (hStack->top == 10)//小時(shí)指示器是否計(jì)滿(mǎn)
????????????????{
????????????????//計(jì)滿(mǎn)退棧
????????????????????for (i = 0; i < 11; i++)
????????????????????{
????????????????????????temp = PopStack(hStack);
????????????????????????EnQueue(ballQueue, temp);
????????????????????}
????????????????????EnQueue(ballQueue, data);
????????????????????time++;//計(jì)滿(mǎn)一次，即12小時(shí)
????????????????????if (TrueBallQueue(ballQueue))//回到初始狀態(tài)
????????????????????{
????????????????????????break;
????????????????????}
????????????????}
????????????????else
????????????????{
????????????????????PushStack(hStack, data);
????????????????}
????????????}
????????????else
????????????{
????????????????PushStack(fmStack, data);
????????????}
????????}
????????else
????????{
????????????PushStack(mStack, data);
????????}
????}
????time = (time * 12) / 24;
????printf("需要經(jīng)過(guò)%d天球隊(duì)列恢復(fù)初始狀態(tài)粥惧！\n", time);
????return 0;
}
