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.更新size
    q->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.不要忘记更新size
    q->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. 广度优先搜索(比如二叉搜索树的层次遍历)