前言
? ? ? ? 在學(xué)過棧之后，會(huì)了解到棧的底層是根據(jù)順序表或者鏈表來構(gòu)建的，那么我們今天要學(xué)習(xí)的隊(duì)列是否也是基于順序表和鏈表呢？那我們直接進(jìn)入正題吧！
1. 隊(duì)列的概念（圖解）
? ? ? ? 還是跟上節(jié)一樣，依舊用圖解的方式讓大家更好的理解概念。
1.1 隊(duì)列的組成：
? ? ? ? 隊(duì)列：隊(duì)列指的是圖中黑色邊框及其內(nèi)部的空間
? ? ? ? 隊(duì)頭：出元素的一邊叫隊(duì)頭
? ? ? ? 隊(duì)尾：入元素的一邊叫隊(duì)尾
? ? ? ? 隊(duì)內(nèi)元素：藍(lán)色正方形
1.2 隊(duì)列的進(jìn)出規(guī)則：先進(jìn)先出
? ? ? ? 隊(duì)列的進(jìn)出規(guī)則跟棧不一樣，棧是先進(jìn)后出，而隊(duì)列是先進(jìn)先出。
? ? ? ? 隊(duì)列只能從隊(duì)頭出，隊(duì)尾入，所以這就造就了隊(duì)列的先進(jìn)先出，先從隊(duì)尾入的元素，先從隊(duì)頭出。
2. 隊(duì)列的架構(gòu)
2.1 隊(duì)列為順序表構(gòu)成（舍棄方案）
? ? ? ? 隊(duì)列的入隊(duì)列相當(dāng)于尾插（頭插），隊(duì)列的出隊(duì)列相當(dāng)于頭刪（尾刪）????????
? ? ? ? 我們知道順序表的尾插尾刪是非?？斓模芊奖?。但是頭插頭刪卻需要挪動(dòng)數(shù)據(jù)，覆蓋，十分麻煩。無論是我們?nèi)腙?duì)列和出隊(duì)列，我們都必然會(huì)涉及到頭的挪動(dòng)。這樣大大增加了我們時(shí)間復(fù)雜度，所以我們隊(duì)列不推薦使用順序表構(gòu)建。
2.2 隊(duì)列為鏈表構(gòu)成（文末源代碼）
? ? ? ? 我們是選擇什么樣的鏈表呢？單向鏈表還是雙向鏈表，是否帶頭，是否成環(huán)？不要著急，我們先來看單鏈表是否簡單可行。
2.2.1 隊(duì)列為單鏈表構(gòu)成
? ? ? ? 如圖，我們選擇鏈表的頭部作為了隊(duì)頭，鏈表的尾部作為了隊(duì)尾，那么出隊(duì)列就是頭刪，入隊(duì)列就是尾插。
1. 入隊(duì)列：
? ? ? ? 入隊(duì)列就是鏈表的尾插，先找到鏈表的尾，再跟新節(jié)點(diǎn)連接就可以了。但是當(dāng)我們隊(duì)列中沒有元素的時(shí)候，就需要改變一下鏈表頭指針指向的位置，讓他指向第一個(gè)節(jié)點(diǎn)，這里我們是改變指針，需要用到二級(jí)指針，但是我們今天不用二級(jí)指針，使用一個(gè)新的方法來解決。
2. 出隊(duì)列
? ? ? ? 出隊(duì)列相當(dāng)于鏈表的頭刪，看圖就可以了。????????
我們會(huì)發(fā)現(xiàn)其實(shí)單鏈表已經(jīng)可以幾乎很好的解決隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu)了，那我們就沒有必要去創(chuàng)造什么帶頭啊，循環(huán)啊，雙向啊這些結(jié)構(gòu)。所以接下來就讓源代碼登場吧！
3. 隊(duì)列由單鏈表構(gòu)成（源代碼）
3.1 隊(duì)列的定義
? ? ? ? 這里跟以往不同的點(diǎn)是 這里我們重新定義了一個(gè)結(jié)構(gòu)體，包含了隊(duì)列的頭節(jié)點(diǎn)和尾結(jié)點(diǎn)，我們這么定義的目的是可以更改頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。
//如果你要更改隊(duì)列元素的數(shù)據(jù)類型，在這里更改一次就OK了，int變成其他數(shù)據(jù)類型
typedef int QDataType;
//這里我們正常定義隊(duì)列的節(jié)點(diǎn)，因?yàn)槭擎湵順?gòu)成的，和鏈表節(jié)點(diǎn)一樣
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
//這里我們重新定義了一個(gè)結(jié)構(gòu)體，包含了隊(duì)列的頭節(jié)點(diǎn)和尾結(jié)點(diǎn)，我們這么定義的目的是可以更改頭節(jié)點(diǎn)和尾節(jié)點(diǎn)
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Que;3.2 隊(duì)列的初始化
//初始化
void QueueInit(Que* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}3.3?隊(duì)列的銷毀
void QueueDestroy(Que* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}3.4?入隊(duì)列
//入隊(duì)列
void QueuePush(Que* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}3.5?出隊(duì)列
//出隊(duì)列
void QueuePop(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}3.6?取隊(duì)頭元素
//取隊(duì)頭元素
QDataType QueueFront(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}3.7?取隊(duì)尾元素
//取隊(duì)尾元素
QDataType QueueBack(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}3.8?判斷隊(duì)列是否為空
bool QueueEmpty(Que* pq)
{
assert(pq);
return pq->head == NULL;
}3.9?求隊(duì)列長度
//隊(duì)列的長度
int QueueSize(Que* pq)
{
assert(pq);
return pq->size;
}4. 習(xí)題
4.1?下列關(guān)于隊(duì)列的敘述錯(cuò)誤的是（ ）
A.隊(duì)列可以使用鏈表實(shí)現(xiàn)
B.隊(duì)列是一種“先入先出”的數(shù)據(jù)結(jié)構(gòu)
C.數(shù)據(jù)出隊(duì)列時(shí)一定只影響尾指針
D.數(shù)據(jù)入隊(duì)列時(shí)一定從尾部插入
答案：C
解析：出隊(duì)操作，一定會(huì)影響頭指針，如果出隊(duì)之后，隊(duì)列為空，會(huì)影響尾指針。
4.2 ?用無頭單鏈表存儲(chǔ)隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作時(shí)（）
A.僅修改隊(duì)頭指針
B.隊(duì)頭、隊(duì)尾指針都要修改
C.隊(duì)頭、隊(duì)尾指針都可能要修改
D.僅修改隊(duì)尾指針
答案：C
解析：出隊(duì)操作，一定會(huì)修改頭指針，如果出隊(duì)之后，隊(duì)列為空，需要修改尾指針。
4.3 以下不是隊(duì)列的基本運(yùn)算的是（ ）
A.從隊(duì)尾插入一個(gè)新元素
B.從隊(duì)列中刪除隊(duì)尾元素
C.判斷一個(gè)隊(duì)列是否為空
D.讀取隊(duì)頭元素的值
答案：B
解析：隊(duì)列只能從隊(duì)頭刪除元素。
4.4 下面關(guān)于棧和隊(duì)列的說法中錯(cuò)誤的是（ ）（多選）
A.隊(duì)列和棧通常都使用鏈表實(shí)現(xiàn)
B.隊(duì)列和棧都只能從兩端插入、刪除數(shù)據(jù)
C.隊(duì)列和棧都不支持隨機(jī)訪問和隨機(jī)插入
D.隊(duì)列是“先入先出”，棧是“先入后出”
答案：AB
解析：
A錯(cuò)誤：棧是尾部插入和刪除，一般使用順序表實(shí)現(xiàn)，隊(duì)列是頭部刪除尾部插入，一般使用鏈表實(shí)現(xiàn)
B錯(cuò)誤：棧是后進(jìn)先出，尾部插入和刪除，并不是兩端；隊(duì)列是先進(jìn)先出，尾部插入頭部刪除。
4.5 下列關(guān)于順序結(jié)構(gòu)實(shí)現(xiàn)循環(huán)隊(duì)列的說法，正確的是（ ）
A.循環(huán)隊(duì)列的長度通常都不固定
B.直接用隊(duì)頭和隊(duì)尾在同一個(gè)位置可以判斷循環(huán)隊(duì)列是否為滿
C.通過設(shè)置計(jì)數(shù)的方式可以判斷隊(duì)列空或者滿
D.循環(huán)隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)
答案：C
解析：順序結(jié)構(gòu)實(shí)現(xiàn)循環(huán)隊(duì)列是通過數(shù)組下標(biāo)的循環(huán)來實(shí)現(xiàn)的
A錯(cuò)誤：循環(huán)隊(duì)列的長度都是固定的
B錯(cuò)誤：隊(duì)頭和隊(duì)尾在同一個(gè)位置時(shí) 隊(duì)列可能是空的，也可能是滿的，因此無法判斷
C正確：設(shè)置計(jì)數(shù)即添加一個(gè)字段來記錄隊(duì)列中有效元素的個(gè)數(shù)，如果隊(duì)列中有效元素個(gè)數(shù)等于空間總大小時(shí)隊(duì)列滿，如果隊(duì)列中有效元素個(gè)數(shù)為0時(shí)隊(duì)列空
D錯(cuò)誤：循環(huán)隊(duì)列也是隊(duì)列的一種，是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)文章來源：http://www.zghlxwxcb.cn/news/detail-736402.html
好啦，我們關(guān)于隊(duì)列的實(shí)現(xiàn)已經(jīng)結(jié)束了，謝謝大家！文章來源地址http://www.zghlxwxcb.cn/news/detail-736402.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之隊(duì)列（源代碼?圖解?習(xí)題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
