企业官网建设流程全解析

企业网站建设报告,宣传片拍摄制作报价单,重庆承越网站建设公,给企业做网站如何定价文章目录 1. 队列的基本概念1.1 概念1.2 队列相关概念1.3 队列的基本操作 2. 队列的顺序存储结构2.1 顺序队列2.2 循环队列2.3 顺序队列的基本操作代码2.3.1 初始化2.3.2 队列空2.3.3 队列满2.3.4 入队2.3.5 出队2.3.6 读队头2.3.7 获取队列元素个数 3. 队列的链式存储结构3.1 …文章目录1. 队列的基本概念1.1 概念1.2 队列相关概念1.3 队列的基本操作2. 队列的顺序存储结构2.1 顺序队列2.2 循环队列2.3 顺序队列的基本操作代码2.3.1 初始化2.3.2 队列空2.3.3 队列满2.3.4 入队2.3.5 出队2.3.6 读队头2.3.7 获取队列元素个数3. 队列的链式存储结构3.1 链式队列结构3.2 链式队列基本操作代码实现3.2.1 初始化3.2.2 队列空3.2.3 入队3.2.4 出队3.2.5 读队头3.2.6 销毁队列1. 队列的基本概念1.1 概念队列是一种特殊的线性表只允许在一端进行插入数据操作在另一端进行删除数据操作的一种数据结构。队列具有先进先出(First In First Out简称FIFO) 的原则。队列Queue是一种特殊的线性数据结构其操作遵循先进先出First In, First Out, FIFO的原则。即元素的插入只能在队列的一端进行而删除操作则在另一端执行。这种单向进出的特性使得最早进入队列的元素能够最先被移除广泛应用于任务调度、缓冲处理、广度优先搜索等场景。1.2 队列相关概念队尾进行插入操作的一端称为队尾队尾指向的是最后一个元素队头进行删除操作的一端称为队头队头指向的是第一个元素入队将一个元素添加到队尾的操作称为入队出队从队头取出一个元素的操作称为出队队尾Rear进行插入操作的一端新元素从队尾加入。队尾指针通常指向当前最后一个有效元素的位置。队头Front进行删除操作的一端元素从此处移出。队头指针指向当前最前端的元素。入队Enqueue将一个新元素添加到队尾的操作。出队Dequeue从队头移除一个元素的操作。1.3 队列的基本操作队列的核心操作通常包括入队出队获取队头元素判断队列是否为空队列的物理实现主要有两种方式基于数组顺序存储和基于链表链式存储。其中基于数组的实现又可进一步分为顺序队列和循环队列。2. 队列的顺序存储结构使用数组实现队列称为顺序存储结构。为高效管理队列状态需定义两个指针front指向队头元素的位置rear指向下一个可插入位置即队尾后一位本文统一采用 front 和 rear 表示队头与队尾指针特殊说明除外。2.1 顺序队列顺序队列使用一组地址连续的存储单元数组依次存放从队头到队尾的元素。同时设置队头指针front和队尾指针rear。其结构定义示例如下#defineMAX_SIZE100//设置队列最大存储元素个数typedefstruct{//定义元素结构}ElementType// 定义队列结构体typedefstruct{ElementType data[MAX_SIZE];intfront;intrear;}ArrayQueue;请注意我们在此使用“元素”而非“数据”来指代队列的组成单元是因为队列中的单元可以是基本数据类型、数组、结构体等任何有效数据类型。如上图所示在顺序队列中入队时rear指针向后移动front指针不变。出队时front指针向后移动rear指针不变。基础的入队和出队操作代码如下// 入队intenqueueArray(ArrayQueue*q,ElementType e){if(q-rearMAX_SIZE){printf(队列已满\n);return-1;// 失败}q-data[q-rear]e;return0;// 成功}// 出队intdequeueArray(ArrayQueue*q,ElementType*e){if(q-frontq-rear){printf(队列为空\n);return-1;}*eq-data[q-front];return0;}上述代码逻辑简单直接。但考虑一种情况如果队列在执行若干次出队操作后front指针前移此时即使数组尾部仍有空间新元素入队时也可能因rear指针到达数组末尾而被误判为队列已满。此时q-rear MAX_SIZE满足队列已满的判断条件但是队列还有4个元素空间可存储这种情况被称为“假溢出”。到这里你可能会有这样的疑问出队时为什么队头要往后移动而不是一直指向数组下标为0的位置若强制 front 始终为 0则每次出队后需将后续所有元素前移一位造成频繁的数据迁移时间复杂度为 O(n)严重影响性能。因此采用移动 front 指针的方式避免实时迁移仅在必要时整体前移数据。对于顺序队列我们可以采用如下方法如果我们出队时队头往后移动一位这样我们就避免每次出队都进行数据迁移我们只需要在只有在rear等于数组大小且front不等于0时进行一次数据迁移将已经出队留下的空间继续供入队时使用。尽管该方法减少了迁移频率但仍无法彻底消除性能仍受限。为此引入更优的解决方案——循环队列2.2 循环队列循环队列是对顺序队列的改进通过将数组逻辑上首尾相连形成一个环形结构从而解决“假溢出”问题。当 rear 到达数组末尾时自动回到下标 0实现空间的循环利用。同理front 也可循环移动。先来看看循环队列的入队、出队操作如果使用循环队列的方式当队列为空以及队列满的时候front和rear指针都是出于重叠的状态即frontrear这就会出现歧义了这会让我们分辨不清当front和rear重叠的时候队列是空的还是队满状态。循环队列避免了“假溢出”的问题又如何解决循环队列“队空”和“队满”判断的问题有三种方式区分“队空”和“队满”结构体中增加一个计数器用以记录队列中元素数量优点逻辑清晰判断高效缺点多占用一个整型空间// 定义队列结构体typedefstruct{ElementType data[MAX_SIZE];intfront;intrear;intcnt;// 元素个数}CircularQueue;牺牲一个存储单元常用方法牺牲一个队列单元来区分队空和队满入队时少用一个队列单元这是种较为普遍的做法约定以“队头指针在队尾指针的下一位置作为队满的标志”约定队列最多存放MAX_SIZE-1个元素保留一个空位用于区分空满状态。队空条件front rear队满条件(rear 1) % MAX_SIZE front优点无需额外变量实现简洁广泛用于标准库和竞赛编程缺点牺牲一个存储单元设置状态标志flag引入一个标志位标识上一次操作是入队还是出队辅助判断当前状态。优点节省空间适合内存敏感场景缺点逻辑较复杂易出错维护成本高// 定义队列结构体typedefstruct{ElementType data[MAX_SIZE];intfront;intrear;intflag;}CircularQueue;这种方式和第1种类似只是第1种方法是定量判断flag判断是定性判断逻辑上不如记录数量的方法简单且容易理解。2.3 顺序队列的基本操作代码以循环队列为例牺牲一个存储单元的方案2.3.1 初始化voidinitQueue(CircularQueue*q){q-front0;q-rear0;}2.3.2 队列空boolisEmpty(CircularQueue*q){returnq-frontq-rear;}2.3.3 队列满boolisFull(CircularQueue*q){return(q-rear1)%MAX_SIZEq-front;}2.3.4 入队boolenqueue(CircularQueue*q,intvalue){if(isFull(q)){printf(队列已满无法入队\n);returnfalse;}q-data[q-rear]value;q-rear(q-rear1)%MAX_SIZE;returntrue;}2.3.5 出队booldequeue(CircularQueue*q,int*value){if(isEmpty(q)){printf(队列为空无法出队\n);returnfalse;}*valueq-data[q-front];q-front(q-front1)%MAX_SIZE;returntrue;}2.3.6 读队头boolgetFront(CircularQueue*q,int*value){if(isEmpty(q)){printf(队列为空\n);returnfalse;}*valueq-data[q-front];returntrue;}2.3.7 获取队列元素个数intgetSize(CircularQueue*q){return(q-rear-q-frontMAX_SIZE)%MAX_SIZE;}3. 队列的链式存储结构3.1 链式队列结构链式队列基于单链表实现由一系列节点构成每个节点包含数据域和指向下一节点的指针。队列维护两个外部指针队头指针front指向链表的第一个节点队尾指针rear指向链表的最后一个节点操作流程入队在 rear 后创建新节点并更新 rear 指针出队删除 front 所指节点释放内存并将 front 移至下一个节点优点动态分配内存无需预设容量无“假溢出”问题空间利用率高插入删除效率高O(1)缺点每个节点需额外存储指针空间开销大内存分配/释放带来一定时间开销存在内存碎片风险频繁申请释放链式队列入队出队头节点3.2 链式队列基本操作代码实现3.2.1 初始化节点与队列结构定义// 链式队列节点定义typedefstructQueueNode{intdata;structQueueNode*next;}QueueNode;// 链式队列结构定义typedefstruct{QueueNode*front;QueueNode*rear;}LinkedQueue;// 初始化队列voidinitLinkedQueue(LinkedQueue*q){q-frontNULL;q-rearNULL;}3.2.2 队列空// 判断队列是否为空boolisLinkedQueueEmpty(LinkedQueue*q){returnq-frontNULL;}3.2.3 入队boolenqueueLinked(LinkedQueue*q,intvalue){QueueNode*newNode(QueueNode*)malloc(sizeof(QueueNode));if(newNodeNULL){printf(内存分配失败\n);returnfalse;}newNode-datavalue;newNode-nextNULL;if(isLinkedQueueEmpty(q)){// 队列为空时front和rear都指向新节点q-frontnewNode;q-rearnewNode;}else{// 队列不为空时将新节点添加到rear后面q-rear-nextnewNode;q-rearnewNode;}returntrue;}3.2.4 出队// 出队操作booldequeueLinked(LinkedQueue*q,int*value){if(isLinkedQueueEmpty(q)){printf(队列为空无法出队\n);returnfalse;}QueueNode*tempq-front;*valuetemp-data;q-frontq-front-next;// 如果出队后队列为空需要更新rear指针if(q-frontNULL){q-rearNULL;}free(temp);returntrue;}3.2.5 读队头boolgetFrontLinked(LinkedQueue*q,int*value){if(isLinkedQueueEmpty(q)){printf(队列为空\n);returnfalse;}*valueq-front-data;returntrue;}3.2.6 销毁队列// 销毁队列voiddestroyLinkedQueue(LinkedQueue*q){intvalue;while(!isLinkedQueueEmpty(q)){dequeueLinked(q,value);}}