数据结构 | 队列：从概念到实战

个人主页-爱因斯晨

文章专栏-数据结构

继续加油！

一、队列的基本概念

队列是一种先进先出（FIFO，First In First Out） 的线性数据结构，仅允许在一端进行插入操作（队尾），另一端进行删除操作（队头）。

生活中的队列场景：

• 银行窗口排队办理业务

• 打印机任务队列

• 消息队列中的消息传递

二、队列的核心操作

1. 初始化（InitQueue）：创建一个空队列

2. 入队（EnQueue）：在队尾插入元素

3. 出队（DeQueue）：从队头删除元素

4. 获取队头元素（GetFront）：返回队头元素值

5. 判空（IsEmpty）：判断队列是否为空

6. 销毁（DestroyQueue）：释放队列占用的内存

三、C 语言实现队列

3.1 顺序队列（数组实现）

顺序队列使用数组存储元素，通过队头指针（front）和队尾指针（rear）标记队列边界。

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100  // 队列最大容量

// 顺序队列结构体
typedef struct {
    int data[MAX_SIZE];
    int front;  // 队头指针（指向队头元素）
    int rear;   // 队尾指针（指向队尾元素的下一个位置）
} SeqQueue;

// 初始化队列
void InitQueue(SeqQueue *q) {
    q->front = 0;
    q->rear = 0;
}

// 判空
int IsEmpty(SeqQueue *q) {
    return q->front == q->rear;
}

// 判满
int IsFull(SeqQueue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;  // 预留一个空间区分空满
}

// 入队
int EnQueue(SeqQueue *q, int value) {
    if (IsFull(q)) {
        printf("队列已满，无法入队\n");
        return 0;  // 入队失败
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;  // 循环移动队尾指针
    return 1;  // 入队成功
}

// 出队
int DeQueue(SeqQueue *q, int *value) {
    if (IsEmpty(q)) {
        printf("队列为空，无法出队\n");
        return 0;  // 出队失败
    }
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;  // 循环移动队头指针
    return 1;  // 出队成功
}

// 获取队头元素
int GetFront(SeqQueue *q, int *value) {
    if (IsEmpty(q)) {
        printf("队列为空，无队头元素\n");
        return 0;
    }
    *value = q->data[q->front];
    return 1;
}

// 测试顺序队列
int main() {
    SeqQueue q;
    InitQueue(&q);
    
    // 入队操作
    EnQueue(&q, 10);
    EnQueue(&q, 20);
    EnQueue(&q, 30);
    
    // 获取队头元素
    int frontVal;
    GetFront(&q, &frontVal);
    printf("队头元素：%d\n", frontVal);  // 输出：10
    
    // 出队操作
    int deVal;
    DeQueue(&q, &deVal);
    printf("出队元素：%d\n", deVal);  // 输出：10
    
    // 再次获取队头
    GetFront(&q, &frontVal);
    printf("新队头元素：%d\n", frontVal);  // 输出：20
    
    return 0;
}

顺序队列特点：

• 优点：实现简单，访问速度快

• 缺点：容量固定，存在 “假溢出” 问题（需用循环队列优化）

3.2 链式队列（链表实现）

链式队列使用链表存储元素，队头指针指向头节点，队尾指针指向尾节点。

#include <stdio.h>
#include <stdlib.h>

// 节点结构体
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 链式队列结构体
typedef struct {
    Node *front;  // 队头指针（指向头节点）
    Node *rear;   // 队尾指针（指向尾节点）
} LinkQueue;

// 初始化队列
void InitQueue(LinkQueue *q) {
    // 创建头节点（不存储数据）
    Node *head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    q->front = head;
    q->rear = head;
}

// 判空
int IsEmpty(LinkQueue *q) {
    return q->front == q->rear;
}

// 入队
void EnQueue(LinkQueue *q, int value) {
    // 创建新节点
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    
    // 插入到队尾
    q->rear->next = newNode;
    q->rear = newNode;  // 更新队尾指针
}

// 出队
int DeQueue(LinkQueue *q, int *value) {
    if (IsEmpty(q)) {
        printf("队列为空，无法出队\n");
        return 0;
    }
    
    Node *temp = q->front->next;  // 待删除节点
    *value = temp->data;
    q->front->next = temp->next;
    
    // 如果删除的是最后一个节点，需更新队尾指针
    if (q->rear == temp) {
        q->rear = q->front;
    }
    
    free(temp);  // 释放节点内存
    return 1;
}

// 获取队头元素
int GetFront(LinkQueue *q, int *value) {
    if (IsEmpty(q)) {
        printf("队列为空，无队头元素\n");
        return 0;
    }
    *value = q->front->next->data;
    return 1;
}

// 销毁队列
void DestroyQueue(LinkQueue *q) {
    // 释放所有节点
    while (q->front != NULL) {
        q->rear = q->front->next;
        free(q->front);
        q->front = q->rear;
    }
}

// 测试链式队列
int main() {
    LinkQueue q;
    InitQueue(&q);
    
    // 入队
    EnQueue(&q, 100);
    EnQueue(&q, 200);
    EnQueue(&q, 300);
    
    // 获取队头
    int frontVal;
    GetFront(&q, &frontVal);
    printf("队头元素：%d\n", frontVal);  // 输出：100
    
    // 出队
    int deVal;
    DeQueue(&q, &deVal);
    printf("出队元素：%d\n", deVal);  // 输出：100
    
    // 销毁队列
    DestroyQueue(&q);
    return 0;
}

链式队列特点：

• 优点：容量动态扩展，不存在溢出问题

• 缺点：需要额外空间存储指针，操作稍复杂

四、队列的应用场景

1. 广度优先搜索（BFS）：在二叉树层次遍历、图的遍历中常用

2. 缓冲处理：如键盘输入缓冲、网络数据接收缓冲

3. 任务调度：操作系统中的进程调度、线程池任务调度

4. 消息传递：分布式系统中的消息队列（如 RabbitMQ）

五、两种实现的对比选择