c#队列及其操作
可以用数组、链表实现队列，大致与栈相似，简要介绍下队列实现吧。值得注意的是循环队列判空判满操作，在用链表实现时需要额外思考下出入队列条件。
设计头文件
#ifndef ARRAY_QUEUE_H #define ARRAY_QUEUE_H#include <stdbool.h> #include <stdlib.h> #include <stdio.h> #define QUEUE_CAPACITY 10 typedef int ElementType;typedef struct {// 由于是固长数组队列，所以直接把数组作为结构体对象的一个成员ElementType elements[QUEUE_CAPACITY];int front; // 队头元素的索引int rear; // 队尾元素下一个位置的索引int size; // 队列数组中实际存储元素的个数 } ArrayQueue;// 初始化一个空队列 ArrayQueue *queue_create(); // 销毁一个队列 void queue_destroy(ArrayQueue *q); // 判满 bool is_full(ArrayQueue *q); // 判空 bool is_empty(ArrayQueue *q); // 入队 bool enqueue(ArrayQueue *q, ElementType element); // 出队 ElementType dequeue(ArrayQueue *q); // 访问队首元素 ElementType peek(ArrayQueue *q);#endif // !ARRAY_QUEUE_H
实现创建和销毁队列
// 初始化一个空队列 ArrayQueue *queue_create() {return calloc(1, sizeof(ArrayQueue)); } // 销毁一个队列 void queue_destroy(ArrayQueue *q) {free(q); }
实现判空和判满
// 判满 bool is_full(ArrayQueue *q) {return q->size == QUEUE_CAPACITY; } // 判空 bool is_empty(ArrayQueue *q) {return q->size == 0; }
实现入队操作
// 入队 bool enqueue(ArrayQueue *q, ElementType element) {// 1.判满if (is_full(q)) {printf("error: queue is full.\n");return false;}// 2.队列没满时才入队q->elements[q->rear] = element;// 3.更新rear索引q->rear = (q->rear + 1) % QUEUE_CAPACITY;// 4.更新sizeq->size++;return true; // 入队成功 }
实现出队操作
/* * 出队就是将front索引的元素返回，然后将front索引后移 * 注意：不需要对front位置的元素做任何修改 * 因为front和rear之间的元素才是队列元素，其它位置即便有值也不算队列元素 * 其他位置的垃圾值，会随着队列出入队操作逐渐被覆盖 */ ElementType dequeue(ArrayQueue *q) {// 1.判空if (is_empty(q)) {printf("error: queue is empty.\n");exit(1);}// 2.队列非空，记录队首元素以用于返回ElementType ret = q->elements[q->front];// 3.更新front索引q->front = (q->front + 1) % QUEUE_CAPACITY;// 4.不要忘记更新sizeq->size--;return ret; }
实现访问队首元素
// 访问队首元素 ElementType peek(ArrayQueue *q) {// 1.判断队列是否是空的if (is_empty(q)) {printf("error: queue is empty.\n");exit(1);}// 2.队列非空返回队首元素return q->elements[q->front]; }
扩展: 链式队列
#ifndef LIST_QUEUE_H #define LIST_QUEUE_H#include <stdbool.h> #include <stdio.h> #include <stdlib.h>// 定义队列中的元素类型 typedef int ElementType;// 队列节点的结构 typedef struct node_s {ElementType data;struct node_s *next; } QueueNode;// 队列的结构 typedef struct {QueueNode *front; // 队头结点指针QueueNode *rear; // 队尾结点指针 } LinkedListQueue;// 函数声明 // 创建链式队列 LinkedListQueue *create_queue(); // 销毁链式队列 void destroy_queue(LinkedListQueue *q); // 入队列 bool enqueue(LinkedListQueue *q, ElementType element); // 出队列并返回队头元素 ElementType dequeue(LinkedListQueue *q); // 访问队头元素 ElementType peek_queue(LinkedListQueue *q); // 判空 bool is_empty(LinkedListQueue *q);#endif // !LIST_QUEUE_H链式队列实现-参考代码
#include "list_queue.h"// 函数声明 LinkedListQueue *create_queue() {return calloc(1, sizeof(LinkedListQueue)); }void destroy_queue(LinkedListQueue *q) {// 从队头开始遍历链表，销毁每一个结点QueueNode *current = q->front;while (current != NULL) {QueueNode *temp = current->next;free(current);current = temp;}// 销毁队列结构体free(q); }bool is_empty(LinkedListQueue *q) {// 队头指针是空指针，即表示空队列return q->front == NULL; }// 入队操作: 只能在队尾插入一个结点 // 由于已存在尾指针，所以这里的操作就是链表尾插 bool enqueue(LinkedListQueue *q, ElementType element) {QueueNode *new_node = malloc(sizeof(QueueNode));if (new_node == NULL) {printf("Error: malloc failed in enqueue.\n");return false;}// 初始化新结点new_node->data = element;new_node->next = NULL;// 开始进行尾插法插入一个结点// 分两种情况：如果尾插插入的是第一个结点需要同步更新头指针，否则仅需要更新尾指针if (q->front == NULL) {// 插入的是第一个结点q->front = new_node;q->rear = new_node;}else {// 插入的不是第一个结点q->rear->next = new_node;q->rear = new_node;}return true; }// 出队，在队头删除一个结点。也就是在删除链表的第一个结点 ElementType dequeue(LinkedListQueue *q) {if (is_empty(q)) {printf("Error: queue is empty.\n");exit(1);}QueueNode *tmp = q->front;// 将出队的结点数据保存ElementType remove_data = tmp->data;// 更新队头指针q->front = tmp->next;if (q->front == NULL) {// 如果队头更新后,队列为空,说明出队的就是最后一个元素// 于是同步更新队尾指针q->rear = NULL;}free(tmp);return remove_data; }// 访问队头元素但不出队 ElementType peek_queue(LinkedListQueue *q) {if (is_empty(q)) {printf("Error: queue is empty.\n");exit(1);}return q->front->data; }
扩展: 动态数组队列
既然可以实现固定长度的队列，那么基于动态数组，就可以实现一个动态数组队列
#ifndef DYNAMIC_QUEUE_H #define DYNAMIC_QUEUE_H#include <stdbool.h> #include <stdlib.h> #include <stdio.h>typedef int ElementType; // 该队列当前存储int元素 #define DEFAULT_CAPACITY 10 // 数组队列的初始长度是10 #define THRESHOLD 1000 // 超过阈值每次扩容1.5倍扩，否则2倍的扩// 定义队列结构体 typedef struct {ElementType *data; // 动态数组存储队列元素int front; // 标记队头元素的索引int rear; // 标记队尾元素下一个位置的索引int size; // 当前队列中元素数量int capacity; // 队列容量 } DynamicQueue;// 队列基本操作函数声明 // 创建动态数组队列 DynamicQueue *create_queue(); // 销毁动态数组队列 void destroy_queue(DynamicQueue *q); // 判空 bool is_empty(DynamicQueue *q); // 判满 bool is_full(DynamicQueue *q); // 入队列 bool enqueue(DynamicQueue *q, ElementType data); // 出队列并且返回队头元素 ElementType dequeue(DynamicQueue *q);#endif // DYNAMIC_QUEUE_H参考代码
#include "dynamic_queue.h"// 创建并初始化队列 DynamicQueue *create_queue() {DynamicQueue *q = calloc(1, sizeof(DynamicQueue));if (q == NULL) {printf("error: calloc failed in create_queue.\n");return NULL;}// front、rear、size自动初始化0值，无需再手动初始化了q->data = calloc(DEFAULT_CAPACITY, sizeof(ElementType)); // 使用calloc避免随机值if (q->data == NULL) {printf("error: calloc failed in create_queue.\n");free(q);return NULL;}q->capacity = DEFAULT_CAPACITY;return q; }// 销毁队列 void destroy_queue(DynamicQueue *q) {free(q->data);free(q); }// 检查队列是否为空 bool is_empty(DynamicQueue *q) {return q->size == 0; }// 检查队列是否已满 bool is_full(DynamicQueue *q) {return q->size == q->capacity; }/*这里采用一种简单粗暴的扩容手段:直接分配新容量的内存块然后遍历旧内存块中的队列元素,将这些元素全部从头开始复制到新内存块中这样的操作在完成后,需要更新front索引和rear索引 */ static bool resize_queue(DynamicQueue *q) {int old_capacity = q->capacity;int new_capacity = (old_capacity < THRESHOLD) ?(old_capacity << 1) :(old_capacity + (old_capacity >> 1));// 重新分配一个新的,更长的动态数组ElementType *new_data = malloc(new_capacity * sizeof(ElementType));if (new_data == NULL) {printf("error: realloc failed in resize_queue.\n");return false;}int curr = q->front; // curr索引用于遍历整个队列中的元素int index = 0;while (index < q->size) {new_data[index] = q->data[curr];curr = (curr + 1) % q->capacity;index++;} // while循环结束时,new_data就从头开始包含了队列的所有元素 free(q->data);q->data = new_data;q->front = 0;q->rear = q->size;q->capacity = new_capacity;return true; }// 入队操作 bool enqueue(DynamicQueue *q, ElementType data) {if (is_full(q)) {if (!resize_queue(q)) {printf("error: 扩容失败.\n");return false; // 队列扩容失败,入队也同步失败}}q->data[q->rear] = data;q->rear = (q->rear + 1) % q->capacity; // 循环队列q->size++;return true; }// 出队操作 ElementType dequeue(DynamicQueue *q) {if (is_empty(q)) {printf("error: 队列为空，无法出队。\n");exit(1);}ElementType item = q->data[q->front];q->front = (q->front + 1) % q->capacity; // 循环队列q->size--;return item; }
队列的应用场景
- 操作系统的任务调度，进程/线程按照到达顺序来排队等待CPU执行权。
- 各种数据处理系统中的缓冲区/缓存机制。比如stdin/stdout缓冲区，先输入缓冲区的数据，总是先从缓冲区输出。
- 打印机的任务管理，当多个打印任务同时到达时，它们在队列中排队，按照提交的顺序进行打印。
- 后端应用系统中的消息队列。
- 广度优先搜索(比如二叉搜索树的层次遍历)