队列（Queue）的C语言实现

文章目录队列Queue的C语言实现 什么是队列 队列的基本操作 C语言实现队列 ️1. 基于数组的队列实现2. 基于链表的队列实现队列的应用场景 性能分析 ⚡总结 队列Queue的C语言实现 队列是一种常见的数据结构广泛应用于计算机科学和编程中。它遵循先进先出First In, First OutFIFO的原则就像现实生活中的排队一样先来的人先接受服务。本文将详细介绍队列的基本概念、操作及其在C语言中的实现方式并提供代码示例、图表和外部资源链接帮助您深入理解。什么是队列 队列是一种线性数据结构包含两个主要操作入队Enqueue在队列的尾部添加元素。出队Dequeue从队列的头部移除元素。这种结构非常适合处理需要按顺序处理数据的场景例如任务调度、消息传递或广度优先搜索算法。下面是一个简单的mermaid图表展示了队列的基本操作流程StartEnqueue OperationAdd Element to RearEnd EnqueueDequeue OperationRemove Element from FrontEnd DequeueContinue Processing队列的基本操作 队列通常支持以下核心操作enqueue添加元素到队尾。dequeue移除队头元素。peek/front查看队头元素而不移除它。isEmpty检查队列是否为空。isFull检查队列是否已满对于固定大小的队列。这些操作确保了队列的FIFO行为使其在各种应用中非常有用。C语言实现队列 ️在C语言中队列可以通过数组或链表来实现。下面我将展示两种常见的实现方式使用数组的静态队列和使用链表的动态队列。1. 基于数组的队列实现基于数组的队列使用一个固定大小的数组来存储元素并维护两个指针front和rear分别指向队列的头部和尾部。#includestdio.h#includestdlib.h#includestdbool.h#defineMAX_SIZE100// 定义队列的最大容量typedefstruct{intitems[MAX_SIZE];intfront;intrear;}Queue;// 初始化队列voidinitQueue(Queue*q){q-front-1;q-rear-1;}// 检查队列是否为空boolisEmpty(Queue*q){returnq-front-1;}// 检查队列是否已满boolisFull(Queue*q){return(q-rear1)%MAX_SIZEq-front;}// 入队操作voidenqueue(Queue*q,intvalue){if(isFull(q)){printf(Queue is full! Cannot enqueue %d\n,value);return;}if(isEmpty(q)){q-front0;}q-rear(q-rear1)%MAX_SIZE;q-items[q-rear]value;printf(Enqueued: %d\n,value);}// 出队操作intdequeue(Queue*q){if(isEmpty(q)){printf(Queue is empty! Cannot dequeue.\n);return-1;}intvalueq-items[q-front];if(q-frontq-rear){q-front-1;q-rear-1;}else{q-front(q-front1)%MAX_SIZE;}printf(Dequeued: %d\n,value);returnvalue;}// 查看队头元素intpeek(Queue*q){if(isEmpty(q)){printf(Queue is empty!\n);return-1;}returnq-items[q-front];}intmain(){Queue q;initQueue(q);enqueue(q,10);enqueue(q,20);enqueue(q,30);printf(Front element: %d\n,peek(q));dequeue(q);printf(Front element after dequeue: %d\n,peek(q));return0;}这个实现使用了循环数组来高效利用空间。当rear到达数组末尾时它会绕回到开头只要前面有空位。2. 基于链表的队列实现基于链表的队列动态分配内存因此没有固定大小的限制除了系统内存限制。每个节点包含数据和指向下一个节点的指针。#includestdio.h#includestdlib.h#includestdbool.htypedefstructNode{intdata;structNode*next;}Node;typedefstruct{Node*front;Node*rear;}Queue;// 初始化队列voidinitQueue(Queue*q){q-frontNULL;q-rearNULL;}// 检查队列是否为空boolisEmpty(Queue*q){returnq-frontNULL;}// 入队操作voidenqueue(Queue*q,intvalue){Node*newNode(Node*)malloc(sizeof(Node));if(!newNode){printf(Memory allocation failed! Cannot enqueue %d\n,value);return;}newNode-datavalue;newNode-nextNULL;if(isEmpty(q)){q-frontnewNode;q-rearnewNode;}else{q-rear-nextnewNode;q-rearnewNode;}printf(Enqueued: %d\n,value);}// 出队操作intdequeue(Queue*q){if(isEmpty(q)){printf(Queue is empty! Cannot dequeue.\n);return-1;}Node*tempq-front;intvaluetemp-data;q-frontq-front-next;if(q-frontNULL){q-rearNULL;}free(temp);printf(Dequeued: %d\n,value);returnvalue;}// 查看队头元素intpeek(Queue*q){if(isEmpty(q)){printf(Queue is empty!\n);return-1;}returnq-front-data;}// 释放队列内存voidfreeQueue(Queue*q){while(!isEmpty(q)){dequeue(q);}}intmain(){Queue q;initQueue(q);enqueue(q,10);enqueue(q,20);enqueue(q,30);printf(Front element: %d\n,peek(q));dequeue(q);printf(Front element after dequeue: %d\n,peek(q));freeQueue(q);// 避免内存泄漏return0;}链表实现更加灵活但需要管理动态内存注意避免内存泄漏。队列的应用场景 队列在计算机科学中无处不在。以下是一些常见应用操作系统处理进程调度和I/O请求。网络通信管理数据包传输顺序。广度优先搜索BFS用于图和树的遍历。打印队列管理多个打印任务的顺序。例如在BFS算法中队列用于存储待访问的节点确保按层次遍历。您可以在GeeksforGeeks的BFS介绍中了解更多细节。性能分析 ⚡队列操作的复杂度通常为入队和出队O(1) 时间如果实现正确。空间复杂度O(n)其中n是队列中的元素数量。基于数组的实现可能在某些情况下浪费空间如果队列大小固定而链表实现更灵活但可能有额外的内存开销。总结 队列是一种简单但强大的数据结构通过FIFO原则管理数据。在C语言中您可以使用数组或链表来实现它每种方式各有优缺点。掌握队列有助于解决许多编程问题特别是在需要顺序处理的场景中。如果您想深入阅读数据结构的更多内容可以参考Cprogramming.com的数据结构教程或Programiz的队列指南这些资源提供了额外的示例和解释。希望这篇博客帮助您理解了队列的C语言实现继续编码享受学习过程