一、队列基础概念1. 队列的定义与特性队列Queue是一种操作受限的线性表遵循FIFOFirst‑In‑First‑Out先进先出原则。它只允许在表的一端队尾进行插入操作在另一端队头进行删除操作。核心操作入队Enqueue在队尾添加新元素。出队Dequeue从队头移除元素。2. 队列的基本术语队头Front允许删除元素的一端即最早进入队列的元素所在位置。队尾Rear允许插入元素的一端即最新进入队列的元素所在位置。队列长度Length队列中当前元素的个数。空队列Empty Queue队列长度为 0 的状态。3. 队列的常见应用场景任务调度与缓存操作系统进程调度、打印任务队列。数据缓冲I/O 缓冲区、消息队列如 RabbitMQ、Kafka 等。算法应用广度优先搜索BFS遍历树或图。并发控制多线程环境下的任务队列、请求排队。网络通信数据包发送与接收的缓冲区。4. 队列的两种主要实现方式顺序队列数组实现使用连续内存空间存储元素。普通顺序队列的缺陷存在“假溢出”现象队尾指针到达数组末尾但队头前面仍有空闲空间。改进方案循环队列Circular Queue通过取模运算实现逻辑上的环形结构充分利用存储空间。链式队列链表实现使用单链表或双向链表存储元素每个节点包含数据域和指向下一个节点的指针。优点动态分配内存不存在假溢出问题插入和删除操作时间复杂度为 O(1)。缺点每个节点需要额外存储指针空间开销略大访问任意位置元素需要遍历。5. 队列的基本操作API创建队列create_queue初始化队列结构。入队enqueue将元素添加到队尾。出队dequeue移除并返回队头元素。获取队头元素get_front/peek查看队头元素但不移除。判空is_empty检查队列是否为空。获取队列长度get_length返回当前队列中元素的数量。遍历traverse/show按顺序输出队列中的所有元素。销毁队列destroy_queue释放队列占用的所有内存。6. 循环队列的关键点判空条件队头指针 front 队尾指针 rear。判满条件通常采用两种策略牺牲一个存储单元(rear 1) % MAXSIZE front。增加一个 size 字段记录当前元素个数size MAXSIZE 即为满。入队操作rear (rear 1) % MAXSIZE。出队操作front (front 1) % MAXSIZE。7. 链式队列的实现要点通常使用带头节点的单链表维护头指针front和尾指针rear。入队时将新节点链接到 rear 之后并更新 rear 指向新节点。出队时删除 front 指向的节点并更新 front 指向下一个节点。当队列为空时front 和 rear 均指向头节点或均为 NULL。当队列中只有一个元素时front 和 rear 指向同一个节点。8. 队列的时间复杂度分析操作顺序队列循环队列链式队列入队enqueueO(1)O(1)出队dequeueO(1)O(1)获取队头peekO(1)O(1)判空is_emptyO(1)O(1)遍历traverseO(n)O(n)9. 队列的变体与扩展双端队列Deque允许在两端进行插入和删除操作。优先队列Priority Queue元素按优先级出队通常用堆Heap实现。阻塞队列Blocking Queue当队列为空时获取操作会被阻塞当队列满时插入操作会被阻塞。并发队列线程安全的队列实现如 Java 中的 ConcurrentLinkedQueue。二、链式队列1. 创建、判空、销毁Queue_t *create_queue(void) { Queue_t *pq malloc(sizeof(Queue_t)); if(NULL pq) { printf(malloc error\n); return NULL; } pq-phead NULL; pq-ptail NULL; pq-clen 0; return pq; } int queue_is_empty(Queue_t *pq) { return NULL pq-phead; } void destroy_queue(Queue_t *pq) { if(NULL pq) return; while(!queue_is_empty(pq)) { dequeue(pq); } free(pq); }2. 入队队尾插入int enqueue(Queue_t *pq, int data) { if(NULL pq) return -1; QNode_t *pnew malloc(sizeof(QNode_t)); if(NULL pnew) { printf(malloc error\n); return -1; } pnew-data data; pnew-pnext NULL; if(queue_is_empty(pq)) { pq-phead pnew; pq-ptail pnew; } else { pq-ptail-pnext pnew; pq-ptail pnew; } pq-clen; return 0; }3. 出队队头删除int dequeue(Queue_t *pq) { if(NULL pq || queue_is_empty(pq)) { printf(队列空无法出队\n); return -1; } QNode_t *pdel pq-phead; pq-phead pq-phead-pnext; free(pdel); pq-clen--; //注意删完变空队列ptail置NULL避免野指针 if(queue_is_empty(pq)) { pq-ptail NULL; } return 0; }4. 获取队头元素int get_front(Queue_t *pq,int *val) { if(NULL pq || queue_is_empty(pq)) return -1; *val pq-phead-data; return 0; }5. 遍历打印void show_queue(Queue_t *pq) { if(queue_is_empty(pq)) { printf(队列为空\n); return; } QNode_t *p pq-phead; printf(队列元素); while(p ! NULL) { printf(%d ,p-data); p p-pnext; } printf(\n); }三、循环队列1. 创建、判满、判空、销毁SQue_t *create_seq_queue(void) { SQue_t *psq malloc(sizeof(SQue_t)); if (NULL psq) { printf(malloc error\n); return NULL; } //开辟存储数据的数组空间 psq-pbase malloc(SEQ_MAX_LEN * sizeof(Data_t)); if (NULL psq-pbase) { printf(malloc error\n); free(psq); //分配数组失败要释放已经申请的SQue_t防止内存泄漏 return NULL; } psq-head 0; psq-tail 0; return psq; } //队列是否满 int is_full_seq_queue(SQue_t *psq) { return (psq-tail 1) % SEQ_MAX_LEN psq-head; } //队列是否空 int is_empty_seq_queue(SQue_t *psq) { return psq-head psq-tail; } void destroy_seq_queue(SQue_t *psq) { if (psq NULL) return; free(psq-pbase); //先释放数组 free(psq); //再释放管理结构体 }2. 入队、出队、获取队头//入队队尾添加元素 int push_seq_queue(SQue_t *psq, Data_t data) { if (is_full_seq_queue(psq)) { printf(队列已满无法入队\n); return -1; } psq-pbase[psq-tail] data; psq-tail (psq-tail 1) % SEQ_MAX_LEN; return 0; } //出队队头删除元素pdata接收出队的数据可以传NULL不接收 int pop_seq_queue(SQue_t *psq, Data_t *pdata) { if (is_empty_seq_queue(psq)) { printf(队列为空无法出队\n); return -1; } if (pdata ! NULL) { *pdata psq-pbase[psq-head]; } psq-head (psq-head 1) % SEQ_MAX_LEN; return 0; } //获取队头元素不删除 int get_seq_queue_head(SQue_t *psq, Data_t *pdata) { if (is_empty_seq_queue(psq)) { return -1; } if (pdata ! NULL) { *pdata psq-pbase[psq-head]; return 0; } return -1; }3. 遍历打印void show_seq_queue(SQue_t *psq) { if(is_empty_seq_queue(psq)) { printf(队列为空\n); return; } int i; for (i psq-head; i ! psq-tail; i (i 1) % SEQ_MAX_LEN) { printf(%d , psq-pbase[i].num); } printf(\n); }