手机网站引导页js英文网站搜索

当前位置： 首页 > news >正文

手机网站引导页js,英文网站搜索,电子政务网站建设,ui基础教程入门大家好#xff0c;我是小卡皮巴拉 文章目录 目录 引言 一.队列的基本概念 1.1 队列的定义 1.2 队列的特性 1.3 队列的基本操作 二.队列的实现方式 2.1 基于链表的队列 2.2 基于数组的队列 三.基于链表的队列实现 定义链表队列的结构 初始化 入队列——向队列中插… 大家好我是小卡皮巴拉  文章目录 目录 引言 一.队列的基本概念 1.1 队列的定义 1.2 队列的特性 1.3 队列的基本操作 二.队列的实现方式 2.1 基于链表的队列 2.2 基于数组的队列 三.基于链表的队列实现 定义链表队列的结构 初始化 入队列——向队列中插入数据 队列判空 队列有效元素个数 出队列——从队列中删除数据 取队头数据 取队尾数据 销毁队列 兄弟们共勉    每篇前言 博客主页小卡皮巴拉  咱的口号小比特大梦想 作者请求由于博主水平有限难免会有错误和不准之处我也非常渴望知道这些错误恳请大佬们批评斧正。 引言 想象一下你在超市排队结账每个人都按顺序等待先到的先结账。这种排队的方式其实就是数据结构中的“队列”。队列简单来说就是数据按照到达的顺序排队先到的先处理。 在编程中队列帮助我们管理一系列的任务或数据确保它们按照正确的顺序被执行或处理。无论是处理用户请求、管理打印任务还是在算法中进行搜索队列都发挥着重要的作用。 现在让我们一起探索这个简单而强大的数据结构了解它的原理和应用看看它是如何在编程世界中为我们服务的。 一.队列的基本概念 1.1 队列的定义 队列Queue是一种特殊的数据结构它按照元素进入的顺序进行排列并遵循先进先出FIFO, First In First Out的原则。队列可以被看作是一个有序的元素集合其中元素的添加入队发生在集合的一端通常称为“队尾”而元素的移除出队则发生在另一端通常称为“队头”。 1.2 队列的特性 先进先出FIFO这是队列最显著的特点。元素按照加入队列的顺序被处理即最早进入队列的元素会最先被移除。 有序性由于FIFO原则队列中的元素始终保持有序状态。 动态性队列的大小可以动态变化。在需要时可以向队列中添加新元素入队也可以从队列中移除元素出队。 边界条件队列有两个重要的边界条件——空队列和满队列对于有限队列。空队列表示队列中没有元素而满队列表示队列已达到其最大容量无法再添加新元素。然而在实际应用中更常见的是通过动态调整或循环使用空间来避免真正的“满”状态。
1.3 队列的基本操作 入队Enqueue向队列中添加一个新元素的操作。通常发生在队尾。 操作结果队列的长度增加1。时间复杂度在大多数情况下入队操作的时间复杂度为O(1)即常数时间。 出队Dequeue从队列中移除一个元素的操作。通常发生在队头。 操作结果队列的长度减少1并返回被移除的元素。时间复杂度同样地在大多数情况下出队操作的时间复杂度也为O(1)。 查看队头元素Front/Peek获取队列头部的元素但不移除它。 操作结果返回队列头部的元素。时间复杂度在大多数情况下查看队头元素的时间复杂度为O(1)。 检查队列是否为空IsEmpty判断队列中是否包含元素。 操作结果返回一个布尔值表示队列是否为空。时间复杂度检查队列是否为空的操作通常也是O(1)的。 获取队列的大小Size返回队列中当前包含的元素数量。 操作结果返回一个整数表示队列的大小。时间复杂度获取队列大小的操作通常是O(1)的。 二.队列的实现方式 队列的实现方式主要有两种 2.1 基于链表的队列 实现方式 链表队列使用节点Node来存储数据每个节点包含数据部分和指向下一个节点的指针。队列包含两个指针分别指向队头和队尾。入队操作在队尾添加新节点出队操作移除队头节点。 优势 动态性链表队列可以动态调整大小无需预分配固定空间。内存利用率没有固定的空间限制可以根据需要分配和释放内存。插入和删除效率高在链表中插入和删除元素只需调整指针时间复杂度为O(1)。 劣势 内存开销每个节点都需要额外的指针空间增加了内存开销。访问效率低由于链表不是连续存储的访问特定位置的元素需要从头节点开始遍历时间复杂度较高。 2.2 基于数组的队列 实现方式 数组队列使用固定大小的数组来存储元素并使用两个索引如front和rear来指示队头和队尾的位置。入队操作在队尾添加元素出队操作移除队头元素。当数组空间不足时可以进行扩容操作但通常不常见因为扩容会导致性能下降。更常见的是采用循环队列的方式当队尾到达数组末尾时回到数组开头继续添加元素。 优势 内存利用率高数组是连续存储的内存利用率较高没有额外的指针开销。访问效率高可以通过索引直接访问数组中的元素时间复杂度为O(1)。实现简单数组队列的实现相对简单不需要处理复杂的指针操作。 劣势 固定大小数组队列的大小是固定的需要提前分配足够的空间。如果空间不足可能导致性能下降或内存溢出。扩容成本高虽然可以采用扩容的方式来解决空间不足的问题但扩容会导致额外的内存分配和数据复制操作成本较高。假溢出在普通数组队列中当队尾指针达到数组末尾时即使数组中间还有空闲空间也无法继续入队导致“假溢出”现象。循环队列可以解决这个问题但实现相对复杂一些。 一般情况下基于链表的队列实现更加常见下面我们来给出基于链表的队列的实现。 三.基于链表的队列实现 定义链表队列的结构 首先我们定义了一个名为QDataType的类型别名它基于int类型。这个类型别名将用于队列中存储的数据元素。 接着我们定义了一个名为QueueNode的结构体它代表队列中的一个节点。这个结构体包含以下两个成员 data这是一个QDataType类型的变量用于存储队列节点的数据。next这是一个指向QueueNode类型的指针它指向队列中的下一个节点。如果这是队列的最后一个节点则此指针通常被设置为NULL。 然后我们定义了一个名为Queue的结构体通过typedef我们也可以用Queue来直接引用它而不需要使用struct关键字。这个结构体代表了一个队列的数据结构并包含以下三个成员 phead这是一个指向QueueNode类型的指针它指向队列的头部即队列中第一个进入的元素所在的节点。如果队列为空则此指针通常被设置为NULL。ptail这是一个指向QueueNode类型的指针它指向队列的尾部即队列中最后一个进入的元素所在的节点。这个指针使得我们可以在队列的尾部高效地添加新元素。如果队列为空则此指针也通常被设置为NULL。size这是一个整型变量表示队列中有效元素的个数。这个值在队列的操作过程中会动态变化并且提供了队列当前长度的直接信息。 函数代码 typedef int QDataType; //定义队列结点的结构 typedef struct QueueNode {QDataType data;struct QueueNode* next; }QueueNode;//定义队列的结构 typedef struct Queue {QueueNode* phead;//队头QueueNode* ptail;//队尾int size; //队列有效元素个数 }Queue; 初始化 函数名称QueueInit 函数目的初始化一个队列为其分配必要的资源并设置初始状态。 函数参数 Queue* pq这是一个指向Queue结构体的指针指向需要被初始化的队列。 函数体详细解析 参数有效性检查 使用assert(pq);语句来确保传入的指针pq是有效的。如果pq为NULL则程序会终止并显示错误信息。初始化队列头部和尾部指针 将pq-phead和pq-ptail都设置为NULL表示队列在初始化时是空的没有节点。初始化队列大小 将pq-size设置为0表示队列中没有元素。 通过QueueInit函数的执行一个队列被成功初始化其头部和尾部指针均指向NULL且队列大小为0表示队列当前为空且已准备好进行后续的入队和出队操作。 函数代码 //初始化 void QueueInit(Queue* pq) {assert(pq);pq-phead pq-ptail NULL;pq-size 0; } 入队列——向队列中插入数据 函数名称QueuePush 函数目的向队列中添加一个新元素。 函数参数 Queue* pq指向需要添加元素的队列的指针。QDataType x需要被添加到队列中的元素值。 函数体详细解析 参数有效性检查 使用assert(pq);语句来确保传入的队列指针pq是有效的。如果pq为NULL则程序会终止并显示错误信息由断言机制提供。内存分配 通过malloc(sizeof(QueueNode))为新的队列节点分配内存。sizeof(QueueNode)计算了QueueNode结构体所需的内存大小。将分配的内存地址转换为QueueNode类型并赋值给newnode指针。检查malloc是否成功分配了内存。如果newnode为NULL则表示内存分配失败。此时程序通过perror函数输出错误信息并通过exit(1)终止执行。初始化新节点 将传入的元素值x赋值给新节点的data成员。将新节点的next成员设置为NULL表示这是队列中的最后一个节点至少在当前添加操作完成时是这样。更新队列的队尾和队头指针 如果队列为空即pq-phead NULL则将队头和队尾指针都指向新节点newnode。如果队列不为空则将当前队尾节点的next指针指向新节点newnode并更新队尾指针pq-ptail使其指向新节点。这里有一个潜在的优化点可以直接将pq-ptail newnode;因为在上一步已经确保了pq-ptail-next newnode;。不过原代码中的写法在逻辑上也是正确的只是稍微多了一次对pq-ptail的读取操作。更新队列大小 将队列的大小pq-size增加1以反映新添加的元素。 函数代码 //入队列——向队列中插入数据 void QueuePush(Queue pq, QDataType x) {assert(pq);QueueNode* newnode (QueueNode)malloc(sizeof(QueueNode));if (newnode NULL){perror(malloc fail!\n);exit(1);}newnode-data x;newnode-next NULL;//队列为空队头和队尾都是newnodeif (pq-phead NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail pq-ptail-next;}pq-size; } 队列判空 函数名称QueueEmpty 函数目的判断队列是否为空。 函数参数 Queue pq指向需要检查的队列的指针。 函数体详细解析 参数有效性检查 使用assert(pq);语句来确保传入的队列指针pq是有效的。如果pq为NULL则程序会终止并显示错误信息由断言机制提供。这是为了防止程序在尝试访问pq指向的内存时发生崩溃。判断队列是否为空 函数通过检查队列的头部指针pq-phead是否为NULL来判断队列是否为空。如果pq-phead为NULL则表示队列中没有节点因此队列为空。这里需要注意的是由于队列是先进先出的数据结构只要队列的头部指针为NULL就可以确定队列为空无需检查尾部指针pq-ptail。在正常的队列操作中如果队列为空头部和尾部指针都会是NULL。但是只检查头部指针就足以确定队列是否为空因为只要有一个节点存在头部指针就不会是NULL。返回值 函数返回一个布尔值。如果队列为空则返回true或非零值在C语言中通常使用1表示真如果队列不为空则返回false或零值。 函数代码 //队列判空 bool QueueEmpty(Queue* pq) {assert(pq);//队列为空时头为空或头和尾均为空return pq-phead NULL; }队列有效元素个数 函数名称QueueSize 函数目的获取队列中有效元素的个数。 函数参数 Queue* pq指向需要查询的队列的指针。 函数体解析 这个函数非常简单它直接返回队列结构体中存储的元素个数pq-size。这个size字段通常是在队列操作过程中维护的以确保它始终反映队列中当前有效元素的数量。 函数代码 //队列有效元素个数 int QueueSize(Queue* pq) {return pq-size; } 出队列——从队列中删除数据 函数名QueuePop 目的从队列中删除出队最前面的数据元素。 参数 Queue* pq指向需要操作的队列的指针。该队列应该是一个有效的队列即pq不应为NULL且队列不应为空。 函数体详细解析 参数有效性检查 assert(pq);确保传入的队列指针pq是有效的即不是NULL。如果pq为NULL则程序会在这里终止并显示错误信息由断言机制提供。assert(!(QueueEmpty(pq)));确保队列不为空。这是通过调用QueueEmpty函数来实现的该函数应该返回一个布尔值指示队列是否为空。如果队列为空则QueueEmpty(pq)将返回true或非零值而!(QueueEmpty(pq))将返回false或零值这将导致断言失败程序终止。出队操作 QueueNode* temp pq-phead;声明一个QueueNode类型的指针temp并将其初始化为队列的头节点pq-phead。这是为了保存当前头节点的地址以便稍后可以释放其内存。pq-phead pq-phead-next;将队列的头指针pq-phead更新为指向下一个节点。这样原来的头节点就被从队列中移除了。更新尾指针 if (pq-phead NULL)检查更新后的头指针是否为NULL。如果是这意味着队列现在为空因为所有的节点都已经被移除。 pq-ptail NULL;如果队列为空则将尾指针pq-ptail也设置为NULL。这是必要的因为尾指针应该始终指向队列中的最后一个节点或者如果队列为空则应该为NULL。释放内存 free(temp);释放之前保存的头节点temp的内存。这是必要的以避免内存泄漏。更新队列大小 –pq-size;将队列的大小pq-size减1以反映已经移除了一个节点。 取队头数据 函数名QueueFront 目的获取队列前面的即最先进入的数据元素但不从队列中移除它。 参数 Queue* pq指向需要操作的队列的指针。该队列应该是一个有效的队列即pq不应为NULL且队列不应为空。 返回类型QDataType 这是一个假设的数据类型表示队列中存储的数据的类型。在实际代码中QDataType应该被替换为实际的数据类型如int、float、char等或者是一个用户定义的结构体或类的类型。 函数体详细解析 参数有效性检查 assert(pq);确保传入的队列指针pq是有效的即不是NULL。如果pq为NULL则程序会在这里终止并显示错误信息由断言机制提供。assert(!QueueEmpty(pq));确保队列不为空。这是通过调用QueueEmpty函数来实现的该函数应该返回一个布尔值通常是int类型其中0表示false非0表示true指示队列是否为空。如果队列为空则断言失败程序终止。获取队列前面的数据元素 return pq-phead-data;返回队列头节点pq-phead中存储的数据元素。这里假设QueueNode结构体队列节点的类型有一个名为data的成员用于存储数据元素。 函数代码 //取队头数据 QDataType QueueFront(Queue pq) {assert(pq);assert(!QueueEmpty(pq));return pq-phead-data; } 取队尾数据 函数名QueueBack 目的获取队列尾部的即最后进入的数据元素但不从队列中移除它。 参数 Queue* pq指向需要操作的队列的指针。该队列应该是一个有效的队列即pq不应为NULL且队列不应为空。 返回类型QDataType 这是一个占位符数据类型表示队列中存储的数据的类型。在实际代码中QDataType应该被替换为实际的数据类型如int、float、char等或者是一个用户定义的结构体、类的类型或者是某种形式的指针。 函数体详细解析 参数有效性检查 assert(pq);确保传入的队列指针pq是有效的即不是NULL。如果pq为NULL则程序会在这里终止并显示错误信息由断言机制提供。assert(!QueueEmpty(pq));确保队列不为空。这是通过调用QueueEmpty函数来实现的该函数应该返回一个布尔值在C语言中通常是int类型其中0表示false非0表示true指示队列是否为空。如果队列为空则断言失败程序终止。获取队列尾部的数据元素 return pq-ptail-data;返回队列尾节点pq-ptail中存储的数据元素。这里假设QueueNode结构体队列节点的类型有一个名为data的成员用于存储数据元素。 函数代码 //取队尾数据 QDataType QueueBack(Queue pq) {assert(pq);assert(!QueueEmpty(pq));return pq-ptail-data; } 销毁队列 函数名QueueDestroy 目的销毁队列释放其占用的所有内存资源。 参数 Queue* pq指向需要销毁的队列的指针。该队列应该是一个有效的队列即pq不应为NULL。但是此函数将清空队列即使它不是空的。 返回类型void 此函数不返回任何值。 函数体详细解析 参数有效性检查 assert(pq);确保传入的队列指针pq是有效的即不是NULL。如果pq为NULL则程序会在这里终止并显示错误信息由断言机制提供。这是基本的错误检查但在实际应用中即使pq为NULL一个更健壮的实现可能会选择安静地返回而不是断言失败。遍历并释放队列节点 QueueNode* pcur pq-phead;声明一个QueueNode类型的指针pcur并将其初始化为队列的头节点pq-phead。while (pcur)使用一个循环来遍历队列中的所有节点直到pcur变为NULL表示已经到达队列的末尾。 QueueNode* next pcur-next;在释放当前节点之前先保存下一个节点的指针以便在释放当前节点后能够继续遍历。free(pcur);释放当前节点的内存。pcur next;将pcur更新为下一个节点继续循环。重置队列指针和大小 pq-phead pq-ptail NULL;将队列的头指针和尾指针都设置为NULL表示队列现在是空的。pq-size 0;将队列的大小设置为0表示队列中没有元素。 函数代码 //销毁队列 void QueueDestroy(Queue* pq) {assert(pq);QueueNode* pcur pq-phead;while (pcur){QueueNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-ptail NULL;pq-size 0; } 兄弟们共勉    码字不易求个三连 抱拳了兄弟们