本章重點(diǎn)

• 隊(duì)列的概念及結(jié)構(gòu)

• 隊(duì)列的實(shí)現(xiàn)方式

• 鏈表方式實(shí)現(xiàn)棧接口

• 隊(duì)列面試題

一、隊(duì)列的概念及結(jié)構(gòu)

隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出 FIFO(First In First Out)

入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾

出隊(duì)列：進(jìn)行刪除操作的一端稱為隊(duì)頭

• 隊(duì)頭：線性表允許刪除的那一端。
• 隊(duì)尾：線性表允許插入的那一端。
• 空隊(duì)：不含任何元素的空表。

二、隊(duì)列的實(shí)現(xiàn)方式

????????如圖3-5所示為依次向隊(duì)列中插入元素?a0，a1，…，an-1后的示意圖，其中，a0是當(dāng)前隊(duì)頭元素，an-1?是當(dāng)前隊(duì)尾元素。

????????就像在食堂買飯就餐一樣，如果你在就餐人不多時(shí)去食堂就餐，你一到買飯窗口就能得到食堂服務(wù)人員的服務(wù)；但如果你在就餐人很多時(shí)去食堂就餐，你就需要在某個(gè)窗口排隊(duì)等待，直到輪到你時(shí)才能得到食堂服務(wù)人員的服務(wù)。在軟件設(shè)計(jì)中也經(jīng)常會(huì)遇到需要排隊(duì)等待服務(wù)的問題。隊(duì)列可用于臨時(shí)存儲(chǔ)那些需要等待接受服務(wù)的信息序列。

? ? ? ? 隊(duì)列只允許在頭部插入，尾部刪除，因此隊(duì)列的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)。

1.順序隊(duì)列

如圖3-6所示為一個(gè)有6個(gè)內(nèi)存單元的順序隊(duì)列的動(dòng)態(tài)示意圖，圖中front為隊(duì)頭指針，rear為隊(duì)尾指針。圖3-6 (a)表示一個(gè)空隊(duì)列；圖3-6 (b)表示A、B、C入隊(duì)列后的狀態(tài)；圖3-6 (c) 為A、B出隊(duì)列后的狀態(tài)；圖3-6 (d) 為D，E入隊(duì)列后的狀態(tài)。

?2.鏈?zhǔn)疥?duì)列

????????我們已知，隊(duì)列是操作受限制的線性表，隊(duì)列有隊(duì)頭和隊(duì)尾，插入元素的一端稱為隊(duì)尾,
刪除元素的一端稱為隊(duì)頭。
????????鏈?zhǔn)疥?duì)列的隊(duì)頭指針指向隊(duì)列的當(dāng)前頭結(jié)點(diǎn)位置，隊(duì)尾指針指向隊(duì)列的當(dāng)前隊(duì)尾結(jié)點(diǎn)位置。對(duì)于不帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列，出隊(duì)列時(shí)可直接刪除隊(duì)頭指針?biāo)傅慕Y(jié)點(diǎn)，因此鏈?zhǔn)疥?duì)列沒有頭結(jié)點(diǎn)更方便。一個(gè)不帶頭結(jié)點(diǎn)、隊(duì)列中有元素a0，a1，…，an-1的鏈?zhǔn)疥?duì)列的結(jié)構(gòu)如圖3-9所示，其中，指針?front?指示的是鏈?zhǔn)疥?duì)列的隊(duì)頭結(jié)點(diǎn)，指針?rear?指示的是鏈?zhǔn)疥?duì)列的隊(duì)尾結(jié)點(diǎn)。

三、鏈表方式實(shí)現(xiàn)棧接口

由于隊(duì)列只允許在頭部插入，尾部刪除，因此我們會(huì)改變頭結(jié)點(diǎn)，前面我們學(xué)過用二級(jí)指針和返回值兩種方式來處理頭結(jié)點(diǎn)改變，今天我們來學(xué)一種新方式：結(jié)構(gòu)體修改，將隊(duì)列的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)放入到一個(gè)結(jié)構(gòu)體當(dāng)中，通過結(jié)構(gòu)體地址就可以修改結(jié)構(gòu)體的內(nèi)容，同時(shí)還加入了一個(gè)size，用來計(jì)算當(dāng)前隊(duì)列的長(zhǎng)度。

typedef int QDataType;// 單鏈?zhǔn)浇Y(jié)構(gòu)：表示隊(duì)列
typedef struct QListNode
{struct QListNode* Next;QDataType data;
}QNode;// 隊(duì)列的結(jié)構(gòu)
typedef struct Queue
{QNode* front;QNode* rear;int size;
}Queue;// 初始化隊(duì)列
void QueueInit(Queue * q);
// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* q, QDataType data);
// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* q);
// 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* q);
// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* q);
// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* q);
// 檢測(cè)隊(duì)列是否為空
bool QueueEmpty(Queue* q);
// 銷毀隊(duì)列
void QueueDestroy(Queue* q);

1.初始化隊(duì)列：void QueueInit(Queue* q)

直接將front和rear域都設(shè)置為NULL，將隊(duì)列長(zhǎng)度設(shè)置為0，

// 初始化隊(duì)列
void QueueInit(Queue* q)
{assert(q);q->front = q->rear = NULL;q->size = 0;
}

2.隊(duì)尾入隊(duì)列：void QueuePush(Queue* q, QDataType data)

構(gòu)造一個(gè)節(jié)點(diǎn)newnode，data域存儲(chǔ)數(shù)據(jù)，next域存儲(chǔ)NULL，若原鏈隊(duì)為空，則將鏈隊(duì)結(jié)點(diǎn)的兩個(gè)域都指向結(jié)點(diǎn)newnode，否則將結(jié)點(diǎn)newnode鏈接到單鏈表末尾，并讓鏈隊(duì)結(jié)點(diǎn)的rear域指向它，再讓隊(duì)列的長(zhǎng)度+1

// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = data;newnode->Next = NULL;if (q->rear == NULL){q->front = q->rear = newnode;}else{q->rear->Next = newnode;q->rear = newnode;}q->size++;
}

3.隊(duì)頭出隊(duì)列：void QueuePop(Queue* q)

若原鏈隊(duì)為空，則下溢，assert斷言提示錯(cuò)誤，否則將隊(duì)首結(jié)點(diǎn)的Next域賦值給next，并刪除隊(duì)首結(jié)點(diǎn)，若原鏈隊(duì)只有一個(gè)結(jié)點(diǎn)，則需要將鏈隊(duì)結(jié)點(diǎn)的兩個(gè)域都設(shè)置為NULL，表示此時(shí)鏈隊(duì)已空。然后隊(duì)列長(zhǎng)度-1.

// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* q)
{assert(q);//隊(duì)列為空,斷言assert(!QueueEmpty(q));//rear出現(xiàn)野指針的問題if (q->front->Next == NULL){free(q->front);q->front = q->rear = NULL;}else{QNode* next = q->front->Next;free(q->front);q->front = next;}q->size--;
}

4.獲取隊(duì)列頭部元素：QDataType QueueFront(Queue* q)

// 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* q)
{assert(q);//隊(duì)列為空,斷言assert(!QueueEmpty(q));return q->front->data;
}

5.獲取隊(duì)列隊(duì)尾元素：QDataType QueueBack(Queue* q)

// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* q)
{assert(q);//隊(duì)列為空,斷言assert(!QueueEmpty(q));return q->rear->data;
}

6.獲取隊(duì)列中有效元素個(gè)數(shù)：int QueueSize(Queue* q)

// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* q)
{assert(q);return q->size;
}

7.檢測(cè)隊(duì)列是否為空：bool QueueEmpty(Queue* q)

// 檢測(cè)隊(duì)列是否為空
bool QueueEmpty(Queue* q)
{assert(q);//頭為空，該隊(duì)列就為空//返回true - 隊(duì)列就為空//返回false - 隊(duì)列不為空return q->front == NULL;
}

8.銷毀隊(duì)列：void QueueDestroy(Queue* q)

銷毀隊(duì)列創(chuàng)建一個(gè)結(jié)點(diǎn)保存下個(gè)結(jié)點(diǎn)的值，釋放當(dāng)前結(jié)點(diǎn)，然后依次遍歷隊(duì)列，依次釋放結(jié)點(diǎn)。釋放后需要將隊(duì)頭和隊(duì)尾都置空，隊(duì)列長(zhǎng)度設(shè)置為0，由于是通過結(jié)構(gòu)體去修改頭結(jié)點(diǎn)，此時(shí)隊(duì)列已經(jīng)為空指針，在調(diào)用函數(shù)后，不需要手動(dòng)將頭指針置空。

// 銷毀隊(duì)列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->front;while (cur){QNode* next = cur->Next;free(cur);cur = next;}q->front = q->rear = NULL;q->size = 0;
}

四、隊(duì)列面試題

1. 用隊(duì)列實(shí)現(xiàn)棧。OJ鏈接

• 棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，元素從頂端入棧，然后從頂端出棧。
• 隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，元素從后端入隊(duì)，然后從前端出隊(duì)。

思路：

????????為了滿足棧的特性，即最后入棧的元素最先出棧，在使用隊(duì)列實(shí)現(xiàn)棧時(shí)，應(yīng)滿足隊(duì)列前端的元素是最后入棧的元素。可以使用兩個(gè)隊(duì)列實(shí)現(xiàn)棧的操作，其中?queue1用于存儲(chǔ)棧內(nèi)的元素，queue2作為入棧操作的輔助隊(duì)列。

????????入棧操作時(shí)，首先將元素入隊(duì)到 queue2?，然后將 queue1的全部元素依次出隊(duì)并入隊(duì)到 queue2此時(shí) queue2的前端的元素即為新入棧的元素，再將 queue1和 queue2?互換，則 queue1??的元素即為棧內(nèi)的元素，queue1的前端和后端分別對(duì)應(yīng)棧頂和棧底。

????????由于每次入棧操作都確保 queue1的前端元素為棧頂元素，因此出棧操作和獲得棧頂元素操作都可以簡(jiǎn)單實(shí)現(xiàn)。出棧操作只需要移除 queue1的前端元素并返回即可，獲得棧頂元素操作只需要獲得 queue1的前端元素并返回即可（不移除元素）。

????????由于 queue1用于存儲(chǔ)棧內(nèi)的元素，判斷棧是否為空時(shí)，只需要判斷 queue1是否為空即可。

typedef struct {int* stk;int stkSize;int stkCapacity;
} Stack;Stack* stackCreate(int cpacity) {Stack* ret = malloc(sizeof(Stack));ret->stk = malloc(sizeof(int) * cpacity);ret->stkSize = 0;ret->stkCapacity = cpacity;return ret;
}void stackPush(Stack* obj, int x) {obj->stk[obj->stkSize++] = x;
}void stackPop(Stack* obj) {obj->stkSize--;
}int stackTop(Stack* obj) {return obj->stk[obj->stkSize - 1];
}bool stackEmpty(Stack* obj) {return obj->stkSize == 0;
}void stackFree(Stack* obj) {free(obj->stk);
}typedef struct {Stack* inStack;Stack* outStack;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* ret = malloc(sizeof(MyQueue));ret->inStack = stackCreate(100);ret->outStack = stackCreate(100);return ret;
}void in2out(MyQueue* obj) {while (!stackEmpty(obj->inStack)) {stackPush(obj->outStack, stackTop(obj->inStack));stackPop(obj->inStack);}
}void myQueuePush(MyQueue* obj, int x) {stackPush(obj->inStack, x);
}int myQueuePop(MyQueue* obj) {if (stackEmpty(obj->outStack)) {in2out(obj);}int x = stackTop(obj->outStack);stackPop(obj->outStack);return x;
}int myQueuePeek(MyQueue* obj) {if (stackEmpty(obj->outStack)) {in2out(obj);}return stackTop(obj->outStack);
}bool myQueueEmpty(MyQueue* obj) {return stackEmpty(obj->inStack) && stackEmpty(obj->outStack);
}void myQueueFree(MyQueue* obj) {stackFree(obj->inStack);stackFree(obj->outStack);
}

2. 用棧實(shí)現(xiàn)隊(duì)列。OJ鏈接

將一個(gè)棧當(dāng)作輸入棧，用于壓入 push\ 傳入的數(shù)據(jù)；另一個(gè)棧當(dāng)作輸出棧，用于 pop 和 peek 操作。每次 pop 或 peek 時(shí)，若輸出棧為空則將輸入棧的全部數(shù)據(jù)依次彈出并壓入輸出棧，這樣輸出棧從棧頂往棧底的順序就是隊(duì)列從隊(duì)首往隊(duì)尾的順序。

typedef struct {int* stk;int stkSize;int stkCapacity;
} Stack;Stack* stackCreate(int cpacity) {Stack* ret = malloc(sizeof(Stack));ret->stk = malloc(sizeof(int) * cpacity);ret->stkSize = 0;ret->stkCapacity = cpacity;return ret;
}void stackPush(Stack* obj, int x) {obj->stk[obj->stkSize++] = x;
}void stackPop(Stack* obj) {obj->stkSize--;
}int stackTop(Stack* obj) {return obj->stk[obj->stkSize - 1];
}bool stackEmpty(Stack* obj) {return obj->stkSize == 0;
}void stackFree(Stack* obj) {free(obj->stk);
}typedef struct {Stack* inStack;Stack* outStack;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* ret = malloc(sizeof(MyQueue));ret->inStack = stackCreate(100);ret->outStack = stackCreate(100);return ret;
}void in2out(MyQueue* obj) {while (!stackEmpty(obj->inStack)) {stackPush(obj->outStack, stackTop(obj->inStack));stackPop(obj->inStack);}
}void myQueuePush(MyQueue* obj, int x) {stackPush(obj->inStack, x);
}int myQueuePop(MyQueue* obj) {if (stackEmpty(obj->outStack)) {in2out(obj);}int x = stackTop(obj->outStack);stackPop(obj->outStack);return x;
}int myQueuePeek(MyQueue* obj) {if (stackEmpty(obj->outStack)) {in2out(obj);}return stackTop(obj->outStack);
}bool myQueueEmpty(MyQueue* obj) {return stackEmpty(obj->inStack) && stackEmpty(obj->outStack);
}void myQueueFree(MyQueue* obj) {stackFree(obj->inStack);stackFree(obj->outStack);
}

3. 設(shè)計(jì)循環(huán)隊(duì)列。OJ鏈接

順序隊(duì)列的假溢出問題

????????解決假溢出的方法就是后面滿了，就再?gòu)念^開始，也就是頭尾相接的循環(huán)。我們把隊(duì)列的這種頭尾相接的順序存儲(chǔ)結(jié)構(gòu)稱為循環(huán)隊(duì)列。當(dāng)隊(duì)首指針Q->front = MAXSIZE-1后，再前進(jìn)一個(gè)位置就自動(dòng)到0，這可以利用除法取余運(yùn)算（%）來實(shí)現(xiàn)。

• 初始時(shí)：Q->front = Q->rear=0。
• 隊(duì)首指針進(jìn)1：Q->front = (Q->front + 1) % MAXSIZE。
• 隊(duì)尾指針進(jìn)1：Q->rear = (Q->rear + 1) % MAXSIZE。
• 隊(duì)列長(zhǎng)度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE。

????????出隊(duì)入隊(duì)時(shí)，指針都按照順時(shí)針方向前進(jìn)1，如下圖所示：

????????那么，循環(huán)隊(duì)列隊(duì)空和隊(duì)滿的判斷條件是什么呢？
????????顯然，隊(duì)空的條件是 Q->front == Q->rear 。若入隊(duì)元素的速度快于出隊(duì)元素的速度，則隊(duì)尾指針很快就會(huì)趕上隊(duì)首指針，如圖( d1 ）所示，此時(shí)可以看出隊(duì)滿時(shí)也有 Q ->front == Q -> rear 。為了區(qū)分隊(duì)空還是隊(duì)滿的情況，有三種處理方式：
（1）犧牲一個(gè)單元來區(qū)分隊(duì)空和隊(duì)滿，入隊(duì)時(shí)少用一個(gè)隊(duì)列單元，這是種較為普遍的做法，約定以“隊(duì)頭指針在隊(duì)尾指針的下一位置作為隊(duì)滿的標(biāo)志”，如圖 ( d2 ）所示。

• 隊(duì)滿條件： (Q->rear + 1)%Maxsize == Q->front
• 隊(duì)空條件仍： Q->front == Q->rear
• 隊(duì)列中元素的個(gè)數(shù)： (Q->rear - Q ->front + Maxsize)% Maxsize

（2）類型中增設(shè)表示元素個(gè)數(shù)的數(shù)據(jù)成員。這樣，隊(duì)空的條件為 Q->size == O ；隊(duì)滿的條件為 Q->size == Maxsize 。這兩種情況都有 Q->front == Q->rear
（3）類型中增設(shè)tag 數(shù)據(jù)成員，以區(qū)分是隊(duì)滿還是隊(duì)空。tag 等于0時(shí)，若因刪除導(dǎo)致 Q->front == Q->rear ，則為隊(duì)空；tag 等于 1 時(shí)，若因插入導(dǎo)致 Q ->front == Q->rear ，則為隊(duì)滿。

typedef struct {int front;int rear;int capacity;int *elements;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));obj->capacity = k + 1;obj->rear = obj->front = 0;obj->elements = (int *)malloc(sizeof(int) * obj->capacity);return obj;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if ((obj->rear + 1) % obj->capacity == obj->front) {return false;}obj->elements[obj->rear] = value;obj->rear = (obj->rear + 1) % obj->capacity;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (obj->rear == obj->front) {return false;}obj->front = (obj->front + 1) % obj->capacity;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (obj->rear == obj->front) {return -1;}return obj->elements[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if (obj->rear == obj->front) {return -1;}return obj->elements[(obj->rear - 1 + obj->capacity) % obj->capacity];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->front;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1) % obj->capacity == obj->front;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->elements);free(obj);
}

本章結(jié)束啦！！！