C语言 队列的实现全解析

什么是队列

队列是一种常见的数据结构，它采用先进先出的方式来管理数据。当我们需要按照时间顺序依次处理一系列任务时，队列便成了一个非常有用的工具。

队列的实现

在C语言中，队列可以通过数组或者链表来实现。当使用数组实现队列时，我们需要定义一个固定大小的数组和两个指针——队头指针head和队尾指针tail。定义如下：

#define QUEUE_SIZE 100

typedef struct {
    int data[QUEUE_SIZE];
    int head, tail;
} Queue;

其中，head指向队列的第一个元素，tail指向队尾元素的下一个位置。初始化队列时，将head和tail均初始化为0即可：

Queue q;
q.head = q.tail = 0; // 初始化队列

队列的操作

接下来我们需要实现队列的四个基本操作——入队、出队、查看队首元素和查看队列大小。

入队

入队操作用来将新的元素添加到队列末尾。如果队列已满，入队操作将无法执行。

int enqueue(Queue *q, int element) {
    if ((q->tail + 1) % QUEUE_SIZE == q->head) {
        return 0; // 队列已满，无法入队
    }
    q->data[q->tail] = element;
    q->tail = (q->tail + 1) % QUEUE_SIZE;
    return 1; // 入队成功
}

如果队列已满，tail指针将指向队列的头部，所以我们使用(q->tail + 1) % QUEUE_SIZE来计算新的tail的位置。

出队

出队操作用来将队列中的第一个元素移除并返回它的值。如果队列为空，出队操作将无法执行。

int dequeue(Queue *q) {
    if (q->head == q->tail) {
        return -1; // 队列为空，无法出队
    }
    int res = q->data[q->head];
    q->head = (q->head + 1) % QUEUE_SIZE;
    return res;
}

查看队首元素

查看队首元素操作用来返回队列中的第一个元素，但不会将其移除。如果队列为空，查看队首元素的操作将返回-1。

int peek(Queue *q) {
    if (q->head == q->tail) {
        return -1; // 队列为空，无队首元素
    }
    return q->data[q->head];
}

查看队列大小

查看队列大小操作用来返回队列中元素的个数。

int size(Queue *q) {
    return (q->tail - q->head + QUEUE_SIZE) % QUEUE_SIZE;
}

示例说明

下面给出两个队列的示例操作。

示例一

假设我们要实现一个循环队列，当队列满时，新来的元素将覆盖队列中原有的元素。

#include <stdio.h>

int main() {
    Queue q;
    q.head = q.tail = 0; // 初始化队列
    int n = 5; // 队列的大小为5
    int i;
    for (i = 0; i < n + 1; i++) {
        enqueue(&q, i);
        printf("enqueue %d\n", i);
    }
    printf("队列的元素个数为 %d\n", size(&q)); // 队列的元素个数为 5
    for (i = 0; i < n; i++) {
        int x = dequeue(&q);
        printf("dequeue %d\n", x);
    }
    printf("队列的元素个数为 %d\n", size(&q)); // 队列的元素个数为 0
    return 0;
}

输出：

enqueue 0
enqueue 1
enqueue 2
enqueue 3
enqueue 4
队列已满，无法入队
队列的元素个数为 5
dequeue 0
dequeue 1
dequeue 2
dequeue 3
dequeue 4
队列的元素个数为 0

示例二

假设我们要通过队列实现一个简单的计算器，读入一系列整数和加减号，并按照之前整数的顺序依次进行加减运算，最后输出结果。

#include <stdio.h>

int main() {
    Queue q;
    q.head = q.tail = 0; // 初始化队列
    int n, res = 0, sign = 1; // sign表示当前数字的符号
    char ch;
    scanf("%d", &n);
    enqueue(&q, n); // 将第一个数字入队
    while ((ch = getchar()) != '\n') { 
        if (ch >= '0' && ch <= '9') {
            n = n * 10 + ch - '0';
        } else {
            res += sign * dequeue(&q); // 将队首元素弹出并加到res中
            enqueue(&q, sign * n); // 将新的数字入队
            sign = (ch == '+') ? 1 : -1; // 根据运算符更新符号
            n = 0; // 清除n，准备读入下一个数字
        }
    }
    res += sign * dequeue(&q); // 将队首元素弹出并加到res中
    printf("计算结果为 %d\n", res);
    return 0;
}

假设输入如下：

10 + 1 - 4 + 3

输出：

计算结果为 10

总结

在本文中，我们通过C语言的数组实现和结构体定义，讲解了队列的操作和实现方式，同时提供了两个队列的例子。作为一种常见的数据结构，队列在程序设计中有着广泛的应用，如线程池、事件处理等，自行练习写队列程序有助于更好地掌握C语言的数据结构和算法。