文章目录引入队列解决的是“按到达顺序服务”一、链队列的结构节点串起来两个指针守住两端二、根据功能使用C语言实现1. 初始化三个成员先指向“空状态”2. 入队首节点和普通节点是两种情况3. 出队真正关键的是只剩一个节点4. 获取队头队尾元素5. 查看元素数量与销毁链表三、运行测试四、复杂度与内存代价五、扩展练习1. 手动追踪队列的两端六、完整参考代码Queue.hQueue.ctest.c引入队列解决的是“按到达顺序服务”在实际排队买票场景中先到的人通常先办理打印机收到多个任务时也常按提交顺序处理。若后来的人可以随意插队系统就很难预测也不公平。队列queue把这种规则抽象成一种线性数据结构先进入的元素先离开即 FIFOFirst In, First Out先进先出。队列有两个操作端元素从队尾rear加入从队头front删除。注意“加入”和“删除”发生在不同位置这正是它与栈的关键区别。队列的常见操作包括QueuePush在队尾入队。QueuePop从队头出队。QueueFront查看队头元素不删除。QueueBack查看队尾元素不删除。QueueSize获取有效元素个数。QueueEmpty判断队列是否为空。队列也只是一个抽象接口可以用数组实现也可以用链表实现。本篇采用的是带头尾指针的链队列实现。一、链队列的结构节点串起来两个指针守住两端本篇同样采用三个文件Queue.h、Queue.c、test.c来实现链队列。Queue.h链队列节点定义以及功能函数声明。Queue.c链队列各功能函数具体实现。test.c测试功能有效性。定义链队列节点与结构typedefintQDataType;//定义队列节点,链式结构typedefstructQueueNode{QDataType data;structQueueNode*next;}QNode;//队列结构队头队尾typedefstructQueue{QNode*front;//队头指针QNode*rear;//队尾指针intsize;//元素数量}Queue;当队列保存10、20、30时逻辑结构是front rear │ │ ▼ ▼ [10 | next] ──▶ [20 | next] ──▶ [30 | NULL] size 3front指向第一个要被服务的节点rear指向最后一个刚进入的节点。因为两端地址都保存着所以队尾追加不需要从头遍历整条链表队头删除也能直接定位。链队列实现时须保证以下规则空队列时front NULL、rear NULL、size 0。非空队列时front和rear都不为空rear-next NULL。只有一个节点时front rear这个节点的next仍为NULL。二、根据功能使用C语言实现1. 初始化三个成员先指向“空状态”使用QueueInit()函数初始化队列但不在初始化时申请节点//初始化队列voidQueueInit(Queue*q){assert(q);q-frontNULL;q-rearNULL;q-size0;}链队列的空间随入队动态申请因此空队列本身只需要两个个指针和一个计数器。2. 入队首节点和普通节点是两种情况新节点先写入数据并把next设为NULL因为它会成为新的队尾//队尾入队列voidQueuePush(Queue*q,QDataType x){assert(q);//申请节点QNode*newNode(QNode*)malloc(sizeof(QNode));if(newNodeNULL){perror(QueuePush()::malloc() fail);return;}newNode-datax;newNode-nextNULL;//判断当前队列是否有节点if(q-rearNULL){q-rearq-frontnewNode;}else{q-rear-nextnewNode;q-rearnewNode;}q-size;}第一次入队时队头和队尾必须同时指向新节点之后才是“旧队尾连到新节点再移动rear”的普通流程。若忘记处理第一次入队front仍为空后续QueueFront就无法工作。3. 出队真正关键的是只剩一个节点普通出队只需保存下一个节点、释放旧队头、移动front//队头出队列voidQueuePop(Queue*q){assert(q);if(QueueEmpty(q)){printf(当前队列为空无法出队列\n);return;}else{//处理只有单个节点的情况if(q-front-nextNULL){free(q-front);q-frontq-rearNULL;}//处理多个节点else{QNode*nextq-front-next;free(q-front);q-frontnext;}}q-size--;}//检测队列是否为空boolQueueEmpty(Queue*q){assert(q);if(q-frontNULL)returntrue;elsereturnfalse;}最后一个节点出队后front变成NULL此时必须让rear也变成NULL否则rear会成为悬空指针它指向已经释放的内存下一次入队或取队尾都可能出错。4. 获取队头队尾元素在获取队头队尾元素值时仅读队头队尾指针的指向不执行任何删除插入与改变指向的操作//获取队列头部元素QDataTypeQueueFront(Queue*q){assert(q);if(QueueEmpty(q)){printf(当前队列为空无法获取\n);return;}else{returnq-front-data;}}//获取队列队尾元素QDataTypeQueueBack(Queue*q){assert(q);if(QueueEmpty(q)){printf(当前队列为空无法获取\n);return;}else{returnq-rear-data;}}5. 查看元素数量与销毁链表由于我们在设计队列结构时为其设置了记录元素数量的变量size所以函数QueueSize()可直接返回队列结构中size的值//获取队列有效元素个数intQueueSize(Queue*q){assert(q);returnq-size;}//销毁队列voidQueueDestroy(Queue*q){assert(q);QNode*curq-front;while(cur){QNode*nextcur-next;free(cur);curnext;}q-frontq-rearNULL;q-size0;}销毁函数则从队头开始逐个释放先保存next再释放当前节点最后把队头、队尾和数量恢复为空状态。这种“先记住下一跳再释放当前节点”的顺序与链表中的一样不能颠倒。三、运行测试在test.c文件中编写测试代码初始化队列后入队1 2 3 4然后依次取出队头元素并打印同时统计当前的元素个数再出队尾最后销毁voidtest(){Queue q;QueueInit(q);QueuePush(q,1);QueuePush(q,2);QueuePush(q,3);QueuePush(q,4);while(!QueueEmpty(q)){printf(队头元素%d ,QueueFront(q));printf(元素数量%d \n,QueueSize(q));QueuePop(q);}QueueDestroy(q);}运行结果四、复杂度与内存代价操作复杂度原因QueuePushO(1)直接在rear后连接新节点QueuePopO(1)直接移动front并释放旧节点QueueFront、QueueBackO(1)直接读取两端指针QueueSize、QueueEmptyO(1)读取计数器或指针QueueDestroyO(n)必须访问并释放每个节点链队列不会像固定数组那样因为“容量满”而整体搬迁元素数量可以按需增长代价是每个节点多了一个next指针还要承担多次malloc/free的管理成本。若任务数量已知且频繁访问连续数组可能有更好的缓存局部性若数量变化大且需要两端O(1)操作链队列则更加灵活。五、扩展练习1. 手动追踪队列的两端操作序列为Push(7)、Push(9)、Pop()、Push(4)、Pop()、Pop()。写出每一步的队头、队尾和size。思路入队只改变rear出队只改变front删除前要先记住当前队头。参考答案Push(7)队头 7队尾 7size1。Push(9)队头 7队尾 9size2。Pop()队头 9队尾 9size1。push(4)队头 9队尾 4size2。两次Pop()后为空frontNULL、rearNULL、size0。六、完整参考代码Queue.h#pragmaonce#includestdio.h#includestdlib.h#includestdbool.h#includeassert.htypedefintQDataType;//定义队列节点,链式结构typedefstructQueueNode{QDataType data;structQueueNode*next;}QNode;//队列结构队头队尾typedefstructQueue{QNode*front;//队头指针QNode*rear;//队尾指针intsize;//元素数量}Queue;//初始化队列voidQueueInit(Queue*q);//队尾入队列voidQueuePush(Queue*q,QDataType x);//队头出队列voidQueuePop(Queue*q);//获取队列头部元素QDataTypeQueueFront(Queue*q);//获取队列队尾元素QDataTypeQueueBack(Queue*q);//获取队列有效元素个数intQueueSize(Queue*q);//检测队列是否为空boolQueueEmpty(Queue*q);//销毁队列voidQueueDestroy(Queue*q);Queue.c#includeQueue.h//初始化队列voidQueueInit(Queue*q){assert(q);q-frontNULL;q-rearNULL;q-size0;}//队尾入队列voidQueuePush(Queue*q,QDataType x){assert(q);QNode*newNode(QNode*)malloc(sizeof(QNode));if(newNodeNULL){perror(QueuePush()::malloc() fail);return;}newNode-datax;newNode-nextNULL;if(q-rearNULL){q-rearq-frontnewNode;}else{q-rear-nextnewNode;q-rearnewNode;}q-size;}//队头出队列voidQueuePop(Queue*q){assert(q);if(QueueEmpty(q)){printf(当前队列为空无法出队列\n);return;}else{//处理只有单个节点的情况if(q-front-nextNULL){free(q-front);q-frontq-rearNULL;}//处理多个节点else{QNode*nextq-front-next;free(q-front);q-frontnext;}}q-size--;}//获取队列头部元素QDataTypeQueueFront(Queue*q){assert(q);if(QueusEmpty(q)){printf(当前队列为空无法获取\n);return;}else{returnq-front-data;}}//获取队列队尾元素QDataTypeQueueBack(Queue*q){assert(q);if(QueueEmpty(q)){printf(当前队列为空无法获取\n);return;}else{returnq-rear-data;}}//获取队列有效元素个数intQueueSize(Queue*q){assert(q);returnq-size;}//检测队列是否为空boolQueueEmpty(Queue*q){assert(q);if(q-frontNULL)returntrue;elsereturnfalse;}//销毁队列voidQueueDestroy(Queue*q){assert(q);QNode*curq-front;while(cur){QNode*nextcur-next;free(cur);curnext;}q-frontq-rearNULL;q-size0;}test.c#includeQueue.hvoidtest(){Queue q;QueueInit(q);QueuePush(q,1);QueuePush(q,2);QueuePush(q,3);QueuePush(q,4);while(!QueueEmpty(q)){printf(队头元素%d ,QueueFront(q));printf(元素数量%d \n,QueueSize(q));QueuePop(q);}QueueDestroy(q);}intmain(){test();return0;}