C ~ 鏈式隊列與循環隊列

? ? ? 此處的鏈式與循環隊列可以應用于BFS和樹的層序遍歷。下面是對其結構和基本操作的程序描述。

1、循環隊列

? ? 解決循環隊列的隊空和隊滿的方法：

? ? [1].增加一個參數count，用來記錄數組中當前元素的個數；

? ? [2].為避免隊空和滿兩狀態混淆，少用一個存儲空間，也就是數組最后一個存數空間不用，（rear+1）% QSIZE= front 時, 隊滿;

? ? ? ?a）判斷是否為空隊列：front==rear； b)判斷隊列是否已滿：front=(rear+1)%size； ?

typedef struct{      //隊列結構定義
    int front;
    int rear;
    int count;  //隊列元素計數
    int key[QSIZE];
}BFSQueue;

void InitBFSQueue(BFSQueue *BFSQ)  //隊列初始化
{
    BFSQ->front=0;  //front指向隊列第一個元素
    BFSQ->rear=0;   //rear指向隊列中下一個空位
    BFSQ->count=0;
}
int EmptyBFSQueue(BFSQueue *BFSQ) //空
{
    return BFSQ->count==0;
}
int FullBFSQueue(BFSQueue *BFSQ)  //滿
{
    return BFSQ->count==QSIZE;
}

void AddBFSQueue(BFSQueue *BFSQ,int num)  //插入
{
    if(!FullBFSQueue(BFSQ))
    {
        BFSQ->count++;
        BFSQ->key[BFSQ->rear]=num;
        BFSQ->rear=(BFSQ->rear+1) % QSIZE;
    }
}

int DelBFSQueue(BFSQueue *BFSQ)  //刪除
{
    int temp;
    if(!EmptyBFSQueue(BFSQ))
    {
        BFSQ->count--;
        temp=BFSQ->key[BFSQ->front];
        BFSQ->front=(BFSQ->front+1) % QSIZE;
        return temp;
    }
    else
        return NULL;
}
/******************************************************************/

2、鏈式隊列

typedef struct QNode{  // 隊列元素結構  
    int key;
    struct QNode *next;
}QNode;
typedef struct{  // 隊列結構 
    QNode *front;
    QNode *rear;
    int count;
}BFSQueue;

void InitBFSQueue(BFSQueue *BFSQ)  //隊列初始化
{
    BFSQ->front=NULL;  
    BFSQ->rear=NULL; 
    BFSQ->count=0;
}
int EmptyBFSQueue(BFSQueue *BFSQ) //空
{
    return BFSQ->count==0;
}

void AddBFSQueue(BFSQueue *BFSQ,int num)  //插入
{
    QNode *np=(QNode *)malloc(sizeof(QNode));
    np->key=num;
    np->next=NULL;
      //BFSQ->count++;

    if(!EmptyBFSQueue(BFSQ))  // 隊列非空
    {        
        BFSQ->rear->next=np;
        BFSQ->rear=np;
    }
    else                      // 隊列空
    {
        BFSQ->rear=np;
        BFSQ->front=np;
    }
    BFSQ->count++;
}
int DelBFSQueue(BFSQueue *BFSQ)  //刪除
{
    int temp;
    QNode *tp=(QNode *)malloc(sizeof(QNode));
    if(!EmptyBFSQueue(BFSQ)) //隊列非空
    {
          //BFSQ->count--;  //注意，必須在隊列判定之后增加或減小count的值///
        tp=BFSQ->front;
        temp=tp->key;
        if(BFSQ->count==1)  //出隊后隊列為空
        {
            BFSQ->rear=NULL;
            BFSQ->front=NULL;
        }
        else  //出隊后隊列非空
        {
            BFSQ->front=tp->next;
        }        
        BFSQ->count--;
        free(tp);  //釋放暫存指針

        return temp;
    }
    else
        return NULL;
}