C语言数据结构之队列算法详解

什么是队列？

在计算机科学中，队列是一种抽象数据类型或线性数据结构。它具有先进先出（FIFO）的特性，即先进入队列的元素先被处理或先被移除。队列通常用于解决先到先服务的问题（如请求处理），但也常用于广泛的异步编程中。

队列的特点

队列通常具有以下特点：

• 队列可以为空；
• 队列从队首插入元素，从队尾移除元素；
• 队列只允许从队尾插入元素，从队首移除元素；
• 只有队尾和队首可以访问（获取或移除）队列的元素；
• 队列具有线性结构，且一次只能将一个元素插入或移除。

队列的操作

对于队列，常见的操作有：

• enQueue：插入一个元素到队列的队尾
• deQueue：移除队列中的队首元素
• peek：返回队列中的队首元素
• isEmpty：判断队列是否为空
• isFull：判断队列是否已满
• size：返回队列元素的个数

队列算法详解

1. 数组实现的队列

数组实现的队列是最简单、最基础的队列实现方法。队列通过数组的方式存储，使用两个指针head和tail分别指向队首和队尾。

C语言数组实现的队列示例代码：

#define MAX_SIZE 10

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

void init(Queue *q) {
    q->head = q->tail = 0;
}

int isEmpty(Queue *q) {
    return q->head == q->tail;
}

int isFull(Queue *q) {
    return (q->tail + 1) % MAX_SIZE == q->head;
}

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

void enQueue(Queue *q, int e) {
    if (isFull(q)) {
        printf("Queue is Full\n");
        return;
    }
    q->data[q->tail] = e;
    q->tail = (q->tail + 1) % MAX_SIZE;
}

int deQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is Empty\n");
        exit(-1);
    }
    int e = q->data[q->head];
    q->head = (q->head + 1) % MAX_SIZE;
    return e;
}

int peek(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is Empty\n");
        exit(-1);
    }
    return q->data[q->head];
}

int main(int argc, char const *argv[]) {
    Queue q;
    init(&q);
    enQueue(&q, 1);
    enQueue(&q, 2);
    enQueue(&q, 3);
    while(!isEmpty(&q)) {
        printf("%d ", deQueue(&q));
    }
    return 0;
}

2. 链表实现的队列

链表实现的队列是一种比较灵活的实现方式，相对于数组实现，它的插入和删除时间复杂度更低。而且不会浪费空间（因为不需要预留空间，只需要在需要的时候申请空间即可）。

C语言链表实现的队列示例代码：

typedef struct _node {
    int val;
    struct _node *next;
} Node;

typedef struct {
    Node *head;
    Node *tail;
    int size;
} Queue;

void init(Queue *q) {
    q->head = q->tail = NULL;
    q->size = 0;
}

int isEmpty(Queue *q) {
    return q->head == NULL;
}

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

void enQueue(Queue *q, int e) {
    Node *n = (Node *) malloc(sizeof(Node));
    n->val = e;
    n->next = NULL;
    if (q->size == 0) {
        q->head = q->tail = n;
    } else {
        q->tail->next = n;
        q->tail = n;
    }
    q->size++;
}

int deQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is Empty\n");
        exit(-1);
    }
    Node *n = q->head;
    int e = n->val;
    q->head = q->head->next;
    free(n);
    q->size--;
    return e;
}

int peek(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is Empty\n");
        exit(-1);
    }
    return q->head->val;
}

int main(int argc, char const *argv[]) {
    Queue q;
    init(&q);
    enQueue(&q, 1);
    enQueue(&q, 2);
    enQueue(&q, 3);
    while(!isEmpty(&q)) {
        printf("%d ", deQueue(&q));
    }
    return 0;
}

总结

队列是一种常见的数据结构，它具有先进先出的特点。队列有多种实现方法，包括数组实现、链表实现等。不同的实现方法有着不同的优点和缺点，我们可以根据实际情况进行选择。