// 循環(huán)隊(duì)列的實(shí)現(xiàn)源碼：
#include"stdio.h"
#include"stdlib.h"
//這是一個(gè)靜態(tài)隊(duì)列的例程
#define MAXSIZE 10 //隊(duì)列的最大容量
typedef char ElemType; //定義一個(gè)隊(duì)列元素類型，這種編程思路很好，程序有擴(kuò)展空間
//聲明一個(gè)有關(guān)循環(huán)隊(duì)列的數(shù)據(jù)塊，注意每個(gè)元素的意義！
struct Queue
{
ElemType *base;//數(shù)據(jù)類型頭指針
int front; //隊(duì)頭（front）進(jìn)行隊(duì)列元素刪除操作的數(shù)組指針?biāo)饕�，很巧妙�?/div>
由于隊(duì)列有元素出列，front就向后移動(dòng)，所以隊(duì)列前面的空間就空了出來。為了更合理的利用空間，人們想了一個(gè)辦法：將隊(duì)列的首尾相連接。這樣當(dāng)rear移動(dòng)到front處時(shí)，會(huì)再從0開始循環(huán)。那當(dāng)什么時(shí)候隊(duì)列滿呢？當(dāng)rear等于front的時(shí)候�？墒顷�(duì)列為空的時(shí)候也是同樣的條件，那不就沒法判斷了嗎？又有人提出了這樣的想法：犧牲一個(gè)存儲(chǔ)空間，front前面不存數(shù)據(jù)，當(dāng)rear在front前面的時(shí)候就是滿了，如圖：
//////////////////////-------GKXW-----作者為本文付出很大心血，轉(zhuǎn)載請(qǐng)署名！-------////////////////////////////////
int rear; //隊(duì)尾（rear）進(jìn)行隊(duì)列元素插入操作的數(shù)組指針?biāo)饕�，很巧妙�?/div>
我想，看完本篇內(nèi)容uc/os-ii操作系統(tǒng)的“消息隊(duì)列”部分內(nèi)容就可以輕松理解了。關(guān)于循環(huán)隊(duì)列，我的理解是：既節(jié)省了內(nèi)存空間，同時(shí)在時(shí)間復(fù)雜度和空間復(fù)雜度上大大提高了效率。至于算法我們都是站在巨人的肩膀上學(xué)習(xí)學(xué)習(xí)再學(xué)習(xí)，很難想象如果沒有現(xiàn)成的代碼，我們要實(shí)現(xiàn)循環(huán)隊(duì)列的操作該有多難。 關(guān)于循環(huán)隊(duì)列算法真的非常精妙！學(xué)習(xí)本文能感受到C語言的魅力。
隊(duì)列是一種特殊的線性表，它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列。在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將是最先被刪除的元素；反之最后插入的元素將最后被刪除的元素，因此隊(duì)列又稱為“先進(jìn)先出”（FIFO—first in first out）的線性表。 隊(duì)列分為鏈?zhǔn)疥?duì)列和靜態(tài)隊(duì)列；靜態(tài)隊(duì)列一般用數(shù)組來實(shí)現(xiàn)，但此時(shí)的隊(duì)列必須是循環(huán)隊(duì)列，否則會(huì)造成巨大的內(nèi)存浪費(fèi)；鏈?zhǔn)疥?duì)列是用鏈表來實(shí)現(xiàn)隊(duì)列的。
};
//創(chuàng)建隊(duì)列或曰初始化隊(duì)列
void Queue_Iinit(Queue * q)
{
// q= new Queue;
q->base=(ElemType *)malloc(MAXSIZE*sizeof(ElemType));//
if(!q->base)
{
printf("內(nèi)存分配失敗！\n");
exit(1);
}
q->front=q->rear=0;
//這一步很重要！將隊(duì)頭和隊(duì)尾指針?biāo)饕齫->front，q->rea都賦值為0，即同時(shí)指向數(shù)組第一個(gè)元素
}
//入隊(duì)操作，入隊(duì)從隊(duì)尾rear處開始
void InsertQueue(Queue * q,ElemType e)
{
if((q->rear+1)%MAXSIZE==q->front)//先判斷隊(duì)列是否已滿,因?yàn)槿腙?duì)從隊(duì)尾rear處開始，所以先判斷rear指針?biāo)饕?/div>
///////////////////////////////////----GKXW------------2015年11月14日18:47:4/////////////////////////////////////////////////////*
表達(dá)式(q->rear+1)%MAXSIZE也叫取模運(yùn)算，該表達(dá)式能確保(q->rear+1)%MAXSIZE的結(jié)果小于MAXSIZE！
這樣可以確保數(shù)組指針不越界。為什么要rear加1呢？騰出一個(gè)數(shù)據(jù)的空閑空間。
這種算法很技巧！
*/
{
printf("隊(duì)列已滿！\n");
return;
}
q->base[q->rear]=e;//
q->rear=((q->rear+1)%MAXSIZE);//這一步既實(shí)現(xiàn)了指針前移同時(shí)還實(shí)現(xiàn)了指針不越界！技巧！
}
//出隊(duì)操作，出隊(duì)是從隊(duì)頭front處開始
void DeleteQueue(Queue * q,ElemType *e)
{
if(q->front==q->rear)//已空，說明隊(duì)列元素已經(jīng)刪除完畢
{
printf("老大，隊(duì)列已空！\n");
return;
}
// *(e++)=q->base[q->front];//完成此步還不夠！還需要指針?biāo)饕莆唬∽⒁赓x值方法！
*e=q->base[q->front];//完成此步還不夠！還需要指針?biāo)饕莆�！注意賦值方法！
q->front=(q->front+1)%MAXSIZE; //指針指向下一個(gè)空閑空間，確保不越界
}
//判斷隊(duì)列是否為空
bool EmptyQueue(Queue * q)
{
if(q->front==q->rear) //判斷是否為空
{
printf("隊(duì)列已空！\n");
return true;
}
else
return false;
}
//判斷隊(duì)列是否為滿
bool FullQueue(Queue * q)
{
if((q->rear+1)%MAXSIZE==q->front) //判斷循環(huán)鏈表是否滿，留一個(gè)預(yù)留空間不用
{
printf("隊(duì)列已滿！\n");
return true;
}
else
return false;
}
/***********************************************
輸出每一個(gè)元素
************************************************/
void TraverseQueue(Queue * q)
{
int i=q->front;
printf("隊(duì)中的元素是:\n");
while( (i%MAXSIZE)!=q->rear ) //注意，這里沒有加1，打印每一個(gè)元素
{
printf("%c\n ",q->base[i]);
i++;
}
printf("\n");
}
void main()
{
Queue q;
char c;
Queue_Iinit(&q);
printf("請(qǐng)輸入循環(huán)隊(duì)列元素，以#作為結(jié)束符\n");
scanf("%c",&c);//注意！本句表示一次輸入一個(gè)字符
InsertQueue(&q,c);
/*
注意：比如輸入“1110010#”再按下回車鍵，字符串“1110010#”就以一次一個(gè)字符的順序輸入到PC鍵盤緩沖區(qū)即入棧；
出棧時(shí)是以“后進(jìn)先出”的順序出棧，剛好最后入棧的字符就是二進(jìn)制的最低位。對(duì)于棧的操作一定要注意入棧出棧順序
*/
while(c!='#')
{
scanf("%c",&c);//這里為什么還要此句呢？因?yàn)閟canf()一次只能輸入一個(gè)字符，所以必須循環(huán)輸入
InsertQueue(&q,c);
}
getchar();//改變鍵盤輸入緩存指針，即將回車鍵讀出來，這樣可以避免“\r”字符（回車鍵）輸出
TraverseQueue(&q);
printf("開始出隊(duì)命令！\n");
while(1)
{
DeleteQueue(&q,&c);
printf("出隊(duì)：%c\n ",c);
if( EmptyQueue( &q))
break;
}
}
我想，看完本篇內(nèi)容uc/os-ii操作系統(tǒng)的“消息隊(duì)列”部分內(nèi)容就可以輕松理解了。關(guān)于循環(huán)隊(duì)列，我的理解是：既節(jié)省了內(nèi)存空間，同時(shí)在時(shí)間復(fù)雜度和空間復(fù)雜度上大大提高了效率。至于算法我們都是站在巨人的肩膀上學(xué)習(xí)學(xué)習(xí)再學(xué)習(xí)，很難想象如果沒有現(xiàn)成的代碼，我們要實(shí)現(xiàn)循環(huán)隊(duì)列的操作該有多難。 關(guān)于循環(huán)隊(duì)列算法真的非常精妙！學(xué)習(xí)本文能感受到C語言的魅力。
隊(duì)列是一種特殊的線性表，它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列。在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將是最先被刪除的元素；反之最后插入的元素將最后被刪除的元素，因此隊(duì)列又稱為“先進(jìn)先出”（FIFO—first in first out）的線性表。 隊(duì)列分為鏈?zhǔn)疥?duì)列和靜態(tài)隊(duì)列；靜態(tài)隊(duì)列一般用數(shù)組來實(shí)現(xiàn)，但此時(shí)的隊(duì)列必須是循環(huán)隊(duì)列，否則會(huì)造成巨大的內(nèi)存浪費(fèi)；鏈?zhǔn)疥?duì)列是用鏈表來實(shí)現(xiàn)隊(duì)列的。
由于隊(duì)列有元素出列，front就向后移動(dòng)，所以隊(duì)列前面的空間就空了出來。為了更合理的利用空間，人們想了一個(gè)辦法：將隊(duì)列的首尾相連接。這樣當(dāng)rear移動(dòng)到front處時(shí)，會(huì)再從0開始循環(huán)。那當(dāng)什么時(shí)候隊(duì)列滿呢？當(dāng)rear等于front的時(shí)候�？墒顷�(duì)列為空的時(shí)候也是同樣的條件，那不就沒法判斷了嗎？又有人提出了這樣的想法：犧牲一個(gè)存儲(chǔ)空間，front前面不存數(shù)據(jù)，當(dāng)rear在front前面的時(shí)候就是滿了，如圖：
//////////////////////-------GKXW-----作者為本文付出很大心血，轉(zhuǎn)載請(qǐng)署名！-------////////////////////////////////
| 歡迎光臨 (http://www.torrancerestoration.com/bbs/) | Powered by Discuz! X3.1 |