数据结构（初阶）（六）----队列

队列

队列概念与结构队列的实现头文件`Queue.h`实现`Queue.c`队列与结点结构打印初始化销毁入队队列判空出队取队头元素取队尾元素队列有效数据个数 测试文件`test.c`

概念与结构

概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 的原则。

⼊队列：进⾏插⼊操作的⼀端称为队尾

出队列：进⾏删除操作的⼀端称为队头

队列底层结构选型

队列也可以数组和链表的结构实现，使⽤链表的结构实现更优⼀些，因为如果使⽤数组的结构，出队列在数组头上出数据，效率会⽐较低。

队列的实现 头文件Queue.h #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> //队列结点结构 typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QueueNode; //队列结构 typedef struct Queue { QueueNode* phead; //队头 QueueNode* ptail; //队尾 int size; //记录有效数据个数 }Queue; //打印队列 void QueuePrint(Queue* pq); //初始化 void QueueInit(Queue* pq); //销毁 void QueueDestory(Queue* pq); //入队 void QueuePush(Queue* pq, QDataType x); //队列判空 bool QueueEmpty(Queue* pq); //出队 void QueuePop(Queue* pq); //取队头元素 QDataType QueueFront(Queue* pq); //取队尾元素 QDataType QueueBack(Queue* pq); //队列有效数据个数 int QueueSize(Queue* pq); 实现Queue.c 队列与结点结构 //队列结点结构 typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QueueNode; //队列结构 typedef struct Queue { QueueNode* phead; //队头 QueueNode* ptail; //队尾 int size; //记录有效数据个数 }Queue; 打印 //打印队列 void QueuePrint(Queue* pq) { assert(pq); QueueNode* pcur = pq->phead; while (pcur) { printf("%d ", pcur->data); pcur = pcur->next; } printf("\n"); } 初始化 //初始化 void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } 销毁 //销毁 void QueueDestory(Queue* pq) { assert(pq); QueueNode* pcur = pq->phead; while (pcur) { QueueNode* next = pcur->next; free(pcur); pcur = next; } pq->phead = pq->ptail = NULL; } 入队 //入队 void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); if (newNode == NULL) { perror("malloc fail"); exit(1); } newNode->data = x; newNode->next = NULL; //队列为空 if (pq->phead == NULL) { pq->phead = pq->ptail = newNode; }else{//不为空 pq->ptail->next = newNode; pq->ptail = pq->ptail->next; } ++pq->size; } 队列判空 //队列判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == 0; } 出队 //出队 void QueuePop(Queue* pq) { assert(!QueueEmpty(pq)); //出队的是头结点 //当队列中只有一个结点时 if (pq->phead == pq->ptail) { free(pq->phead); pq->phead = pq->ptail = NULL; }else { QueueNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } --pq->size; } 取队头元素 //取队头元素 QDataType QueueFront(Queue* pq) { assert(pq); return pq->phead->data; } 取队尾元素 //取队尾元素 QDataType QueueBack(Queue* pq) { assert(pq); return pq->ptail->data; } 队列有效数据个数

可以选择遍历队列，但是使用size次数较多，循环遍历，额外浪费时间 也可以在定义队列结构时，加上int size作为计数器

//队列有效数据个数 //int QueueSize(Queue* pq) //{ // int size = 0; // QueueNode* pcur = pq->phead; // while (pcur) // { // ++size; // pcur = pcur->next; // } // return size; //} int QueueSize(Queue* pq) { return pq->size; } 测试文件test.c #define _CRT_SECURE_NO_WARNINGS #include"Queue.h" void test1() { Queue q; //初始化 QueueInit(&q); //入队 QueuePush(&q,1); QueuePush(&q,2); QueuePush(&q,3); QueuePush(&q,4); //打印队列 QueuePrint(&q); 出队 //QueuePop(&q); //QueuePop(&q); //QueuePop(&q); //取队头元素 QDataType head = QueueFront(&q); printf("队头元素：%d\n", head); //取队头元素 QDataType tail = QueueBack(&q); printf("队尾元素：%d\n", tail); //队列有效数据个数 int size = QueueSize(&q); printf("有效数据个数：%d\n", size); //销毁 QueueDestory(&q); } int main() { test1(); return 0; }