网站左侧导航源码,佛山省钱网站设计哪家便宜,安阳网站制作 网络服务,建设网站的题目个人主页#xff1a;17_Kevin-CSDN博客 专栏#xff1a;《数据结构》 一、队列的概念和结构
队列是只允许在一端进行插入数据操作#xff0c;在另一端进行删除数据操作的特殊线性表#xff0c;队列具有先进先出 FIFO(First In First Out) 入队列#xff1a;进行插入操作的… 个人主页17_Kevin-CSDN博客 专栏《数据结构》 一、队列的概念和结构
队列是只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头 二、队列的操作 队列有以下几种常见的操作 入队Enqueue将一个元素添加到队尾。出队Dequeue从队头删除并返回一个元素。查看队头元素Front返回队头元素但不删除它。查看队尾元素Rear返回队尾元素但不删除它。判断队列是否为空Empty返回队列是否为空。清空队列Clear删除队列中的所有元素。 三、队列的实现 1. 实现方法的选择 队列可以使用多种数据结构来实现如数组、链表等。
但是用链表实现队列效果更优因为如果是数组的话队列每次需要从头上出数据这样就需要将数组后面的数据依次往前挪动这样会增加时间复杂度不如使用链表直接free掉队头数据快捷。 2. 代码实现 2.0 创建队列结构
typedef int QDataType;typedef struct QueueNode
{int val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
创建一个结构体类型QNode来作为队列中每个节点的数据存储结构体用Queue作为存储队头和队尾还有队列长度的结构体类型。 2.1 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}
和链表的初始化大同小异。 2.2 队列的销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}
首先检查传入的pq队列是不是已经没有数据了然后创建一个Queue类型的变量cur和next用来遍历销毁队列。在循环中用next来指向cur的下一个数据然后free掉现在cur的数据持续推动向前一个接一个销毁。
在 while (cur) 循环结束后cur 确实已经被设置为 NULL但是将队列的头指针和尾指针都设置为 NULL 是为了确保队列的状态被正确地重置为空闲状态。
即使 cur 已经是 NULL队列的其他成员变量如 size仍然可能包含不正确的值。通过将头指针和尾指针都设置为 NULL可以确保队列被完全清空并避免任何潜在的错误或未初始化的状态。 2.3 入队列
// 入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail){pq-ptail-next newnode;//将当前尾的next设置为newnodepq-ptail newnode;//更新pq的尾节点所以当前尾节点为newnode}else{pq-phead pq-ptail newnode;}pq-size;
}
在创建空间并分配后根据队列的当前状态进行不同的操作。如果队列的尾指针 pq-ptail 不为 NULL则将 newnode 插入到队列的尾部。首先将 pq-ptail-next 设置为 newnode将 newnode 连接到队列的尾部。然后将 pq-ptail 更新为 newnode以便后续的操作可以正确地找到队列的尾部。如果队列的尾指针为 NULL表示队列为空此时将 newnode 设置为队列的头指针和尾指针即 pq-phead pq-ptail newnode。 2.4 出队列
// 出队列
void QueuePop(Queue* pq)
{assert(pq);// 0个节点// 温柔检查//if (pq-phead NULL)// return;// 暴力检查 assert(pq-phead ! NULL);// 一个节点// 多个节点if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
} 2.5 返回队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);// 暴力检查 assert(pq-phead ! NULL);return pq-phead-val;
} 2.6 返回队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);// 暴力检查 assert(pq-ptail ! NULL);return pq-ptail-val;
} 四、队列的应用场景 队列在计算机科学中有许多应用场景以下是一些常见的例子消息队列在分布式系统中消息队列用于在不同的进程或节点之间传递消息。 任务队列在操作系统中任务队列用于调度和执行任务。缓冲区在输入输出操作中队列可以用作缓冲区暂存输入数据或输出数据。优先队列优先队列是一种特殊的队列其中元素按照某种优先级排序。在搜索引擎中优先队列可以用于对搜索结果进行排序。 Im Kevin, and well see you next time
