一、隊(duì)列概念

隊(duì)列時(shí)一種特殊的線性表，只允許在表的前端進(jìn)行刪除操作，而在表的后端進(jìn)行插入操作，隊(duì)列具有先進(jìn)先出的特點(diǎn)。

隊(duì)列的操作很簡(jiǎn)單，主要有以下幾種常見的操作：

1. 初始化隊(duì)列：創(chuàng)建一個(gè)隊(duì)列

2. 進(jìn)隊(duì)列：將一個(gè)元素添加到隊(duì)尾

3. 出隊(duì)列：將隊(duì)頭元素取出，同時(shí)刪除該元素，使下一個(gè)元素成為對(duì)頭

4. 獲取隊(duì)列第一元素：將隊(duì)頭元素取出，不刪除該元素

5. 獲取隊(duì)列長(zhǎng)度：根據(jù)隊(duì)頭和隊(duì)尾計(jì)算出隊(duì)列中元素的數(shù)量

二、順序隊(duì)列實(shí)現(xiàn)

將隊(duì)列用順序存儲(chǔ)方式保存時(shí)，在內(nèi)存中申請(qǐng)一片區(qū)域用來保存元素，當(dāng)?shù)谝粋€(gè)元素A進(jìn)入隊(duì)列時(shí)，因是空列隊(duì)，因此元素A將排在隊(duì)頭，接著B、C、D順次進(jìn)入隊(duì)列，就得到如圖所示的隊(duì)列。其中head指向隊(duì)頭，以指示隊(duì)頭元素出隊(duì)操作，tail指向隊(duì)尾，以指示新增元素進(jìn)入隊(duì)列。

如下圖所示：

執(zhí)行一次出隊(duì)操作，元素A將出隊(duì)，這時(shí)第2個(gè)元素B將成為隊(duì)頭，head指針將指向該元素如果要將元素E入隊(duì)，則是將其放入tail指針指向元素的后一個(gè)位置（如下圖為5的單元），并使tail指針指向序號(hào)為5的單元。

（1）定義順序隊(duì)列的結(jié)構(gòu)

#define QUEUEMAX 15

typedef struct{
    DATA data[QUEUEMAX];
    int head;
    int tail;
} SeqQueue;

（2）初始化隊(duì)列

SeqQueue *SeqQueueInit()
{
    SeqQueue *q;
    if (q=(SeqQueue *)malloc(sizeof(SeqQueue))) {
        q->head = 0;
        q->tail = 0;
        return q;
    }

    return NULL;
}

（3）釋放隊(duì)列

void SeqQueueFree(SeqQueue *q)
{
    if (q)
        free(q);
}

（4）獲取隊(duì)列狀態(tài)

/*
*判斷隊(duì)列是否為空
*/

int SeqQueueIsEmpty(SeqQueue *q)
{
    return (q->head == q->tail);
}

/*
*判斷隊(duì)列是否已滿
*/
int SeqQueueIsFull(SeqQueue *q)
{
    return (q->tail == QUEUEMAX);
}

/*
*獲取隊(duì)列的長(zhǎng)度
*/
int SeqQueueLen(SeqQueue *q)
{
    return (q->tail - q->head);
}

（5）入隊(duì)操作

int SeqQueueIn(SeqQueue *q, DATA data)
{
    if (SeqQueueIsFull(q)) {
        printf("隊(duì)列已滿!\n");
        return 0;
    }

    q->data[q->tail++] = data;
    return 1;
}

（6）出隊(duì)操作

DATA *SeqQueueOut(SeqQueue *q)
{
    if (SeqQueueIsEmpty(q)) {
        printf("隊(duì)列已空!\n");
        return NULL;
    }

    return &(q->data[q->head++]);
}

（7）獲取隊(duì)頭元素

DATA *SeqQueuePeek(SeqQueue *q)
{
    if (SeqQueueIsEmpty(q)) {
        printf("隊(duì)列已空!\n");
        return NULL;
    }

    return &(q->data[q->head]);
}

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

由于每次出隊(duì)后，隊(duì)頭的指針都向后移動(dòng)，這時(shí)候就會(huì)出現(xiàn)一個(gè)問題，就是假溢出。如下圖所示：

tail已指向隊(duì)尾，這時(shí)進(jìn)行入隊(duì)操作時(shí)，雖然前面還有空位置，但仍然顯示隊(duì)列已滿。為了解決這個(gè)問題，就提出了循環(huán)隊(duì)列。

循環(huán)隊(duì)列就是將隊(duì)列的首尾相連構(gòu)成一個(gè)環(huán)形區(qū)域，當(dāng)在第n個(gè)位置進(jìn)行元素的入隊(duì)操作后，下一個(gè)地址就翻轉(zhuǎn)為1

循環(huán)隊(duì)列結(jié)構(gòu)圖：

在循環(huán)隊(duì)列中，主要需要計(jì)算隊(duì)尾tail和隊(duì)頭head的序號(hào)

以入隊(duì)操作為例：

1. 將隊(duì)尾序號(hào)加1,即tail=tail+1

2. 若tail=n+1，則tail=1, 其實(shí)前2步，可以使用表達(dá)式tail=（tail+1）%n

3. 若head=tail，即隊(duì)尾和隊(duì)頭重合了，表示隊(duì)列已滿提示隊(duì)列溢出

4. 若未溢出，將元素入隊(duì)即可

（1）定義循環(huán)隊(duì)列的結(jié)構(gòu)

#define QUEUEMAX 15

typedef struct{
    DATA data[QUEUEMAX];
    int head;
    int tail;
} CycQueue;

（2）初始化隊(duì)列

CycQueue *CycQueueInit()
{
    CycQueue *q;
    if (q=(CycQueue *)malloc(sizeof(CycQueue))) {
        q->head = 0;
        q->tail = 0;
        return q;
    }

    return NULL;
}

（3）釋放隊(duì)列

void CycQueueFree(CycQueue *q)
{
    if (q)
        free(q);
}

（4）獲取隊(duì)列狀態(tài)

/*
*判斷隊(duì)列是否為空
*/

int CycQueueIsEmpty(CycQueue *q)
{
    return (q->head == q->tail);
}


/*
*判斷隊(duì)列是否已滿
*/
int CycQueueIsFull(CycQueue *q)
{
    return ((q->tail+1)%QUEUEMAX == q->head);
}


/*
*獲取隊(duì)列的長(zhǎng)度
*/
int CycQueueLen(CycQueue *q)
{
    int n;
    n = q->tail - q->head;
    if (n < 0) {
        n = QUEUEMAX + n;
    }
    return n;
}

（5）入隊(duì)操作

int CycQueueIn(CycQueue *q, DATA data)
{
    if (CycQueueIsFull(q)) {
        printf("隊(duì)列已滿!\n");
        return 0;
    }
    q->tail = (q->tail+1)%QUEUEMAX;
    q->data[q->tail] = data;
    return 1;
}

（6）出隊(duì)操作

DATA *CycQueueOut(CycQueue *q)
{
    int head;

    if (CycQueueIsEmpty(q)) {
        printf("隊(duì)列已空!\n");
        return NULL;
    }

    head = q->head;
    q->head = (q->head +1)%QUEUEMAX;
    return &(q->data[head]);
}

（7）獲取隊(duì)頭元素

DATA *CycQueuePeek(CycQueue *q)
{
    if (CycQueueIsEmpty(q)) {
        printf("隊(duì)列已空!\n");
        return NULL;
    }
    return &(q->data[q->head]);
}