数据结构之队列

1. 队列的概念及结构

1.1 队列的概念

队列：只允许在一段进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

1.2 队列的结构

2. 队列的实现

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

2.1 链式队列的结构定义

typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue;//表示队列整体,一个是出数据，一个是入数据.

QueueNode结构体表示队列中的节点，每个节点包含一个数据项 data 和一个指向下一个节点的指针 next。Queue结构体表示整个队列，包含指向队列头部和尾部节点的指针 phead 和 ptail，以及记录队列大小的变量 size

2.2 队列接口的定义

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);// 获取队列中有效元素个数 bool QueueEmpty(Queue* pq);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0

2.3 初始化队列

void QueueInit(Queue* pq) { assert(pq);// 检查指针是否为空 pq->phead=NULL; //将队列的头指针置为空 pq->ptail = NULL;//将队列的尾指针置为空 pq->size = 0;// 将队列的头指针置为空 }

2.4 判断队列是否为空

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

2.5 销毁队列

void QueueDestroy(Queue* pq) { assert(pq);// 检查指针是否为空 QNode* cur = pq->phead;// 创建一个指针 cur，指向队列的头指针 while (cur) { QNode* next = cur->next;// 创建一个指针 cur，指向队列的头指针 free(cur);// 释放当前节点的内存 cur = next;// 将指针 cur 移动到下一个节点 } pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空 pq->size = 0;// 将队列的大小置为0 }

2.6 队尾入队列

第一种情况：尾插第一个队列元素

第二种情况：已有元素前提下尾插节点

先尾插节点，后把新节点的地址给ptail

void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode));// 创建一个新的节点 if (newnode == NULL) { perror("malloc fail\n");// 检查内存分配是否成功 return; } newnode->data = x;// 设置新节点的数据为传入的元素值 newnode->next = NULL;// 将新节点的指针域置空 //一个节点 if (pq->ptail == NULL)// 判断队列是否为空 { assert(pq->phead == NULL);// 如果队列为空，头指针也应为空 pq->phead = pq->ptail = newnode;// 将新节点同时设置为队列的头节点和尾节点 } //多个节点 else { pq->ptail->next = newnode;// 将新节点同时设置为队列的头节点和尾节点 pq->ptail = newnode;// 更新队列的尾指针为新节点 } pq->size++;// 增加队列的大小计数 }

2.7 队头出队列

第一种：队列只有一个元素时

第二种：队列有多个元素时

void QueuePop(Queue* pq) { assert(pq);// 检查指针是否为空 assert(!QueueEmpty(pq));// 检查队列是否非空 assert(pq->phead);// 检查队列的头指针是否存在 //1.一个节点 if (pq->phead->next == NULL) // 队列只有一个节点的情况 { free(pq->phead); // 释放队列头节点的内存 pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空 } //2.多个节点 else { QNode* next = pq->phead->next; //保存队列头节点的下一个节点指针 free(pq->phead);// 释放队列头节点的内存 pq->phead = next;// 更新队列的头指针为下一个节点 } pq->size--;//减少队列的大小计数 }

2.8 获取队列的头部元素

QDataType QueueFront(Queue* pq) { assert(pq);// 检查指针是否为空 assert(!QueueEmpty(pq));// 检查队列是否非空 assert(pq->phead);// 检查队列的头指针是否存在 return pq->phead->data;// 返回队列头节点的数据 }

2.9 获取队列队尾元素

QDataType QueueBack(Queue* pq) { assert(pq);// 检查队列是否非空 assert(!QueueEmpty(pq));// 检查队列是否非空 assert(pq->ptail);// 检查队列的尾指针是否存在 return pq->ptail->data;//返回队列尾节点的数据 }

2.10 获取队列中有效元素个数

int QueueSize(Queue* pq) { assert(pq);//检查指针是否为空 return pq->size;//返回队列的大小（元素个数） }

2.11 打印队列元素

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