一、隊列概念

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

隊列的操作很簡單，主要有以下幾種常見的操作：

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

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

3. 出隊列：將隊頭元素取出，同時刪除該元素，使下一個元素成為對頭

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

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

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

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

如下圖所示：

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

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

#define QUEUEMAX 15

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

（2）初始化隊列

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

    return NULL;
}

（3）釋放隊列

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

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

/*
*判斷隊列是否為空
*/

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

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

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

（5）入隊操作

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

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

（6）出隊操作

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

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

（7）獲取隊頭元素

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

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

三、循環(huán)隊列

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

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

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

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

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

以入隊操作為例：

1. 將隊尾序號加1,即tail=tail+1

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

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

4. 若未溢出，將元素入隊即可

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

#define QUEUEMAX 15

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

（2）初始化隊列

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

    return NULL;
}

（3）釋放隊列

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

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

/*
*判斷隊列是否為空
*/

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


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


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

（5）入隊操作

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

（6）出隊操作

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

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

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

（7）獲取隊頭元素

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