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