數(shù)據(jù)結(jié)構(gòu)和算法（1）線性表實現(xiàn)
數(shù)據(jù)結(jié)構(gòu)和算法（2）單向循環(huán)鏈表的創(chuàng)建插入刪除實現(xiàn)
數(shù)據(jù)結(jié)構(gòu)和算法（3）雙向鏈表與雙向循環(huán)鏈表的實現(xiàn)
數(shù)據(jù)結(jié)構(gòu)和算法（4）鏈表相關(guān)面試題
數(shù)據(jù)結(jié)構(gòu)和算法（5）棧和隊列的操作和實現(xiàn)
數(shù)據(jù)結(jié)構(gòu)和算法（6）隊列的操作和實現(xiàn)
@[TOC]
1. 數(shù)據(jù)結(jié)構(gòu)和算法（6）隊列的操作和實現(xiàn)
代碼下載
本篇博客代碼下載：
1.1 隊列簡介
隊列是一種先進(jìn)先出(First In First Out)的線性表，也就是FIFO。通常，稱進(jìn)數(shù)據(jù)的一端為 "隊尾"，出數(shù)據(jù)的一端為 "隊頭"，數(shù)據(jù)元素進(jìn)隊列的過程稱為 "入隊"，出隊列的過程稱為 "出隊"。
與棧結(jié)構(gòu)不同的是，隊列的兩端都"開口"，要求數(shù)據(jù)只能從一端進(jìn)，從另一端出，如下圖 所示：
如果對棧結(jié)構(gòu)不熟悉可以參考我之前的博客：“數(shù)據(jù)結(jié)構(gòu)和算法（五）棧和隊列的操作和實現(xiàn)”
隊列的存儲結(jié)構(gòu)
不僅如此，隊列中數(shù)據(jù)的進(jìn)出要遵循 "先進(jìn)先出" 的原則，即最先進(jìn)隊列的數(shù)據(jù)元素，同樣要最先出隊列。拿圖 1 中的隊列來說，從數(shù)據(jù)在隊列中的存儲狀態(tài)可以分析出，元素 1 最先進(jìn)隊，其次是元素 2，最后是元素 3。此時如果將元素 3 出隊，根據(jù)隊列 "先進(jìn)先出" 的特點，元素 1 要先出隊列，元素 2 再出隊列，最后才輪到元素 3 出隊列。
棧和隊列不要混淆，棧結(jié)構(gòu)是一端封口，特點是"先進(jìn)后出"；而隊列的兩端全是開口，特點是"先進(jìn)先出"。
因此，數(shù)據(jù)從表的一端進(jìn)，從另一端出，且遵循 "先進(jìn)先出" 原則的線性存儲結(jié)構(gòu)就是隊列。
隊列存儲結(jié)構(gòu)的實現(xiàn)有以下兩種方式：
- 順序隊列：在順序表的基礎(chǔ)上實現(xiàn)的隊列結(jié)構(gòu)；
- 鏈隊列：在鏈表的基礎(chǔ)上實現(xiàn)的隊列結(jié)構(gòu)；
兩者的區(qū)別僅是順序表和鏈表的區(qū)別，即在實際的物理空間中，數(shù)據(jù)集中存儲的隊列是順序隊列，分散存儲的隊列是鏈隊列。
實際生活中，隊列的應(yīng)用隨處可見，比如排隊買 XXX、醫(yī)院的掛號系統(tǒng)等，采用的都是隊列的結(jié)構(gòu)。
拿排隊買票來說，所有的人排成一隊，先到者排的就靠前，后到者只能從隊尾排隊等待，隊中的每個人都必須等到自己前面的所有人全部買票成功并從隊頭出隊后，才輪到自己買票。這就不是典型的隊列結(jié)構(gòu)嗎？
明白了什么是隊列，接下來開始學(xué)習(xí)順序隊列和鏈隊列的基本實現(xiàn)和注意事項。
1.2 隊列順序存儲
由于順序隊列的底層使用的是數(shù)組，因此需預(yù)先申請一塊足夠大的內(nèi)存空間初始化順序隊列。除此之外，為了滿足順序隊列中數(shù)據(jù)從隊尾進(jìn)，隊頭出且先進(jìn)先出的要求，我們還需要定義兩個指針（top 和 rear）分別用于指向順序隊列中的隊頭元素和隊尾元素，如下圖 所示：
順序隊列的實現(xiàn)
由于順序隊列初始狀態(tài)沒有存儲任何元素，因此
top 指針和 rear 指針重合，且由于順序隊列底層實現(xiàn)靠的是數(shù)組，因此 top 和 rear 實際上是兩個變量，它的值分別是隊頭元素和隊尾元素所在數(shù)組位置的下標(biāo)。
當(dāng)有數(shù)據(jù)元素進(jìn)隊列時，對應(yīng)的實現(xiàn)操作是將其存儲在指針 rear 指向的數(shù)組位置，然后 rear+1；當(dāng)需要隊頭元素出隊時，僅需做 top+1 操作。
舉個栗子：
如果我們要將 {1,2,3,4} 用順序隊列存儲的實現(xiàn)，
元素1 進(jìn)隊的過程如下：
元素1 入隊
元素4入隊過程：
元素4入隊
那么我們接下來要將1，2，3，4這四個元素出隊。出隊過程如下：
元素1出隊
元素4出隊：
元素4出隊
我們先看一下一個簡單的順序隊列操作代碼：
#include <stdio.h>
int enQueue(int *a,int rear,int data){
a[rear]=data;
rear++;
return rear;
}
void deQueue(int *a,int front,int rear){
//如果 front==rear，表示隊列為空
while (front!=rear) {
printf("出隊元素：%d\n",a[front]);
front++;
}
}
int main() {
int a[100];
int front,rear;
//設(shè)置隊頭指針和隊尾指針，當(dāng)隊列中沒有元素時，隊頭和隊尾指向同一塊地址
front=rear=0;
//入隊
rear=enQueue(a, rear, 1);
rear=enQueue(a, rear, 2);
rear=enQueue(a, rear, 3);
rear=enQueue(a, rear, 4);
//出隊
deQueue(a, front, rear);
return 0;
}
輸出結(jié)構(gòu)為：
出隊元素：1
出隊元素：2
出隊元素：3
出隊元素：4
上面這種順序存儲隊列會存在一些問題，如假溢出問題，如下圖：
順序隊列假溢出問題
如上圖，我們先將A，B，C三個元素依次入隊，然后將A,B 出隊，然后又入隊了D，E，元素，這個時候rear隊尾指針指向了數(shù)組的最后，實際上我們還有兩個空間可以利用，這個時候隊列并沒有滿，但是由于rear指向了最后，也就是順序隊列整體發(fā)生了后移，這樣造成的影響是：
- 順序隊列之前的數(shù)組存儲空間將無法再被使用，造成了空間浪費；也就是假溢出。
- 另外如如果順序表申請的空間不足夠大，則直接造成程序中數(shù)組溢出，產(chǎn)生溢出錯誤；
為了解決上面問題，我們有一種比較優(yōu)的解決辦法，就是用循環(huán)隊列來解決假溢出問題。
接下來將介紹循環(huán)隊列。
1.2.1 循環(huán)隊列
循環(huán)隊列就是，當(dāng)隊尾指針移動到數(shù)組末尾時，下次再有元素入隊時，可以將隊尾指針重新移到數(shù)組前面沒有元素的位置。
循環(huán)隊列操作如下圖：
循環(huán)隊列解決假溢出問題
如上圖：
（a） 我們用Q.front == Q.rear表示隊列為空。
當(dāng)我們依次入隊a,b,c三個元素后，如上圖(b)所示。
接下來，我們將元素a 從隊頭出隊，如上圖(c)所示。
然后，我們又依次入隊了d ,e ,f, g這個時候?qū)嶋H上隊列已經(jīng)存滿了，單我們發(fā)現(xiàn) Q.front == Q.rear，如上圖(d1)所示。但是我們前面(a)中用Q.front == Q.rear表示隊列為空，但是隊列滿了的時候我們Q.front == Q.rear就無法區(qū)分到底是隊列為空還是滿了。為了解決這個問題，我們一般采用犧牲一個存儲空間的方式。也就如上圖(d2) 我們用Q.front = Q.rear + 1表示堆滿，就是犧牲一個存儲單元不存放數(shù)據(jù)。
在循環(huán)隊列中我們判斷隊列為空，隊列為滿的條件如下：
- 隊列為滿：
(Q.rear+1)％maxSize==Q.front- 隊列為空：
Q.rear==Q.front- 隊列中有效的數(shù)據(jù)的個數(shù)：
(Q.rear+maxSize-Q.front)%maxSize
1.2.2 循環(huán)隊列的代碼實現(xiàn)
- 循環(huán)隊列的順序存儲結(jié)構(gòu)
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct KQueue
{
KQueueElementType data[MAXSIZE];
int front; /* 頭指針 */
int rear; /* 尾指針，若隊列不空，指向隊列尾元素的下一個位置 */
}KQueue;
1.2.2.1 初始化
//1. 初始化一個隊列
KStatus initQueue(KQueue *Q) {
Q->front = Q->rear = 0;
return OK;
}
1.2.2.2 隊列清空
//2. 將隊列清空
KStatus clearQueue(KQueue *Q) {
Q->front = Q->rear = 0;
return OK;
}
1.2.2.3 隊列判空
//3. 隊列判空
KStatus isEmpty(KQueue Q) {
return Q.front == Q.rear ;
}
1.2.2.4 隊列是否滿了
//4. 隊列是否滿了
KStatus isFull(KQueue Q) {
return Q.front == (Q.rear + 1 ) % MAXSIZE;
}
1.2.2.5 查詢隊列長度
//5. 查詢隊列長度
int getLength(KQueue Q) {
return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}
1.2.2.6 獲取隊頭元素
//6. 獲取隊頭元素
//若隊列不空,則用e返回Q的隊頭元素,并返回OK,否則返回ERROR;
KStatus getHead(KQueue Q, KQueueElementType *e) {
//判斷是否隊列為空
if (isEmpty(Q)) {
return ERROR;
}
//取出元素值
*e = Q.data[Q.front];
return OK;
}
1.2.2.7 入隊
//7. 入隊
// 若隊列未滿,則插入元素e為新隊尾元素
KStatus enQueue(KQueue *Q, KQueueElementType e) {
//判斷隊列是否滿了
if (isFull(*Q)) {
return ERROR;
}
//將元素e賦值給隊尾
Q->data[Q->rear] = e;
//rear指針向后移動一位，若到最后則轉(zhuǎn)到數(shù)組頭部
Q->rear = (Q->rear + 1) % MAXSIZE;
return OK;
}
1.2.2.8 出隊
//8. 出隊
//若隊列不空,則刪除Q中隊頭的元素,用e返回值
KStatus deQueue(KQueue *Q, KQueueElementType *e) {
if (isEmpty(*Q)) return ERROR;
//從隊頭取出元素賦值給e
*e = Q->data[Q->front];
//front指針向后移動一位，刪除對頭元素
Q->front = (Q->front + 1) % MAXSIZE;
return OK;
}
1.2.2.9 遍歷隊列
//9. 遍歷隊列
KStatus traverseQueue(KQueue Q) {
int i = Q.front;
while ((i + Q.front) != Q.rear) {
//從隊頭遍歷到隊尾，依次輸出元素，i表示當(dāng)前已經(jīng)輸出到第幾個元素了
//(i + Q.front) != Q.rear 表示 已經(jīng)遍歷到了隊尾了，
//由于我們不能修改front和rear指向，所以需要一個臨時變量記錄當(dāng)前位置
printf("%d ", Q.data[I]);
i = (i + 1) % MAXSIZE;
}
printf("\n");
return OK;
}
1.2.2.10 單元測試
//10. 單元測試
void test() {
printf("循環(huán)隊列操作單元測試\n");
KStatus j;
int I=0;
KQueueElementType d;
KQueue Q;
initQueue(&Q);
printf("初始化隊列后，隊列空否？%u(1:空 0:否)\n",isEmpty(Q));
printf("入隊:\n");
while (i < 10) {
enQueue(&Q, i);
I++;
}
traverseQueue(Q);
printf("隊列長度為: %d\n",getLength(Q));
printf("現(xiàn)在隊列空否？%u(1:空 0:否)\n",isEmpty(Q));
printf("出隊:\n");
//出隊
deQueue(&Q, &d);
printf("出隊的元素:%d\n",d);
traverseQueue(Q);
//獲取隊頭
j=getHead(Q,&d);
if(j)
printf("現(xiàn)在隊頭元素為: %d\n",d);
clearQueue(&Q);
printf("清空隊列后, 隊列空否？%u(1:空 0:否)\n",isEmpty(Q));
}
1.2.2.11 完整代碼
//
// main.c
// 010_Queue
//
// Created by 孔雨露 on 2020/4/18.
// Copyright ? 2020 Apple. All rights reserved.
//
#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存儲空間初始分配量 */
typedef int KStatus;
typedef int KQueueElementType; /* KQueueElementType類型根據(jù)實際情況而定，這里假設(shè)為int */
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct KQueue
{
KQueueElementType data[MAXSIZE];
int front; /* 頭指針 */
int rear; /* 尾指針，若隊列不空，指向隊列尾元素的下一個位置 */
}KQueue;
//1. 初始化一個隊列
KStatus initQueue(KQueue *Q) {
Q->front = Q->rear = 0;
return OK;
}
//2. 將隊列清空
KStatus clearQueue(KQueue *Q) {
Q->front = Q->rear = 0;
return OK;
}
//3. 隊列判空
KStatus isEmpty(KQueue Q) {
return Q.front == Q.rear ;
}
//4. 隊列是否滿了
KStatus isFull(KQueue Q) {
return Q.front == (Q.rear + 1 ) % MAXSIZE;
}
//5. 查詢隊列長度
int getLength(KQueue Q) {
return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}
//6. 獲取隊頭元素
//若隊列不空,則用e返回Q的隊頭元素,并返回OK,否則返回ERROR;
KStatus getHead(KQueue Q, KQueueElementType *e) {
//判斷是否隊列為空
if (isEmpty(Q)) {
return ERROR;
}
//取出元素值
*e = Q.data[Q.front];
return OK;
}
//7. 入隊
// 若隊列未滿,則插入元素e為新隊尾元素
KStatus enQueue(KQueue *Q, KQueueElementType e) {
//判斷隊列是否滿了
if (isFull(*Q)) {
return ERROR;
}
//將元素e賦值給隊尾
Q->data[Q->rear] = e;
//rear指針向后移動一位，若到最后則轉(zhuǎn)到數(shù)組頭部
Q->rear = (Q->rear + 1) % MAXSIZE;
return OK;
}
//8. 出隊
//若隊列不空,則刪除Q中隊頭的元素,用e返回值
KStatus deQueue(KQueue *Q, KQueueElementType *e) {
if (isEmpty(*Q)) return ERROR;
//從隊頭取出元素賦值給e
*e = Q->data[Q->front];
//front指針向后移動一位，刪除對頭元素
Q->front = (Q->front + 1) % MAXSIZE;
return OK;
}
//9. 遍歷隊列
KStatus traverseQueue(KQueue Q) {
int i = Q.front;
while ((i + Q.front) != Q.rear) {
//從隊頭遍歷到隊尾，依次輸出元素，i表示當(dāng)前已經(jīng)輸出到第幾個元素了
//(i + Q.front) != Q.rear 表示 已經(jīng)遍歷到了隊尾了，
//由于我們不能修改front和rear指向，所以需要一個臨時變量記錄當(dāng)前位置
printf("%d ", Q.data[I]);
i = (i + 1) % MAXSIZE;
}
printf("\n");
return OK;
}
//10. 單元測試
void test() {
printf("循環(huán)隊列操作單元測試\n");
KStatus j;
int I=0;
KQueueElementType d;
KQueue Q;
initQueue(&Q);
printf("初始化隊列后，隊列空否？%u(1:空 0:否)\n",isEmpty(Q));
printf("入隊:\n");
while (i < 10) {
enQueue(&Q, i);
I++;
}
traverseQueue(Q);
printf("隊列長度為: %d\n",getLength(Q));
printf("現(xiàn)在隊列空否？%u(1:空 0:否)\n",isEmpty(Q));
printf("出隊:\n");
//出隊
deQueue(&Q, &d);
printf("出隊的元素:%d\n",d);
traverseQueue(Q);
//獲取隊頭
j=getHead(Q,&d);
if(j)
printf("現(xiàn)在隊頭元素為: %d\n",d);
clearQueue(&Q);
printf("清空隊列后, 隊列空否？%u(1:空 0:否)\n",isEmpty(Q));
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
test();
return 0;
}
- 單元測試，輸出結(jié)果：
Hello, World!
循環(huán)隊列操作單元測試
初始化隊列后，隊列空否？1(1:空 0:否)
入隊:
0 1 2 3 4 5 6 7 8 9
隊列長度為: 10
現(xiàn)在隊列空否？0(1:空 0:否)
出隊:
出隊的元素:0
1 2 3 4 5 6 7 8
現(xiàn)在隊頭元素為: 1
清空隊列后, 隊列空否？1(1:空 0:否)
Program ended with exit code: 0
1.3 隊列鏈?zhǔn)酱鎯?/h2>
鏈?zhǔn)疥犃械膶崿F(xiàn)思想同順序隊列類似，只需創(chuàng)建兩個指針（命名為 top 和 rear）分別指向鏈表中隊列的隊頭元素和隊尾元素，如圖下圖1 所示:
圖 1 鏈?zhǔn)疥犃械某跏紶顟B(tài)
圖 1 所示為鏈?zhǔn)疥犃械某跏紶顟B(tài)，此時隊列中沒有存儲任何數(shù)據(jù)元素，因此 top 和 rear 指針都同時指向頭節(jié)點。
下面我們來講解一下 鏈?zhǔn)疥犃腥腙?，出隊操作，鏈?zhǔn)疥犃腥腙?，出隊操作基本跟單鏈表相似，如果不熟悉鏈表的操作可以參考我之前的鏈表相關(guān)的博客：
基本就是入隊就是在鏈表尾部結(jié)點插入一個元素，出隊就是在鏈表頭結(jié)點刪除一個結(jié)點。
- 鏈?zhǔn)疥犃腥腙牪僮鳎?br> 如下圖2 表示鏈?zhǔn)疥犃幸来稳腙?code>{1，2，3} 三個元素：
圖 2 {1,2,3} 入鏈?zhǔn)疥犃?/div>
如上圖所示，在鏈隊隊列中，當(dāng)有新的數(shù)據(jù)元素入隊，只需進(jìn)行以下 3 步操作：
- 將該數(shù)據(jù)元素用節(jié)點包裹，例如新節(jié)點名稱為 elem；
- 與 rear 指針指向的節(jié)點建立邏輯關(guān)系，即執(zhí)行 rear->next=elem；
- 最后移動 rear 指針指向該新節(jié)點，即 rear=elem；
- 鏈?zhǔn)疥犃谐鲫牪僮鳎?br>
當(dāng)鏈?zhǔn)疥犃兄?，有?shù)據(jù)元素需要出隊時，按照 "先進(jìn)先出" 的原則，只需將存儲該數(shù)據(jù)的節(jié)點以及它之前入隊的元素節(jié)點按照原則依次出隊即可。出隊過程就是從鏈表頭依次刪除首結(jié)點的過程, 現(xiàn)在我們需要將上圖2中的
1，2兩個元素出隊，其操作過程 如下圖3所示：
圖 3 鏈?zhǔn)疥犃兄袛?shù)據(jù)元素出隊
如上圖3所示，我們可以知道，在鏈?zhǔn)疥犃兄嘘狀^元素出隊，需要做以下 3 步操作：
- 通過 top 指針直接找到隊頭節(jié)點，創(chuàng)建一個新指針 p 指向此即將出隊的節(jié)點；
- 將 p 節(jié)點（即要出隊的隊頭節(jié)點）從鏈表中摘除；
- 釋放節(jié)點 p，回收其所占的內(nèi)存空間；
1.3.2 隊列鏈?zhǔn)酱鎯Φ拇a實現(xiàn)
- 鏈?zhǔn)疥犃械慕Y(jié)構(gòu)定義
//結(jié)點結(jié)構(gòu)
typedef struct KQueueNode{
KQueueElementType data;
struct KQueueNode *next;
}KQNode, *KQueuePtr;
//隊列的鏈表結(jié)構(gòu)
typedef struct KLinkQueue {
KQueuePtr front; //隊頭
KQueuePtr rear; //隊尾
}KLQueue;
1.3.2.1 初始化
// 1. 初始化隊列
KStatus initQueue(KLQueue *Q) {
//1. 隊列頭指針和尾指針都只需新生成的結(jié)點
Q->front = Q->rear = (KQueuePtr)malloc(sizeof(KQNode));
//2. 判斷結(jié)點是否創(chuàng)建成功
if (!Q->front) return ERROR;
//3. 隊列頭指針域置空
Q->front->next = NULL;
return OK;
}
1.3.2.2 銷毀隊列
// 2. 銷毀隊列
KStatus destoryQueue(KLQueue *Q) {
//遍歷整個隊列，銷毀每一個結(jié)點
while (Q->front) {
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return OK;
}
1.3.2.3 清空隊列
// 3. 清空隊列
KStatus clearQueue(KLQueue *Q) {
KQueuePtr p,q;
Q->rear = Q->front;
p = Q->front->next;
Q->front->next = NULL;
while (p) {
q = p->next;
p = p->next;
free(q);
}
return OK;
}
1.3.2.4 隊列判空
// 4. 隊列判空
KStatus isEmpty(KLQueue Q) {
return Q.front == Q.rear;
}
1.3.2.5 獲取對頭元素
// 6. 獲取對頭元素
KStatus getHead(KLQueue Q, KQueueElementType *e){
if (Q.front != Q.rear) {
//返回隊頭元素的值,隊頭指針不變
*e = Q.front->next->data;
return TRUE;
}
return FALSE;
}
1.3.2.6 獲取隊列長度
// 7. 獲取隊列長度
int getLength(KLQueue Q){
int count = 0;
KQueuePtr p = Q.front;
while (Q.rear != p) {
count++;
p = p->next;
}
return count;
}
1.3.2.7 入隊
// 8. 入隊
KStatus enQueue(KLQueue *Q, KQueueElementType e) {
//為入隊元素分配結(jié)點空間,用指針s指向;
KQueuePtr s = (KQueuePtr)malloc(sizeof(KQNode));
if (!s) return ERROR;
//將新結(jié)點s指定數(shù)據(jù)域
s->data = e;
s->next = NULL;
//將新結(jié)點插入到隊列尾部
Q->rear->next = s;
//修改隊尾指針
Q->rear = s;
return OK;
}
1.3.2.8 出隊
// 9. 出隊
KStatus deQueue(KLQueue *Q, KQueueElementType *e) {
KQueuePtr p;
//判斷隊列是否為空
if (isEmpty(*Q)) return ERROR;
//將要刪除的隊頭結(jié)點暫時存儲在p
p = Q->front->next;
//將要刪除的隊頭結(jié)點的值賦值給e
*e = p->data;
//將原隊列頭結(jié)點的后繼p->next 賦值給頭結(jié)點后繼
Q->front->next = p->next;
//若隊頭就是隊尾,則刪除后將rear指向頭結(jié)點.
if(Q->rear == p) Q->rear = Q->front;
//釋放結(jié)點
free(p);
return OK;
}
1.3.2.9 遍歷隊列
// 10. 遍歷隊列
KStatus traverseQueue(KLQueue Q) {
KQueuePtr p = Q.front->next;
while (p) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
return OK;
}
1.3.2.10 單元測試
// 11. 單元測試
void test() {
printf("鏈隊列的表示與操作!\n");
KStatus iStatus;
KQueueElementType d;
KLQueue q;
//1.初始化隊列q
iStatus = initQueue(&q);
//2. 判斷是否創(chuàng)建成
if (iStatus) {
printf("成功地構(gòu)造了一個空隊列\(zhòng)n");
}
//3.判斷隊列是否為空
printf("是否為空隊列?%d (1:是 0:否)\n",isEmpty(q));
//4.獲取隊列的長度
printf("隊列的長度為%d\n",getLength(q));
//5.插入元素到隊列中
enQueue(&q, -3);
enQueue(&q, 6);
enQueue(&q, 12);
printf("隊列的長度為%d\n",getLength(q));
printf("是否為空隊列?%d (1:是 0:否)\n",isEmpty(q));
//6.遍歷隊列
printf("隊列中的元素如下:\n");
traverseQueue(q);
//7.獲取隊列頭元素
iStatus = getHead(q, &d);
if (iStatus == OK) {
printf("隊頭元素是:%d\n",d);
}
//8.刪除隊頭元素
iStatus = deQueue(&q, &d);
if (iStatus == OK) {
printf("刪除了的隊頭元素為:%d\n",d);
}
//9.獲取隊頭元素
iStatus = getHead(q, &d);
if (iStatus == OK) {
printf("新的隊頭元素為:%d\n",d);
}
//10.清空隊列
clearQueue(&q);
//11.銷毀隊列
destoryQueue(&q);
}
- 單元測試，輸出結(jié)果：
Hello, World!
鏈隊列的表示與操作!
成功地構(gòu)造了一個空隊列
是否為空隊列?1 (1:是 0:否)
隊列的長度為0
隊列的長度為3
是否為空隊列?0 (1:是 0:否)
隊列中的元素如下:
-3 6 12
隊頭元素是:-3
刪除了的隊頭元素為:-3
新的隊頭元素為:6
Program ended with exit code: 0
1.3.2.11 完整代碼
//
// main.c
// 011_LinkQueue
//
// Created by 孔雨露 on 2020/4/18.
// Copyright ? 2020 Apple. All rights reserved.
//
/*
鏈?zhǔn)?隊列的基本操作實現(xiàn)
*/
#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20
typedef int KStatus;
typedef int KQueueElementType;
//結(jié)點結(jié)構(gòu)
typedef struct KQueueNode{
KQueueElementType data;
struct KQueueNode *next;
}KQNode, *KQueuePtr;
//隊列的鏈表結(jié)構(gòu)
typedef struct KLinkQueue {
KQueuePtr front; //隊頭
KQueuePtr rear; //隊尾
}KLQueue;
// 1. 初始化隊列
KStatus initQueue(KLQueue *Q) {
//1. 隊列頭指針和尾指針都只需新生成的結(jié)點
Q->front = Q->rear = (KQueuePtr)malloc(sizeof(KQNode));
//2. 判斷結(jié)點是否創(chuàng)建成功
if (!Q->front) return ERROR;
//3. 隊列頭指針域置空
Q->front->next = NULL;
return OK;
}
// 2. 銷毀隊列
KStatus destoryQueue(KLQueue *Q) {
//遍歷整個隊列，銷毀每一個結(jié)點
while (Q->front) {
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return OK;
}
// 3. 清空隊列
KStatus clearQueue(KLQueue *Q) {
KQueuePtr p,q;
Q->rear = Q->front;
p = Q->front->next;
Q->front->next = NULL;
while (p) {
q = p->next;
p = p->next;
free(q);
}
return OK;
}
// 4. 隊列判空
KStatus isEmpty(KLQueue Q) {
return Q.front == Q.rear;
}
// 6. 獲取對頭元素
KStatus getHead(KLQueue Q, KQueueElementType *e){
if (Q.front != Q.rear) {
//返回隊頭元素的值,隊頭指針不變
*e = Q.front->next->data;
return TRUE;
}
return FALSE;
}
// 7. 獲取隊列長度
int getLength(KLQueue Q){
int count = 0;
KQueuePtr p = Q.front;
while (Q.rear != p) {
count++;
p = p->next;
}
return count;
}
// 8. 入隊
KStatus enQueue(KLQueue *Q, KQueueElementType e) {
//為入隊元素分配結(jié)點空間,用指針s指向;
KQueuePtr s = (KQueuePtr)malloc(sizeof(KQNode));
if (!s) return ERROR;
//將新結(jié)點s指定數(shù)據(jù)域
s->data = e;
s->next = NULL;
//將新結(jié)點插入到隊列尾部
Q->rear->next = s;
//修改隊尾指針
Q->rear = s;
return OK;
}
// 9. 出隊
KStatus deQueue(KLQueue *Q, KQueueElementType *e) {
KQueuePtr p;
//判斷隊列是否為空
if (isEmpty(*Q)) return ERROR;
//將要刪除的隊頭結(jié)點暫時存儲在p
p = Q->front->next;
//將要刪除的隊頭結(jié)點的值賦值給e
*e = p->data;
//將原隊列頭結(jié)點的后繼p->next 賦值給頭結(jié)點后繼
Q->front->next = p->next;
//若隊頭就是隊尾,則刪除后將rear指向頭結(jié)點.
if(Q->rear == p) Q->rear = Q->front;
//釋放結(jié)點
free(p);
return OK;
}
// 10. 遍歷隊列
KStatus traverseQueue(KLQueue Q) {
KQueuePtr p = Q.front->next;
while (p) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
return OK;
}
// 11. 單元測試
void test() {
printf("鏈隊列的表示與操作!\n");
KStatus iStatus;
KQueueElementType d;
KLQueue q;
//1.初始化隊列q
iStatus = initQueue(&q);
//2. 判斷是否創(chuàng)建成
if (iStatus) {
printf("成功地構(gòu)造了一個空隊列\(zhòng)n");
}
//3.判斷隊列是否為空
printf("是否為空隊列?%d (1:是 0:否)\n",isEmpty(q));
//4.獲取隊列的長度
printf("隊列的長度為%d\n",getLength(q));
//5.插入元素到隊列中
enQueue(&q, -3);
enQueue(&q, 6);
enQueue(&q, 12);
printf("隊列的長度為%d\n",getLength(q));
printf("是否為空隊列?%d (1:是 0:否)\n",isEmpty(q));
//6.遍歷隊列
printf("隊列中的元素如下:\n");
traverseQueue(q);
//7.獲取隊列頭元素
iStatus = getHead(q, &d);
if (iStatus == OK) {
printf("隊頭元素是:%d\n",d);
}
//8.刪除隊頭元素
iStatus = deQueue(&q, &d);
if (iStatus == OK) {
printf("刪除了的隊頭元素為:%d\n",d);
}
//9.獲取隊頭元素
iStatus = getHead(q, &d);
if (iStatus == OK) {
printf("新的隊頭元素為:%d\n",d);
}
//10.清空隊列
clearQueue(&q);
//11.銷毀隊列
destoryQueue(&q);
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
test();
return 0;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。
相關(guān)閱讀更多精彩內(nèi)容
- 這里我們只介紹線性表中 存儲結(jié)構(gòu)不同的 順序表 和 鏈表，以及操作受限的 棧 和 隊列 。 數(shù)據(jù)結(jié)構(gòu)與算法系列文章...
- 一、棧 1.1 棧的定義 棧（Stack）：只允許在一端進(jìn)行插入或刪除操作的線性表。首先棧是一種線性表，但是限定這...
- 隊列 隊列的基本概念 隊列是一種操作受限的線性表，只允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除；向隊列中插入元...
- 1、隊列的基本概念 和堆棧一樣隊列也是一種特殊的線性表，隊列的數(shù)據(jù)元素及數(shù)據(jù)元素間的邏輯關(guān)系和線性表是完全相同的，...
- 定義 隊列(Queue)是只允許在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作的線性表。 隊列是一種先進(jìn)先出(First...
