隊列的基本概念

1 隊列的定義

隊列（Queue）：隊列簡稱隊霹娄，也是一種操作受限的線性表翎苫，只允許在表的一端進行插入兔院，而在表的另一端進行刪除姿鸿。向隊列中插入元素稱為入隊或進隊谆吴；刪除元素稱為出隊或離隊。其操作的特性是先進先出（First In First Out,FIFO）苛预，故又稱為先進先出的線性表纪铺。
隊頭（Front）：允許刪除的一端，又稱為隊首碟渺。
隊尾（Rear）：允許插入的一端鲜锚。
空隊列：不含任何元素的空表。

2 隊列常見的基本操作

InitQueue(&Q)：初始化隊列苫拍，構(gòu)造一個空隊列Q芜繁。
QueueEmpty(Q)：判隊列空，若隊列Q為空返回true绒极，否則返回false骏令。
EnQueue(&Q,x)：入隊，若隊列Q未滿垄提，將x加入榔袋，使之稱為新的隊尾。
DeQueue(&Q,&x)：出隊铡俐，若隊列Q非空凰兑，刪除隊頭元素，并用x返回审丘。
GetHead(Q,&x)：讀隊頭元素吏够，若隊列Q非空，則將隊頭元素賦值給x滩报。

3 隊列的順序存儲結(jié)構(gòu)

1.隊列的順序存儲
隊列的順序?qū)崿F(xiàn)是指分配一塊連續(xù)的存儲單元存放隊列中的元素锅知，并附設(shè)兩個指針front和rear分別指示隊頭元素和隊尾元素的位置。設(shè)隊頭指針指向隊頭元素脓钾，隊尾指針指向隊尾元素的下一個位置售睹。
隊列的順序存儲類型可描述為

typedef struct {
    ElemType data[MAXSIZE];
    int front, rear;
} SqQueue;

初始狀態(tài)（隊空條件）：Q.front == Q.rear == 0
進隊操作：隊不滿時，先送值到隊尾元素可训，再將隊尾指針加1
出隊操作：隊不空時昌妹，先取隊頭元素的值生真，再將隊頭指針加1

2.循環(huán)隊列
將順序隊列臆造為一個環(huán)狀的空間，即把存儲隊列元素的表從邏輯上看成一個環(huán)捺宗，稱為循環(huán)隊列柱蟀。當(dāng)隊首指針Q.front = MaxSize - 1后，再前進一個位置就自動到0蚜厉，這可以利用除法取余運算（%）來實現(xiàn)长已。
初始時：Q.front == Q.rear == 0
隊首指針進1：Q.front = (Q.front + 1) % MaxSize
隊尾指針進1：Q.rear = (Q.rear + 1) % MaxSize
隊列長度：(Q.rear + MaxSize - Q.front) % MaxSize
出隊入隊時：指針都按順時針方向進1

為了區(qū)分隊空還是隊滿的情況，有三種處理方式：
1）犧牲一個單元來區(qū)分隊空和隊滿昼牛，入隊時少用一個隊列單元术瓮，這是一種較為普遍的做法，約定“隊頭指針在隊尾指針的下一位置作為隊滿的標(biāo)志”贰健。
隊滿條件為：(Q.rear + 1) % MaxSize == Q.front
隊空條件仍為：Q.front == Q.rear
隊列中元素的個數(shù)：(Q.rear - Q.front + MaxSize) % MaxSize

2）類型中增設(shè)表示元素個數(shù)的數(shù)據(jù)成員胞四。這樣，則隊空的條件為Q.size == 0伶椿；隊滿的條件為Q.size -- MaxSize辜伟。這兩種情況都有Q.front == Q.rear。

3）類型中增設(shè)tag數(shù)據(jù)成員脊另，以區(qū)分是隊滿還是隊空导狡。tag等于0的情況下，若因刪除導(dǎo)致Q.front == Q.rear則為隊空偎痛；tag等于1的情況下旱捧，若因插入導(dǎo)致Q.front == Q.rear則為隊滿。

3.循環(huán)隊列的操作
1）初始化

void InitQueue(SqQueue *Q) {
    Q->rear = Q->front = 0;
}

2）判隊空

int isEmpty(SqQueue *Q) {
    if (Q->rear == Q->front) {
        return 1;
    } else {
        return 0;
    }
}

3）入隊

int EnQueue(SqQueue *Q, ElemType x) {
//隊滿
    if ((Q->rear + 1) % MAXSIZE == Q->front) {
        return 0;
    }
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return 1;
}

4）出隊

int DeQueue(SqQueue *Q, ElemType x) {
    if (Q->rear == Q->front) {
        return 0;
    }
    x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return 1;
}

4 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)

1.隊列的鏈?zhǔn)酱鎯?br> 隊列的鏈?zhǔn)奖硎痉Q為鏈隊列踩麦，它實際上是一個同時帶有隊頭指針和隊尾指針的單鏈表枚赡。頭指針指向頭結(jié)點，尾指針指向尾結(jié)點谓谦，即單鏈表的最后一個結(jié)點（注意與順序存儲的不同）贫橙。
隊列的鏈?zhǔn)酱鎯擅枋鰹?/p>

typedef struct {
    ElemType data;
    struct LinkNode *next;
} LinkNode;

typedef struct {
    LinkNode *front, *rear;
} LinkQueue;

當(dāng)Q.front == NULL且Q.rear == NULL時，鏈?zhǔn)疥犃袨榭铡?br> 通常將鏈?zhǔn)疥犃性O(shè)計成一個帶頭結(jié)點的單鏈表茁计，這樣插入和刪除操作就統(tǒng)一了料皇。

2.鏈?zhǔn)疥犃械幕静僮?br> 1）初始化

void InitQueue(LinkQueue *Q) {
    //建立頭結(jié)點
    Q->front = Q->rear = (LinkNode *) malloc(sizeof(LinkNode));
    //初始為空
    Q->front->next = NULL;
}

2）判隊空

int IsEmpty(LinkQueue *Q) {
    if (Q->front == Q->rear) {
        return 1;
    } else {
        return 0;
    }
}

3）入隊

void EnQueue(LinkQueue *Q,ElemType x) {
      LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
      s->data = x;
      s->next = NULL;
      Q->rear->next = s;
      Q->rear = s;
}

4）出隊

int DeQueue(LinkQueue *Q, ElemType *x) {
    if (Q->front == Q->rear) {
        return ERROR;
    }
    LinkNode *p = Q->front;
    *x = p->data;
    Q->front->next = p->next;
    if (Q->rear == Q->front) {
        Q->rear = Q->front;
    }
    free(p);
    return OK;
}

5 雙端隊列

雙端隊列是指允許兩端都可以進行入隊和出隊操作的隊列谓松。其元素的邏輯仍是線性結(jié)構(gòu)星压。將隊列的兩端分別稱為前端和后端，兩端都可以入隊和出隊鬼譬。

在雙端隊列進隊時：前端進的元素排列在隊列中后端進的元素的前面娜膘，后端進的元素排列在隊列中前端進的元素的后面。
在雙端隊列出隊時：無論前端還是后端出隊优质，先出的元素排列在后出的元素的前面竣贪。
輸出受限的雙端隊列：允許在一端插入和刪除军洼，但在另一端只允許插入的雙端隊列稱為輸出受限的雙端隊列。