前言本篇文章将带你了解队列基本概念、基本操作。这篇文章将带你全部搞懂。队列基本概念队列(queue)是限定在⼀端插⼊另⼀端删除的线性表。因此对队列来说插⼊那⼀端叫做队尾插⼊叫⼊队删除那⼀端叫队头删除叫做出队。队列中的数据元素遵循先进先出(FIFO First InFirst Out)的特性。队列的⼊队出队顺序就简单多了⽆论如何操作⼀种⼊队顺序只对应⼀种出队顺序。队列链式存储这里我采用链式存储队列的链式存储我们可以选⽤单链表结构他们⼊队对应着在表尾插⼊出队对应着在表头删除。队列的基本操作初始化代码如下voidQueueInit(LinkQueue*q)//初始化{assert(q);q-frontq-rear(QNode*)malloc(sizeof(QNode));if(q-frontNULL){printf(申请失败);perror(malloc failed);return;}//申请成功q-front-nextNULL;q-size0;}核心逻辑申请头结点 → 让front和rear都指向它 → 头结点next置空 → 队列长度清零。初始化后队列为空头尾指针重合为后续入队、出队做好准备。销毁代码如下voidQueueDestroy(LinkQueue*q)//销毁{assert(q);QNode*curq-front;while(cur){QNode*nextcur-next;free(cur);curnext;}q-frontq-rearNULL;q-size0;}销毁核心逻辑从front出发用cur逐个遍历链表结点先保存next再free(cur)依次释放所有结点最后把front、rear都置空、长度清零彻底回收队列占用的内存。链式队列入队⼊队就是在表尾插⼊⼀个结点队列设计中我们增加了尾指针所以要实现尾插是很容易的。代码如下voidQueuePush(LinkQueue*q,QDataType x)//入队{assert(q);QNode*newnode(QNode*)malloc(sizeof(QNode));//新节点if(newnodeNULL){printf(申请失败);perror(malloc failed);return;}newnode-datax;newnode-nextNULL;q-rear-nextnewnode;q-rearnewnode;q-size;}核心逻辑申请新结点 → 存入数据 → 尾插到链表尾部 → 更新尾指针rear→ 队列长度加一。借助尾指针入队时间复杂度为 O(1)。出队代码如下voidDeQueue(LinkQueue*q)//出队{assert(q);assert(!QueueEmpty(q));QNode*deq-front-next;//第一个结点printf(队头为%d,de-data);if(de-next){q-front-nextde-next;}else{q-frontq-rearNULL;}free(de);deNULL;q-size--;}核心逻辑出队即删除队头第一个结点。先取front-next作为待删结点de输出其数据若后面还有结点则让front-next跳过de指向下一个结点若删除的是最后一个结点则头尾指针都置空队列回到空状态。最后释放de并让队列长度减一。借助头指针出队时间复杂度为 O(1)。假溢出问题首先我们要先搞清楚为什么会有假溢出问题我们采用顺序存储实现队列队列的存储空间数组中明明还有空闲位置但由于队尾指针rear已经移动到了数组的末尾导致⽆法再插⼊新元素系统错误地判断为“队列已满”的现象这种情况之所以被称为“假”溢出是因为它并⾮真正的空间耗尽⽽是⼀种由于数据结构设计缺陷导致的空间浪费。这么说可能还不太能理解给张图就知道了。我们这里虽然能够给4和5这里插入新元素但是由于我们队头出了两个元素数组还是空的但是rear不能回去也就无法插入新元素所以就造成了假溢出问题。那么如何解决呢我们将这个数组变成一个环形结构就行了。所以就是循环队列。循环队列中新元素⼊队后 rear 指针的更新⽅式为 rear (rear 1) % 数组容量例如给数组下标4添完后41%6 5rear挪到5这个位置◦元素出队后 front 指针的更新⽅式为 front (front 1) % 数组容量。顺序队列的第⼆个问题是他更适合于静态顺序结构不太适合动态顺序结构因为满了扩容时相对复杂也且效率低下。既然这么⿇烦不确定有多少数据时直接使⽤链式队列岂不是更好所以封装实现队列⼀般都⽤链式结构顺序存储适宜于确定最多使⽤多少空间的局限场景。我们在这里可以加一个count用来区分队列是空还是满。或者可以牺牲⼀个空间少存储⼀个数据N个空间只能存储N-1个值这样frontrear就是空逻辑上rear的下⼀个位置是front时就是满。数据结构定义代码如下typedefstruct{int*a;// 指向数组的指针intfront;// 指向对头intrear;// 指向队尾的下⼀个位置intN;// 空间⼤⼩队列⻓度为N-1}MyCircularQueue;初始化代码如下MyCircularQueue*myCircularQueueCreate(intk){MyCircularQueue*obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));// 需要特别注意的是这⾥队列⻓度为k数组我们要开k1个空间obj-a(int*)malloc(sizeof(int)*(k1));obj-rear0;obj-front0;obj-Nk1;returnobj;}核心逻辑申请队列结构体 → 申请k1个空间的数组多开一个用于区分空/满→front、rear都置 0 → 记录容量N k1。初始化后队列为空头尾指针重合。判空和判满代码如下boolmyCircularQueueIsFull(MyCircularQueue*obj){return(obj-rear1)%obj-Nobj-front;}boolmyCircularQueueIsEmpty(MyCircularQueue*obj){returnobj-frontobj-rear;}顺序队列入队代码如下boolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue){if(myCircularQueueIsFull(obj))returnfalse;obj-a[obj-rear]value;obj-rear;obj-rear%obj-N;returntrue;}核心逻辑先判断队列是否已满满了直接返回false否则把数据写入rear指向的位置再让rear后移一位并取模回绕实现环形入队时间复杂度 O(1)。顺序队列出队代码如下boolmyCircularQueueDeQueue(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))returnfalse;obj-front;obj-front%obj-N;returntrue;}核心逻辑先判断队列是否为空空了直接返回false否则让front后移一位并取模回绕逻辑上删除队头元素时间复杂度 O(1)。逐步拆解if(myCircularQueueIsEmpty(obj)) return false先判空队列为空无法出队。obj-front队头指针后移一位跳过当前队头元素。obj-front % obj-N取模回绕让front在数组范围内循环移动实现环形结构。return true出队成功。顺序队列取队头代码如下intmyCircularQueueFront(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))return-1;elsereturnobj-a[obj-front];}核心逻辑先判断队列是否为空空了返回-1否则直接返回front指向位置的元素即队头元素时间复杂度 O(1)。逐步拆解if(myCircularQueueIsEmpty(obj)) return -1先判空队列为空时没有队头可取返回-1表示失败。return obj-a[obj-front]直接通过front下标访问数组返回队头元素的值。取队头不移动front指针只是读取数据不会改变队列状态。结束语那么本篇文章到此结束若有错误或遗漏的地方还请不吝赐教若对你有所帮助还请多多点赞和关注支持一下。