隊列

隊列的基本概念

隊列是一種操作受限的線性表，只允許在表的一端進行插入，而在表的另一端進行刪除；向隊列中插入元素稱為入隊或者進隊，刪除元素稱為出隊或者離隊；隊列的操作特性是先進先出

• 隊頭：允許刪除的一端，又稱為隊首
• 隊尾：允許插入的一段
• 空隊列：不含任何元素的空表

隊列常見的基本操作

隊列常見的基本操作主要有構(gòu)造一個空隊列InitQueue(&Q)、判斷隊列為空QueueEmpty(Q)、入隊EnQueue(&Q,x)、出隊DeQueue(&Q,&x)、讀隊頭元素GetHead(Q,&x)

需要注意的是，隊列是操作受限的線性表，因此不是所有對線性表的操作都可以作為隊列的操作，比如，不可以隨便讀取隊列中間的某個數(shù)據(jù)

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

隊列的順序?qū)崿F(xiàn)是指分配一塊連續(xù)的存儲單元存放隊列中的元素，并設(shè)置兩個指針front和rear分別指向隊頭元素和隊尾元素的位置；設(shè)隊頭指針指向隊頭元素，隊尾指針指向隊尾元素的下一個位置

#define MaxSize 50      //定義隊列中元素的最大個數(shù)
typedef struct{
    ElemType data[MaxSize];
    int front,rear;     //定義隊頭指針和隊尾指針
} SqQueue;

初始條件（隊空條件）：Q.front = 0,Q.rear = 0（隊尾的下一個位置等于0，即隊尾位置等于-1，隊列為空
進隊操作：隊列不滿時，先送值到隊尾元素，再將隊尾指針加一
出隊操作：隊列不為空時，先彈出隊頭元素值，再將隊頭指針加一

d注意：Q.rear == MaxSize并不能作為隊列已滿的條件，因為即使經(jīng)過多次的進隊、出隊，即使隊尾指針Q.rear已經(jīng)達到了MaxSize的位置，但是隊頭指針同樣可能變化，使隊頭發(fā)生后移，導(dǎo)致data數(shù)組中仍然存在可以存放元素的空位置，實際上是一種“假溢出”，這也是順序隊列的一種缺點。

循環(huán)隊列

前面說，順序隊列的缺點是對隊頭元素的刪除操作會導(dǎo)致data數(shù)組中仍然存在未被利用的隊頭空間，甚至出現(xiàn)“假溢出現(xiàn)象”，循環(huán)隊列解決了這種問題；將順序隊列臆造成為一個環(huán)狀的空間，即把存儲隊列的線性表從邏輯上視為一個環(huán)，稱為循環(huán)隊列。

在循環(huán)隊列中，當隊首指針為MaxSize-1時，其下一個位置為0；循環(huán)隊列依靠除法的取余操作實現(xiàn)。

• 初始時：頭結(jié)點的位置指針Q.front=0，指向尾結(jié)點下一個元素位置的指針Q.rear=0
• 隊首指針進1：Q.front=(Q.front+1)%MaxSize
• 隊尾指針進1：Q.rear=(Q.rear+1)%MaxSize
• 隊列長度：(Q.rear+MaxSize-Q.front)%MaxSize (保證正數(shù)？？？)
• 出隊入隊時，指針都向順時針方向加1

判斷循環(huán)隊列隊滿或者隊空時會發(fā)現(xiàn)，循環(huán)隊列隊空的條件為Q.front==Q.rear，和普通隊列一致；但循環(huán)隊列隊滿時，由于Q.rear指向隊末元素的下一個位置，條件仍然是Q.front==Q.rear，因此為了區(qū)分隊空還是隊滿，有幾種處理方式；

1.犧牲一個單元來區(qū)分隊空和隊滿，入隊時少用一個隊列單元；約定以隊頭指針指向隊尾指針指向的下一個位置作為隊滿的標志；

• 隊滿條件：（Q.rear+1)%MaxSize==Q.front
• 隊空條件：Q.rear==Q.front
• 隊列中元素的個數(shù)Q.rear-Q.front+MaxSize)%MaxSize(當Q.rear-Q.front為正數(shù)時，和Q.rear-Q.front等價；當Q.rear越過0的位置，變成一個小于Q.front的值時，加上MaxSize使整個值非負，便于取余數(shù))

2.類型中新增表示元素個數(shù)的數(shù)據(jù)成員Q.size，無視Q.rear==Q.front這一判別條件；這樣循環(huán)隊列的判空條件為Q.size==0，隊滿的判定條件為Q.size==MaxSize-1；對于這兩種情況，都有Q.rear==Q.front

3.類型中增加Q.tag成員，通過記錄導(dǎo)致Q.rear==Q.front的原因區(qū)分隊滿還是隊空；若因刪除導(dǎo)致Q.rear==Q.front，則為隊空，記錄為tag等于0；若因插入導(dǎo)致Q.rear==Q.front，則為隊滿，記錄為tag等于1

循環(huán)隊列的操作

初始化

void InitQueue(SqQueue &Q){
    Q.rear = Q.front = 0;  //初始化隊首、隊尾指針為0
}

判隊空

bool isEmpty(SqQueue Q){
    if (Q.rear == Q.front)  //隊空條件
        return true;
    else
        return false;
}

入隊

bool EnQueue(SqQueue &Q,ElemType x){
    if ((Q.rear + 1)%MaxSize == MaxSize)
        return false;
    Q.data[Q.rear] = x; //原指針指向的是下一個應(yīng)該填充的位置
    Q.rear = (Q.rear + 1)%MaxSize;  //為了防止進入下個周期而大于MaxSize
    return true；
}

出隊

bool DeQueue(SqQueue &Q,ElemType x){
    if(Q.rear == Q.front)
        return true;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1)%MaxSize;
    return true;
}

隊列的鏈式存儲結(jié)構(gòu)

隊列的鏈式表示稱為鏈隊列，它實際上是一個帶有頭指針和尾指針的單鏈表；頭指針指向隊頭結(jié)點，尾指針指向隊尾結(jié)點，即單鏈表的最后一個結(jié)點

注意：在隊列的順序存儲中，尾指針指向隊尾元素的下一個結(jié)點；而在隊列的鏈式存儲結(jié)構(gòu)中，尾指針指向的是隊尾元素所在的結(jié)點

隊列的鏈式存儲類型可以描述為

typedef struct{     //鏈式隊列的結(jié)點
    ElemData data;
    struct LinkNode *next;
}LinkNode;

typedef struct{     //鏈式隊列本身
    LinkNode *front,*next;  //隊列的隊頭和隊尾指針
}LinkQueue;

當隊列的隊頭指針Q.front == NULL和隊尾指針Q.next == NULL時，鏈式隊列為空

出隊時，首先判斷隊是否為空；如果不為空，則將其從鏈表中摘除，并且使Q.front指向下一個結(jié)點（若該結(jié)點為最后一個結(jié)點，則將Q.front和Q.next都設(shè)為NULL；入隊時，建立一個新結(jié)點，將新結(jié)點插入鏈表的尾部，并讓Q.rear指向這個新插入的結(jié)點（若原隊列為空，則令Q.front也指向這個結(jié)點）

因此，不帶頭節(jié)點的鏈式隊列由于存在為空的可能，因此操作上比較麻煩；因此通常將鏈式隊列設(shè)計成帶頭結(jié)點的單鏈表，這樣插入和刪除操作能得到統(tǒng)一

用單鏈表表示的鏈式隊列適合數(shù)據(jù)元素變動比較大的情形，而且不存在隊列滿產(chǎn)生溢出的問題；而且如果程序中需要使用多個隊列，最好使用鏈式隊列，這樣不會出現(xiàn)存儲分配不合理和“溢出”的情形

鏈式隊列的操作

鏈式隊列的初始化

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

判鏈式隊列為空

bool IsEmpty(LinkQueue Q){
    if (Q.front == Q.rear)
        return true;
    else
        return false;
}

入隊操作

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;
}

出隊操作

bool DeQueue(LinkQueue &Q,ElemType &x){
    if (Q.front == Q.rear)
        return false;   //判斷鏈式隊列是否為空
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)
        Q.rear = Q.front;   //如果原隊列只有一個結(jié)點，則刪除后隊列為空
    free(p);
    return true;
}

雙端隊列

雙端隊列是指允許兩端都可以進行入隊和出隊操作的隊列；其元素的結(jié)構(gòu)仍然是線性結(jié)構(gòu)，將隊列的兩端分別稱為前端和后端；兩端都可以出隊或者入隊

輸出受限的雙端隊列：允許在一端進行插入和刪除，但在另一端只允許進行插入

輸入受限的雙端隊列：允許在一段進行插入和刪除，但在另一端只允許進行刪除

若限定雙端隊列從某個端點插入的元素只能從該端點進行刪除，則該雙端隊列退化成兩個棧底相臨接的棧