C語言數(shù)據(jù)結(jié)構(gòu)算法基礎(chǔ)之循環(huán)隊(duì)列示例

第C語言數(shù)據(jù)結(jié)構(gòu)算法基礎(chǔ)之循環(huán)隊(duì)列示例目錄說明示例代碼1.首先定義結(jié)構(gòu)體：2.定義各種算法：3.測試：4.最后的結(jié)果：

說明

循環(huán)隊(duì)列是一種先進(jìn)先出的，首尾相連的隊(duì)列。

大致的結(jié)構(gòu)如下圖：

用數(shù)組來抽象的表示一下的話，如下圖：

循環(huán)隊(duì)列有兩個(gè)指針指向數(shù)據(jù)，上圖中的start和end就是那兩個(gè)指針，它們指向相同的位置，表示的是空，即隊(duì)列是空的。

隨著數(shù)據(jù)的放入，隊(duì)列一般有下面的兩種形式：

需要注意第二種形式，從圖上看end在start的前面了，但是因?yàn)檠h(huán)關(guān)系，前后并不重要。

另外需要考慮的是隊(duì)列滿的情況：

但這種情況存在一個(gè)問題，即空隊(duì)列和滿隊(duì)列沒有辦法區(qū)分了，end和start都指向了相同的位置。

為了解決這個(gè)問題，一個(gè)方法是空出一個(gè)位置不放數(shù)據(jù)，當(dāng)end再加一個(gè)數(shù)據(jù)就等于start的時(shí)候就認(rèn)為隊(duì)列是滿的：

這時(shí)實(shí)際的數(shù)據(jù)長度就會比分配的少1。

下面是隊(duì)列中空和滿的判斷：

1.隊(duì)列為空時(shí)：end==start

2.隊(duì)列為滿時(shí)：(end+1)%size==start

這里的size是指分配的空間大小，而不是隊(duì)列長度，隊(duì)列的實(shí)際長度為(end-start+size)%size，最大長度是size-1

這也是因?yàn)橐紤]循環(huán)的關(guān)系，所以要加上%size這個(gè)操作。

示例代碼

1.首先定義結(jié)構(gòu)體：

//定義循環(huán)隊(duì)列

typedefstruct_LoopQueue{

intdata[8];//存放數(shù)據(jù)

intstart;//頭指針

intend;//尾指針

}LoopQueue;

2.定義各種算法：

#defineTRUE1

#defineFALSE0

#defineSIZE8

//初始化隊(duì)列

intinit(LoopQueue*lq){

lq-start=0;

lq-end=0;

returnTRUE;

//判斷隊(duì)列是否為空

intisEmpty(LoopQueue*lq){

if(lq-start==lq-end){

returnTRUE;

returnFALSE;

//判斷隊(duì)列是否為滿

intisFull(LoopQueue*lq){

if((lq-end+1)%SIZE==lq-start){

returnTRUE;

returnFALSE;

//獲取隊(duì)列的長度

intgetLength(LoopQueue*lq){

return(lq-end-lq-start+SIZE)%SIZE;

//插入數(shù)據(jù)

intpushQueue(LoopQueue*lq,intdata){

if(isFull(lq)){

printf("Queueisfull.\n");

returnFALSE;

lq-data[lq-end]=data;

lq-end=(lq-end+1)%SIZE;

returnTRUE;

//彈出數(shù)據(jù)

intpopQueue(LoopQueue*lq,int*data){

if(isEmpty(lq)){

printf("Queueisempty.\n");

returnFALSE;

*data=lq-data[lq-start];

lq-start=(lq-start+1)%SIZE;

returnTRUE;

//顯示隊(duì)列中的數(shù)據(jù)

voidprintQueue(LoopQueue*lq){

intindex;

intcount;

count=getLength(lq);

if(0==count){

printf("Nodata.\n");

return;

for(index=0;indexcount;index++){

printf("%d",lq-data[index]);

printf("\n");

return;

}

3.測試：

intmain()

intindex;

intnum;

//隊(duì)列測試代碼

LoopQueue*lq=(LoopQueue*)malloc(sizeof(LoopQueue));

init(lq);

printQueue(lq);

for(index=0;indexSIZE;index++){//注意這里要放8個(gè)數(shù)據(jù)，但是實(shí)際上只能放7個(gè)，所以最后一個(gè)會報(bào)錯(cuò)

pushQueue(lq,index);

printQueue(lq);

for(index=0;indexSIZE;index++){//同上，會打印一個(gè)錯(cuò)誤

if(popQueue(lq,num)){

printf("%d\n",