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;
}

队列的应用场景

1. 操作系统的任务调度，进程/线程按照到达顺序来排队等待CPU执行权。
2. 各种数据处理系统中的缓冲区/缓存机制。比如stdin/stdout缓冲区，先输入缓冲区的数据，总是先从缓冲区输出。
3. 打印机的任务管理，当多个打印任务同时到达时，它们在队列中排队，按照提交的顺序进行打印。
4. 后端应用系统中的消息队列。
5. 广度优先搜索(比如二叉搜索树的层次遍历)