C语言数据结构与算法之队列的实现详解

1. 什么是队列

队列（Queue）是一种数据结构，它是一种具有特殊操作约束的线性结构。在队列中，数据元素按照一定的逻辑顺序（即先进先出）存储，允许在队列尾部插入元素，在队列头部删除元素。队列的基本操作如下：

• 队尾入队：将一个新元素插入到队列的尾部；
• 队头出队：将队列中头部的元素删除，并返回该元素；
• 获取队头元素：仅返回队列头部元素的值，不改变队列本身；
• 获取队列元素个数；
• 清空队列。

2. 队列的实现

2.1 队列的数据结构

队列可以使用数组或链表来实现。使用数组时，需要记录队列头和尾的下标，同时要解决数组存满时的“循环队列”问题；使用链表时，则要记录链表头和尾的指针。

2.2 队列的基本操作实现

队列的结构定义

使用链表实现队列时，可以定义如下的队列结构体：

typedef struct _QueueNode {
    int data;
    struct _QueueNode* next;
} QueueNode;

typedef struct _Queue {
    int size;
    QueueNode* front;
    QueueNode* rear;
} Queue;

其中，front 和 rear 分别指向队列头和队列尾，size 表示队列中的元素数量。

实现队尾入队操作

对于入队操作，我们需要新建一个节点，并将其插入到队列末尾。实现如下：

bool EnQueue(Queue* queue, int data) {
    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    if (!node) {
        return false;  // 内存分配失败
    }
    node->data = data;
    node->next = NULL;

    if (queue->rear) {
        queue->rear->next = node;
    }
    queue->rear = node;

    if (!queue->front) {
        queue->front = node;
    }

    queue->size++;
    return true;
}

实现队头出队操作

队头出队操作需要删除链表的第一个节点，并返回该节点的值。实现如下：

int DeQueue(Queue* queue) {
    if (queue->size == 0) {
        return -1;  // 队列为空，返回一个非法结果
    }

    QueueNode* node = queue->front;
    int data = node->data;

    queue->front = node->next;
    queue->size--;

    if (queue->size == 0) {
        queue->rear = NULL;
    }

    free(node);
    return data;
}

实现获取队头元素和获取队列元素个数操作

这两个操作比较简单，分别实现如下：

int Front(Queue* queue) {
    if (queue->size == 0) {
        return -1;  // 队列为空，返回一个非法结果
    }

    return queue->front->data;
}

int Size(Queue* queue) {
    return queue->size;
}

实现清空队列操作

清空队列可以通过循环出队全部操作来实现，如下：

void ClearQueue(Queue* queue) {
    while (queue->size > 0) {
        DeQueue(queue);
    }
}

2.3 队列的示例应用

入队示例

在下面的示例代码中，我们定义了一个 Queue 类型的指针 q，并将其初始化为空队列。然后将元素 10、20 和 30 依次入队（即将它们插入到队列的尾部），最后返回队列元素个数。

int queue_example() {
    Queue queue;
    InitQueue(&queue);

    EnQueue(&queue, 10);
    EnQueue(&queue, 20);
    EnQueue(&queue, 30);

    return Size(&queue);
}

出队示例

在下面的示例代码中，我们定义了一个 Queue 类型的指针 q，并将其初始化为空队列。然后将元素 10、20 和 30 依次入队，接着将队列中头部的一个元素出队并打印出来，最后返回队列元素个数。

int queue_example() {
    Queue queue;
    InitQueue(&queue);

    EnQueue(&queue, 10);
    EnQueue(&queue, 20);
    EnQueue(&queue, 30);

    int data = DeQueue(&queue);
    printf("DeQueue data: %d\n", data);

    return Size(&queue);
}

3. 总结

队列是一种非常实用的数据结构，它可以用来实现很多算法和数据处理任务。实现队列的过程中，我们需要充分理解队列的概念、特点和操作，选择合适的数据结构，实现基本的操作，并且要具备一定的代码优化能力。在实际编程中，我们可以根据具体需求进行封装和拓展，让队列功能更加完备和可靠。