靜態(tài)循環(huán)隊列幾個問題
1.靜態(tài)隊列為什么必須是循環(huán)隊列?
因為不管是入隊還是出隊,front和rear都是增長的,靜態(tài)隊列使用的是數(shù)組來存放入隊的數(shù)據(jù),由于front和rear都是增長的,那么后方就會騰出空余的空間,為了重復(fù)利用,只能將front和rear增長到數(shù)組的末尾的時候,將值重新設(shè)置為數(shù)組第一個元素的位置.
2.循環(huán)隊列需要幾個參數(shù)來確定?
首先定義一個循環(huán)隊列的結(jié)構(gòu)體
typedef struct{
int length;
int * a;
int r;//隊尾,入隊數(shù)據(jù)向隊尾添加
int f;//隊頭,出隊從隊頭出隊
int isFlag;//標(biāo)記這個隊列是否已滿,0表示為空隊列,1表示未滿,2表示已滿
}LoopQueue,*PLoopQueue;
3.循環(huán)隊列的各個參數(shù)的含義?
- length 隊列最多能同時入隊的元素有多少個(隊列的大小)
- a 指向一個指定大小的數(shù)組(通過malloc分配的一個length大小的數(shù)組)
- r 循環(huán)隊列的隊尾(入隊的地方)
- f 循環(huán)隊列的隊頭(出隊的地方)
- isFlag 標(biāo)記當(dāng)前循環(huán)隊列的:EMPTY(空),UNDER(不為空也沒滿),FULL(已滿)
4.初始化隊列
- 創(chuàng)建一個LoopQueue結(jié)構(gòu)體變量
- 申請 length*sizeof(int) 的空間,并賦值給a
- 將r,f都設(shè)置成0
- 將isFlag設(shè)置成EMPTY
5.循環(huán)隊列入隊偽算法?
- 判滿(因為是入隊,當(dāng)隊滿的時候,無法再繼續(xù)入隊)
- return false
- 否則隊列未滿,執(zhí)行入隊操作
- 將val賦值給數(shù)組位置為r的空間
- 將r加一并與length取余(這樣就能非常簡單的實現(xiàn)循環(huán))的結(jié)果賦值給r
- 判斷隊列的狀態(tài)
- 如果r == f(隊頭隊尾在數(shù)組同一位置了,由于是入隊操作導(dǎo)致r == f,所以只能是隊已滿),此時說明隊列已滿 isFlag 設(shè)置為 Full
- 否則 isFlag 設(shè)置為 UNDER(因為剛?cè)腙犚粋€元素,肯定不能是EMPTY)
- return true
6.循環(huán)隊列出隊偽算法?
- 判空(因為是出隊,當(dāng)隊列為空的時候,出隊失敗)
- return false
- 否則不為空,執(zhí)行出隊操作
- 將數(shù)組f位置的空間的值賦值給 *val
- 將f加一并與length取余的結(jié)果賦值給f
- 判斷隊列的狀態(tài)
- 如果f==r(此時是出隊操作,只有可能是隊列為空了),說明隊列為空,將isFlag設(shè)置為EMPTY
- 否則設(shè)置為UNDER,因為剛出隊一個,不可能此時是 Full 了
- return true
程序?qū)崿F(xiàn)
#include <stdio.h>
#include <stdlib.h>
#define EMPTY 0
#define UNDER 1
#define FULL 2
/**
* 循環(huán)隊列
*/
typedef struct{
int length;
int * a;
int r;//隊尾,入隊數(shù)據(jù)向隊尾添加
int f;//隊頭,出隊從隊頭出隊
int isFlag;//標(biāo)記這個隊列是否已滿,0表示為空隊列,1表示未滿,2表示已滿
}LoopQueue,*PLoopQueue;
/**
* 創(chuàng)建一個循環(huán)隊列,默認(rèn)大小是5
* @param length [description]
* @return [description]
*/
LoopQueue createLoopQueue(int length){
LoopQueue l;
if (length<5){
length=5;
}
l.length=length;
l.a=(int *)malloc(length*sizeof(int));
l.r=0;
l.f=0;
l.isFlag=EMPTY;
return l;
}
/**
* 入隊,入隊成功返回1,失敗返回0
* @param pL [description]
* @param val [description]
* @return [description]
*/
int enqueue(PLoopQueue pL,int val){
if (pL->isFlag == FULL){
//隊列已滿,無法再添加數(shù)據(jù)
return 0;
}else{
//否則的話就將當(dāng)前a數(shù)組的r所對應(yīng)的位置用來存儲值
(pL->a)[pL->r]=val;
//r的位置向前移動一次
//被坑的最慘的一次,后加加,使用之后加,在這兒必須使用前 pL->r + 1
pL->r = (pL->r + 1 ) % (pL->length);
//判斷當(dāng)前這個循環(huán)隊列的狀態(tài),因為是如隊,所以接下來添加一個元素的可能狀態(tài)是,UNDER(未滿),或者是FULL(滿)
if (pL->r==pL->f){
//說明此時的隊列已經(jīng)裝滿了
pL->isFlag = FULL;
}else{
//說明此時的隊列還沒有裝滿
pL->isFlag = UNDER;
}
return 1;
}
}
/**
* 出隊
* @param pL [description]
* @param val [description]
* @return [description]
*/
int dequeue(PLoopQueue pL,int * val){
if (pL->isFlag==EMPTY){
//隊列為空,無法再出隊
return 0;
}else{
//取值
*val=pL->a[pL->f];
//將值清除
pL->a[pL->f]=0;
//f向前移動
pL->f =( pL->f + 1 ) % pL->length;
//判斷當(dāng)前這個循環(huán)隊列的狀態(tài),因為是出隊,所以接下來移除一個元素的可能狀態(tài)是,UNDER(未滿),或者是EMPTY(空)
if (pL->f == pL->r){
//此時全部出隊了,當(dāng)前的隊列為空
pL->isFlag = EMPTY;
}else{
pL->isFlag = UNDER;
}
return 1;
}
}
int main(){
LoopQueue loopQueue=createLoopQueue(50);
int i,flag;
int temp;
for(i=0;i<60;i++){
flag=enqueue(&loopQueue,i);
if(flag){
printf("入隊%d\n", i);
}else{
printf("隊列已滿\n");
}
}
while(dequeue(&loopQueue,&temp)){
printf("出隊%d\n", temp);
}
return 0;
}
