隊列

隊列的基本概念

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

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

隊列常見的基本操作

隊列常見的基本操作主要有構(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ā)生后移，導致data數(shù)組中仍然存在可以存放元素的空位置纬黎，實際上是一種“假溢出”幅骄，這也是順序隊列的一種缺點。

循環(huán)隊列

前面說本今，順序隊列的缺點是對隊頭元素的刪除操作會導致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成員蹦漠，通過記錄導致Q.rear==Q.front的原因區(qū)分隊滿還是隊空椭员；若因刪除導致Q.rear==Q.front，則為隊空笛园，記錄為tag等于0隘击；若因插入導致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)，將隊列的兩端分別稱為前端和后端肆氓；兩端都可以出隊或者入隊

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

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

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

考研數(shù)據(jù)結(jié)構(gòu)筆記——3.隊列