目錄

一.隊列概念及結(jié)構

1.1隊列的概念

1.2隊列的結(jié)構

二.隊列的實現(xiàn)

2.1頭文件

2.2鏈式隊列的結(jié)構定義

2.3隊列接口的定義

2.4初始化隊列

2.5判斷隊列是否為空

2.6銷毀隊列

2.7隊尾入隊列

2.8隊頭出隊列

2.9獲取隊列頭部元素

2.10獲取隊列隊尾元素

2.11獲取隊列中有效元素個數(shù)

2.12打印隊列元素

Test.c

Queue.h

Queue.c

---

一.隊列概念及結(jié)構

1.1隊列的概念

二.隊列的實現(xiàn)

隊列也可以數(shù)組和鏈表的結(jié)構實現(xiàn)，使用鏈表的結(jié)構實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結(jié)構，出隊列在數(shù)組頭上出數(shù)據(jù)，效率會比較低

2.1頭文件

#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>

2.2鏈式隊列的結(jié)構定義

typedef int QDataType;
typedef struct QueueNode
{	QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//表示隊列整體,一個是出數(shù)據(jù)，一個是入數(shù)據(jù).

? QueueNode結(jié)構體表示隊列中的節(jié)點，每個節(jié)點包含一個數(shù)據(jù)項?data?和一個指向下一個節(jié)點的指針?next。Queue結(jié)構體表示整個隊列，包含指向隊列頭部和尾部節(jié)點的指針?phead?和?ptail，以及記錄隊列大小的變量?size

2.3隊列接口的定義

void QueueInit(Queue* pq);// 初始化隊列void QueueDestroy(Queue* pq);// 銷毀隊列void QueuePush(Queue* pq, QDataType x);// 隊尾入隊列void QueuePop(Queue* pq);// 隊頭出隊列QDataType QueueFront(Queue* pq);// 獲取隊列頭部元素QDataType QueueBack(Queue* pq);// 獲取隊列隊尾元素int QueueSize(Queue* pq);// 獲取隊列中有效元素個數(shù)bool QueueEmpty(Queue* pq);// 檢測隊列是否為空，如果為空返回非零結(jié)果，如果非空返回0

2.4初始化隊列

void QueueInit(Queue* pq)
{assert(pq);// 檢查指針是否為空pq->phead=NULL; //將隊列的頭指針置為空pq->ptail = NULL;//將隊列的尾指針置為空pq->size = 0;// 將隊列的頭指針置為空
}

2.5判斷隊列是否為空

bool QueueEmpty(Queue* pq)
{assert(pq);//方法一,將隊列的頭指針以及尾指針置空//return pq->phead = NULL && pq->ptail==NULL;//方法二,將隊列的有效元素置空return pq->size == 0;
}

2.6銷毀隊列

代碼解析:

1. assert(pq)?用于斷言?pq?指針不為空，確保傳入的指針有效。

2. 創(chuàng)建一個指針?cur，并將其初始化為隊列的頭指針?pq->phead。

3. 進入循環(huán)，遍歷隊列中的每個節(jié)點。

4. 在循環(huán)中，首先保存當前節(jié)點的下一個節(jié)點指針為?next，以便在釋放當前節(jié)點后能夠訪問下一個節(jié)點。

5. 使用?free(cur)?釋放當前節(jié)點的內(nèi)存。

6. 將指針?cur?移動到下一個節(jié)點，即?cur = next。

7. 循環(huán)繼續(xù)，直到遍歷完隊列中的所有節(jié)點。

8. 在循環(huán)結(jié)束后，將隊列的頭指針和尾指針?pq->phead、pq->ptail?都置為空，表示隊列已經(jīng)為空。

9. 將隊列的大小?pq->size?置為 0，表示隊列中沒有元素。

void QueueDestroy(Queue* pq)
{assert(pq);// 檢查指針是否為空QNode* cur = pq->phead;// 創(chuàng)建一個指針 cur，指向隊列的頭指針while (cur){QNode* next = cur->next;// 創(chuàng)建一個指針 cur，指向隊列的頭指針free(cur);// 釋放當前節(jié)點的內(nèi)存cur = next;// 將指針 cur 移動到下一個節(jié)點}pq->phead = pq->ptail = NULL;// 將隊列的頭指針和尾指針置為空pq->size = 0;// 將隊列的大小置為0
}

2.7隊尾入隊列

第一種情況:尾插第一個隊列元素

第二種情況:已有元素前提下尾插節(jié)點

先尾插節(jié)點，后把新節(jié)點的地址給ptail(讓ptail指向新節(jié)點)

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));// 創(chuàng)建一個新的節(jié)點if (newnode == NULL){perror("malloc fail\n");// 檢查內(nèi)存分配是否成功return;}newnode->data = x;// 設置新節(jié)點的數(shù)據(jù)為傳入的元素值newnode->next = NULL;// 將新節(jié)點的指針域置空//一個節(jié)點if (pq->ptail == NULL)// 判斷隊列是否為空{(diào)assert(pq->phead == NULL);// 如果隊列為空，頭指針也應為空pq->phead = pq->ptail = newnode;// 將新節(jié)點同時設置為隊列的頭節(jié)點和尾節(jié)點}//多個節(jié)點else{pq->ptail->next = newnode;// 將新節(jié)點同時設置為隊列的頭節(jié)點和尾節(jié)點pq->ptail = newnode;// 更新隊列的尾指針為新節(jié)點}pq->size++;// 增加隊列的大小計數(shù)
}

代碼執(zhí)行:?

2.8隊頭出隊列

第一種:隊列只有一個元素時

第二種:隊列有多個元素時

void QueuePop(Queue* pq)
{assert(pq);// 檢查指針是否為空assert(!QueueEmpty(pq));// 檢查隊列是否非空assert(pq->phead);// 檢查隊列的頭指針是否存在//1.一個節(jié)點if (pq->phead->next == NULL) // 隊列只有一個節(jié)點的情況{free(pq->phead); // 釋放隊列頭節(jié)點的內(nèi)存pq->phead = pq->ptail = NULL;// 將隊列的頭指針和尾指針置為空}//2.多個節(jié)點else{QNode* next = pq->phead->next; //保存隊列頭節(jié)點的下一個節(jié)點指針free(pq->phead);// 釋放隊列頭節(jié)點的內(nèi)存pq->phead = next;// 更新隊列的頭指針為下一個節(jié)點}pq->size--;//減少隊列的大小計數(shù)
}

代碼執(zhí)行:?

2.9獲取隊列頭部元素

QDataType QueueFront(Queue* pq)
{assert(pq);// 檢查指針是否為空assert(!QueueEmpty(pq));// 檢查隊列是否非空assert(pq->phead);// 檢查隊列的頭指針是否存在return pq->phead->data;// 返回隊列頭節(jié)點的數(shù)據(jù)
}

代碼執(zhí)行:

2.10獲取隊列隊尾元素

QDataType QueueBack(Queue* pq)
{assert(pq);// 檢查隊列是否非空assert(!QueueEmpty(pq));// 檢查隊列是否非空assert(pq->ptail);// 檢查隊列的尾指針是否存在return pq->ptail->data;//返回隊列尾節(jié)點的數(shù)據(jù)
}

代碼執(zhí)行:

2.11獲取隊列中有效元素個數(shù)

int QueueSize(Queue* pq)
{assert(pq);//檢查指針是否為空return pq->size;//返回隊列的大小（元素個數(shù)）
}

代碼執(zhí)行:

2.12打印隊列元素

void QPrint(Queue* pq)
{assert(pq);QNode* cur = pq->phead;QNode* next = cur;while (cur != NULL){printf("%d ", cur->data);cur = cur->next;}
}

代碼執(zhí)行:?

Test.c

#include"Queue.h"
void TestQueue1()//元素入隊列
{Queue q;QueueInit(&q);QueuePush(&q,1);QueuePush(&q,2);	//printf("%d ", QueueFront(&q));//QueuePop(&q);QueuePush(&q,3);QueuePush(&q,4);//printf("Size:%d\n", QueueSize(&q));//QPrint(&q);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");
}
void TestQueue2()//元素出隊列
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);printf("%d\n", QueueFront(&q));QueuePop(&q);printf("%d\n", QueueFront(&q));QueuePop(&q);printf("%d\n", QueueFront(&q));QueuePop(&q);printf("%d\n", QueueFront(&q));printf("\n");
}
void TestQueue3()//獲取隊列頭部和尾部元素,和隊列元素個數(shù)
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);printf("隊列頭部元素:%d\n",QueueFront(&q));printf("隊列尾部元素:%d\n", QueueBack(&q));printf("Size:%d\n", QueueSize(&q));/*while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}*/printf("\n");
}
void TestQueue4()//打印隊列
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QPrint(&q);printf("\n");
}
int main()
{//TestQueue1();//元素入隊列//TestQueue2();//元素出隊列//TestQueue3();//獲取隊列頭部和尾部元素,和隊列元素個數(shù)TestQueue4();
}

Queue.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{	QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//表示隊列整體,一個是出數(shù)據(jù)，一個是入數(shù)據(jù).void QueueInit(Queue* pq);// 初始化隊列
void QueueDestroy(Queue* pq);// 銷毀隊列
void QueuePush(Queue* pq, QDataType x);// 隊尾入隊列
void QueuePop(Queue* pq);// 隊頭出隊列
QDataType QueueFront(Queue* pq);// 獲取隊列頭部元素
QDataType QueueBack(Queue* pq);// 獲取隊列隊尾元素
int QueueSize(Queue* pq);// 獲取隊列中有效元素個數(shù)
bool QueueEmpty(Queue* pq);// 檢測隊列是否為空，如果為空返回非零結(jié)果，如果非空返回0

Queue.c

#include"Queue.h"
void QueueInit(Queue* pq)
{assert(pq);// 檢查指針是否為空pq->phead=NULL; // 將隊列的頭指針置為空pq->ptail = NULL;// 將隊列的頭指針置為空pq->size = 0;// 將隊列的頭指針置為空
}void QPrint(Queue* pq)
{assert(pq);QNode* cur = pq->phead;QNode* next = cur;while (cur != NULL){printf("%d ", cur->data);cur = cur->next;}
}void QueueDestroy(Queue* pq)
{assert(pq);// 檢查指針是否為空QNode* cur = pq->phead;// 創(chuàng)建一個指針 cur，指向隊列的頭指針while (cur){QNode* next = cur->next;// 創(chuàng)建一個指針 cur，指向隊列的頭指針free(cur);// 釋放當前節(jié)點的內(nèi)存cur = next;// 將指針 cur 移動到下一個節(jié)點}pq->phead = pq->ptail = NULL;// 將隊列的頭指針和尾指針置為空pq->size = 0;// 將隊列的大小置為0
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));// 創(chuàng)建一個新的節(jié)點if (newnode == NULL){perror("malloc fail\n");// 檢查內(nèi)存分配是否成功return;}newnode->data = x;// 設置新節(jié)點的數(shù)據(jù)為傳入的元素值newnode->next = NULL;// 將新節(jié)點的指針域置空//一個節(jié)點//多個節(jié)點if (pq->ptail == NULL)// 判斷隊列是否為空{(diào)assert(pq->phead == NULL);// 如果隊列為空，頭指針也應為空pq->phead = pq->ptail = newnode;// 將新節(jié)點同時設置為隊列的頭節(jié)點和尾節(jié)點}else{pq->ptail->next = newnode;// 將新節(jié)點同時設置為隊列的頭節(jié)點和尾節(jié)點pq->ptail = newnode;// 更新隊列的尾指針為新節(jié)點}pq->size++;// 增加隊列的大小計數(shù)
}void QueuePop(Queue* pq)
{assert(pq);// 檢查指針是否為空assert(!QueueEmpty(pq));// 檢查隊列是否非空assert(pq->phead);// 檢查隊列的頭指針是否存在//1.一個節(jié)點if (pq->phead->next == NULL) // 隊列只有一個節(jié)點的情況{free(pq->phead); // 釋放隊列頭節(jié)點的內(nèi)存pq->phead = pq->ptail = NULL;// 將隊列的頭指針和尾指針置為空}else{//頭刪QNode* next = pq->phead->next; //保存隊列頭節(jié)點的下一個節(jié)點指針free(pq->phead);// 釋放隊列頭節(jié)點的內(nèi)存pq->phead = next;// 更新隊列的頭指針為下一個節(jié)點}pq->size--;//減少隊列的大小計數(shù)
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));// 檢查隊列是否非空assert(pq->phead);// 檢查隊列的頭指針是否存在return pq->phead->data;// 返回隊列頭節(jié)點的數(shù)據(jù)
}QDataType QueueBack(Queue* pq)
{assert(pq);// 檢查隊列是否非空assert(!QueueEmpty(pq));// 檢查隊列是否非空assert(pq->phead);// 檢查隊列的頭指針是否存在return pq->ptail->data;//返回隊列尾節(jié)點的數(shù)據(jù)
}int QueueSize(Queue* pq)
{assert(pq);//檢查指針是否為空return pq->size;//返回隊列的大小（元素個數(shù)）
}
bool QueueEmpty(Queue* pq)
{assert(pq);//方法一,將隊列的頭指針以及尾指針置空//return pq->phead = NULL && pq->ptail==NULL;//方法二,將隊列的有效元素置空return pq->size == 0;
}

? ? ? ? 本篇結(jié)束，如有錯誤，歡迎大家指正，感謝來訪！