我們在使用手機(jī)的時候，偶爾都會碰到過卡住的時候，比如一個地方怎么點(diǎn)都沒有用，屏幕也卡住不顯示其他東西，但當(dāng)你把卡住的App關(guān)閉掉之后，手機(jī)的操作顯示就又恢復(fù)正常了，其實(shí)這就是因?yàn)椴僮飨到y(tǒng)中的各個程序的指令堆積在一起排隊(duì)執(zhí)行，而某一個App卡住的時候，大家都卡住了。

操作系統(tǒng)中是應(yīng)用了一種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)剛才提到的先到先執(zhí)行的排隊(duì)功能，這就是隊(duì)列。

隊(duì)列的定義

隊(duì)列是一種只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。

隊(duì)列是一種先進(jìn)先出（First In First Out）的線性表，簡稱FIFO。允許插入的一端為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。假設(shè)隊(duì)列 q = (q1,q2,q3,....qn)，那么我們一般定義q1就是隊(duì)頭，而qn自然為隊(duì)尾了。這樣我們在刪除操作時，就從q1開始，而插入操作時則從qn開始。這也比較符合我們的生活習(xí)慣，我們在排隊(duì)的時候，就是先到的人先出列，而晚到的人就在隊(duì)尾排隊(duì)。

循環(huán)隊(duì)列

以前的文章，我寫了線性表有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，而同樣，隊(duì)列作為一種特殊的線性表，自然也存在這兩種存儲方式。首先我們先來看隊(duì)列的順序存儲結(jié)構(gòu)。

隊(duì)列順序存儲結(jié)構(gòu)的不足

和線性表的順序存儲結(jié)構(gòu)的缺點(diǎn)一樣，隊(duì)列的若是采用常規(guī)的順序存儲結(jié)構(gòu)，那么它在插入和刪除時，每個元素都要依次向前或向后移動位置，此時的時間復(fù)雜度為O(n)。而當(dāng)隊(duì)列中隊(duì)頭之前的位置空出來，而隊(duì)尾的元素已滿時，明明在隊(duì)頭之前可能還有空間，但是按照順序存儲結(jié)構(gòu)的判斷，此時已經(jīng)不能插入數(shù)據(jù)，再插入數(shù)據(jù)的話，整個數(shù)組就會溢出，而這種之前有空位，卻插入到后面溢出位置的做法，我們稱為 假溢出 。

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

所以為了解決這種假溢出的辦法就是后面滿了，就再從頭開始，尋找之前空出來的空間，把數(shù)據(jù)存儲進(jìn)去，也就是頭尾相接的循環(huán)。我們把隊(duì)列這種頭尾相接的順序存儲結(jié)構(gòu)稱為循環(huán)隊(duì)列。

循環(huán)隊(duì)列的順序存儲結(jié)構(gòu)代碼如下：

#define MAXSIZE 10   //循環(huán)隊(duì)列的最大存儲空間

/**
 *  函數(shù)運(yùn)行狀態(tài)代碼
 */
#define SUCCESS 1
#define ERROR   0

typedef int Status ; //函數(shù)的運(yùn)行狀態(tài) 假設(shè)為int類型

typedef int QElemType; //QElemType的類型根據(jù)實(shí)際情況而定，這里假設(shè)為int

/**
 *  定義一個循環(huán)隊(duì)列
 */
typedef struct{
    
    QElemType data[MAXSIZE];
    
    int front; //循環(huán)隊(duì)列的頭指針
    
    int rear;  //循環(huán)隊(duì)列的尾指針
    
}sqQueue;

循環(huán)隊(duì)列的初始化代碼如下:

/**
 *  初始化一個循環(huán)隊(duì)列
 *
 *  @param Q 循環(huán)隊(duì)列的線性表
 *
 *  @return Status
 */

Status InitQueue (sqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
    
    return SUCCESS;
}

我們來實(shí)現(xiàn)求一個循環(huán)隊(duì)列的長度的功能，其實(shí)很簡單，只要返回尾指針與頭指針相減的數(shù)據(jù)就可以,當(dāng)然，這里我們要考慮當(dāng)循環(huán)了一遍之后頭尾交換位置的情況

/**
 *  求循環(huán)隊(duì)列的隊(duì)列長度
 *
 *  @param Q 循環(huán)隊(duì)列的線性表
 *
 *  @return length
 */
int QueueLength (sqQueue Q)
{
    return (Q.rear - Q.front +MAXSIZE) %MAXSIZE;
}

跟線性表一樣，我們一般要完成插入和刪除功能的代碼，而實(shí)現(xiàn)部分如下:

循環(huán)隊(duì)列的入隊(duì)列操作代碼:

/**
 *  循環(huán)隊(duì)列的入隊(duì)操作
 *
 *  @param Q 循環(huán)隊(duì)列的線性表
 *  @param e 將要插入的數(shù)據(jù)
 *
 *  @return Sataus
 */
Status EnQueue (sqQueue * Q ,QElemType e)
{
    if ((Q->rear + 1) %MAXSIZE == Q->front) {    //判斷隊(duì)列是否滿
        return ERROR;
    }
    
    Q->data[Q->rear] = e;              //將元素e賦值給隊(duì)尾
    Q->rear = (Q->rear + 1) %MAXSIZE;  //將rear尾指針后移一位
                                       //若到隊(duì)尾則轉(zhuǎn)到數(shù)組頭部
    return SUCCESS;
}

循環(huán)隊(duì)列的出隊(duì)列的操作代碼 :

/**
 *  循環(huán)隊(duì)列的出隊(duì)列操作
 *
 *  @param Q 循環(huán)隊(duì)列的線性表
 *  @param e 存儲隊(duì)頭數(shù)據(jù)的元素
 *
 *  @return Status
 */
Status DeQueue (sqQueue * Q, QElemType *e)
{
    if (Q->front == Q->rear) {               //判斷隊(duì)列是否為空
        return ERROR;
    }
    *e = Q->data[Q->front];                  //將隊(duì)頭元素賦值給e
    Q->front = (Q->front + 1) %MAXSIZE;      //front指針后移一位
    
    return SUCCESS;
}

從上面的代碼，我們能夠分析出，單是順序存儲，若不是循環(huán)隊(duì)列，算法的時間性能是不高的，但是循環(huán)隊(duì)列又面臨著數(shù)組可能會溢出的問題，所以我們還需要研究一下不需要擔(dān)心隊(duì)列長度的鏈?zhǔn)酱鎯Y(jié)構(gòu)。

隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實(shí)現(xiàn)

隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)，其實(shí)就是線性表的單鏈表，只不過它只能尾進(jìn)頭出而已，我們把它簡稱為鏈隊(duì)列。為了操作上的方便，我們將隊(duì)列的頭指針指向鏈隊(duì)列的頭結(jié)點(diǎn)，而尾指針指向終點(diǎn)結(jié)點(diǎn)。

空隊(duì)列時，front和rear都指向頭結(jié)點(diǎn)。

鏈隊(duì)列的結(jié)構(gòu)為:

/**
 *  結(jié)點(diǎn)結(jié)構(gòu)
 */
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
    
}QNode, *QueuePtr;

/**
 *  隊(duì)列的鏈表結(jié)構(gòu)
 */
typedef struct
{
    QueuePtr front, rear;    //隊(duì)頭隊(duì)尾指針
    
}LinkQueue;

鏈隊(duì)列的入隊(duì)操作:

/**
 *  插入元素e為鏈隊(duì)列的新的隊(duì)尾元素
 *
 *  @param Q 鏈隊(duì)列
 *  @param e 將要插入的元素e
 *
 *  @return Status
 */
Status EnLinkQueue (LinkQueue * Q, QElemType e)
{
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if (!s) {                    //存儲分配失敗
        return ERROR;
    }
    
    s->data = e;
    s->next = NULL;
    Q->rear->next = s;      //把擁有元素e的新節(jié)點(diǎn)s賦值給原隊(duì)尾結(jié)點(diǎn)的后繼
    
    Q->rear = s;            //把當(dāng)前的s設(shè)置為隊(duì)尾的結(jié)點(diǎn)，rear指向s
    return SUCCESS;
}

鏈隊(duì)列的出隊(duì)操作，其實(shí)就是頭結(jié)點(diǎn)的后繼結(jié)點(diǎn)出隊(duì)，將頭結(jié)點(diǎn)的后繼改成它后面的結(jié)點(diǎn)，之后再釋放要刪除元素的內(nèi)存，若鏈表除了頭結(jié)點(diǎn)之外只剩下一個元素時，則要將rear指向頭結(jié)點(diǎn)。

/**
 *  若隊(duì)列不空，刪除鏈隊(duì)列的隊(duì)頭元素，并用e返回其值
 *
 *  @param Q 鏈隊(duì)列
 *  @param e 刪除的元素的數(shù)據(jù)
 *
 *  @return Status
 */
Status DeLinkeQueue (LinkQueue *Q, QElemType *e)
{
    QueuePtr p;
    if (Q->front == Q->rear) {
        return ERROR;
    }
    
    p = Q->front->next;             //將欲刪除的隊(duì)頭結(jié)點(diǎn)暫存給p
    *e = p->data;                   //將欲刪除的隊(duì)頭結(jié)點(diǎn)賦值給e
    Q->front->next = p->next;       //將原隊(duì)頭的結(jié)點(diǎn)后繼p->next賦值給隊(duì)頭結(jié)點(diǎn)的后繼
    
    if (Q->rear == p) {             //若隊(duì)頭是隊(duì)尾，則刪除后繼后將rear指向頭結(jié)點(diǎn)
        Q->rear = Q->front;
    }
    free(p);                        //釋放p
    return SUCCESS;
}

循環(huán)隊(duì)列和鏈隊(duì)列的比較

循環(huán)隊(duì)列和鏈隊(duì)列的比較可以從兩個方面來比較，首先從時間上，其實(shí)它們的基本操作都是常數(shù)時間，時間復(fù)雜度都為O(1)，不過循環(huán)隊(duì)列是事先申請好空間的，而鏈隊(duì)列是即時申請空間的所以鏈隊(duì)列的每次申請和釋放操作都會帶來一定的性能消耗和時間開銷。

從空間上來說，循環(huán)隊(duì)列必須有一個固定的長度，所以就有了存儲元素個數(shù)和空間的浪費(fèi)的問題，而鏈隊(duì)列則不存在這個問題。

總得來說，在可以確定隊(duì)列長度最大值的情況下，建議用循環(huán)隊(duì)列，如果你無法預(yù)估隊(duì)列的長度時，則用鏈隊(duì)列。

總結(jié)

我們在這里的總結(jié)，將棧和隊(duì)列拿來比較。

• 棧（stack）是限定進(jìn)在表尾進(jìn)行插入和刪除操作的線性表
• 隊(duì)列（Queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。

他們均可以用線性表的順序存儲結(jié)構(gòu)來實(shí)現(xiàn)，但都存在著順序存儲的一些弊端，因此它們各自有各自的技巧來解決這個問題。

對于棧來說，如果存儲的數(shù)據(jù)類型相同的棧，則可以用數(shù)組的兩端作棧底的方法來讓兩個棧共享數(shù)據(jù)，這就可以最大化的利用數(shù)組的空間。

對于隊(duì)列來說，為了避免數(shù)組插入和刪除時需要移動數(shù)據(jù)，于是就引入了循環(huán)隊(duì)列，使得隊(duì)頭和隊(duì)尾可以在數(shù)組中循環(huán)變化。解決了移動數(shù)據(jù)的時間損耗，使得本來插入和刪除的時間復(fù)雜度從O(n)變成了O(1)。

它們也都可以通過鏈?zhǔn)酱鎯Y(jié)構(gòu)來實(shí)現(xiàn)，實(shí)現(xiàn)原則上與線性表基本相同。