1.隊(duì)列的概念

在開(kāi)始前，請(qǐng)牢記這句話(huà)：隊(duì)列是一個(gè)先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。

隊(duì)列（queue）是限定在表的一端進(jìn)行插入，表的另一端進(jìn)行刪除的數(shù)據(jù)結(jié)構(gòu)，如同棧的學(xué)習(xí)，請(qǐng)聯(lián)系前文所學(xué)鏈表，試想一個(gè)單鏈表，我們只能對(duì)他的鏈表表尾進(jìn)行插入，而只能對(duì)鏈表的表頭進(jìn)行結(jié)點(diǎn)的刪除，其余一切的操作均不允許，這樣強(qiáng)限制性的“鏈表“，就是我們所說(shuō)的隊(duì)列。

讓我們重新理順一下定義：隊(duì)列是一個(gè)線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)，規(guī)定這個(gè)數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行插入，另一端進(jìn)行刪除，禁止直接訪(fǎng)問(wèn)除這兩端以外的一切數(shù)據(jù)。

如圖：隊(duì)列就像一個(gè)兩端相通的水管，只允許一端插入，另一端取出，先放入管中的球先從管中拿出。

2. 隊(duì)列的結(jié)點(diǎn)設(shè)計(jì)與初始化

隊(duì)列不如棧那般方便進(jìn)行模擬，因此隊(duì)列只有鏈?zhǔn)降脑O(shè)計(jì)方法，但是不同的是，隊(duì)列本身分為多種隊(duì)列，如順序隊(duì)列（就是此文所講隊(duì)列）和循環(huán)隊(duì)列（下一篇文章所講），以及后文在C++STL章中會(huì)提到的優(yōu)先隊(duì)列等等，均來(lái)自于隊(duì)列的衍生。

我們以順序隊(duì)列的設(shè)計(jì)為例。

首先是隊(duì)列的結(jié)點(diǎn)設(shè)計(jì)，我們可以設(shè)計(jì)出兩個(gè)結(jié)構(gòu)體，一個(gè)結(jié)構(gòu)體Node表示結(jié)點(diǎn)，其中包含有一個(gè)data域和next指針（可以發(fā)現(xiàn)，這樣的結(jié)點(diǎn)設(shè)計(jì)我們已經(jīng)重復(fù)出現(xiàn)了很多次了，正是因?yàn)檫@樣的結(jié)構(gòu)設(shè)計(jì)方便理解）。

（圖表示結(jié)點(diǎn)）

其中data表示數(shù)據(jù)，其可以是簡(jiǎn)單的類(lèi)型（如int,double等等），也可以是復(fù)雜的結(jié)構(gòu)體（struct類(lèi)型）。

next指針表示，下一個(gè)的指針，其指向下一個(gè)結(jié)點(diǎn)，通過(guò)next指針將各個(gè)結(jié)點(diǎn)鏈接。

如同棧再次設(shè)計(jì)一個(gè)結(jié)構(gòu)體進(jìn)行限制性設(shè)計(jì)，接著，我們也額外添加一個(gè)結(jié)構(gòu)體，其包括了兩個(gè)分別永遠(yuǎn)指向隊(duì)列的隊(duì)尾和隊(duì)頭的指針，我們主要的操作只對(duì)這兩個(gè)指針進(jìn)行操作。

（圖表示隊(duì)列設(shè)計(jì)）

其結(jié)構(gòu)體設(shè)計(jì)的代碼可以表示為：

//結(jié)點(diǎn)定義
typedef struct node{
    int data;
    struct node *next;
}node;
//隊(duì)列定義，隊(duì)首指針和隊(duì)尾指針
typedef struct queue{
    node *front;    //頭指針
    node *rear;     //尾指針
}queue;

有關(guān)初始化，稍微復(fù)雜一點(diǎn)的是，我們對(duì)于初始化需要初始化兩個(gè)類(lèi)型，一個(gè)是初始化結(jié)點(diǎn)，一個(gè)是初始化隊(duì)列，初始化隊(duì)列稍微有些不同，那就是當(dāng)初始化隊(duì)列的時(shí)候，需要將頭尾兩個(gè)結(jié)點(diǎn)指向的內(nèi)容統(tǒng)統(tǒng)制空，表示是一個(gè)空隊(duì)列，兩個(gè)創(chuàng)建的函數(shù)代碼可以表示為：

//初始化結(jié)點(diǎn)
node *init_node(){
    node *n=(node*)malloc(sizeof(node));
    if(n==NULL){    //建立失敗，退出
        exit(0);
    }
    return n;
}
 
//初始化隊(duì)列
queue *init_queue(){
    queue *q=(queue*)malloc(sizeof(queue));
    if(q==NULL){    //建立失敗，退出
        exit(0);
    }
    //頭尾結(jié)點(diǎn)均賦值NULL
    q->front=NULL;  
    q->rear=NULL;
    return q;
}

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

判斷隊(duì)列是否為空比較簡(jiǎn)單，直接就是判斷隊(duì)列頭指針是否是空值即可（關(guān)聯(lián)如何創(chuàng)建隊(duì)列可更好理解），判斷隊(duì)列是否為空是比較常用的操作。

其代碼可以表示為：

//隊(duì)列判空
int empty(queue *q){
    if(q->front==NULL){
        return 1;   //1--表示真，說(shuō)明隊(duì)列非空
    }else{
        return 0;   //0--表示假，說(shuō)明隊(duì)列為空
    }
}

或者直接利用返回值進(jìn)行更簡(jiǎn)單的判斷（兩者效果完全一樣）

int empty(queue *q){
    return q->front==NULL;
}