队列

队列是先进先出的数据结构，只能在队尾插入元素、队头删除元素，先进入的数据会优先被取出。

January 1, 1968数据结构1分钟阅读

如果说栈是“后进先出（LIFO）”，那么 队列（Queue） 的规则完全相反，它是：先进先出（FIFO, First In, First Out）。

生活中的典型例子就是排队：

先来排队的人，先办理业务离开；
后来的人只能站在队尾等待。

队列就像一条双向开口的管道，两端分工明确：

队头（Front / Head）： 允许进行删除（出队）的一端。
队尾（Rear / Tail）： 允许进行插入（入队）的一端。

操作	英文	说明
入队	`Enqueue` / `Push`	将新元素添加至队尾。
出队	`Dequeue` / `Pop`	将队头元素移除并返回。
查看队头	`Peek` / `Front`	获取队头元素的值，但不出队。
判空	`IsEmpty`	检查队列中是否有元素。

队列入队与出队操作图解 — 队列的基本操作，从队头执行出队删除元素，向队尾执行入队添加元素，遵循先进先出

在实际应用中，普通队列存在“假溢出”问题（即数组前面有空位，但队尾已满）。为了解决这个问题或适应不同场景，演化出了几种变体：

把数组的首尾相连形成一个环。这是顺序结构实现队列最常用的方式，极大地提高了空间利用率。

两端（队头和队尾）都可以自由地进行入队和出队操作。

元素的出队顺序不再取决于入队时间，而是由元素的优先级决定（通常基于“堆”这种数据结构实现）。

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 5

typedef struct {
    int data[MAX_SIZE];
    int front; // 指向队头
    int rear;  // 指向队尾的下一个位置
} Queue;

void init(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

// 入队 (Enqueue)
bool enqueue(Queue *q, int val) {
    if ((q->rear + 1) % MAX_SIZE == q->front) return false; // 队满
    q->data[q->rear] = val;
    q->rear = (q->rear + 1) % MAX_SIZE; // 取模实现循环
    return true;
}

// 出队 (Dequeue)
bool dequeue(Queue *q, int *val) {
    if (q->front == q->rear) return false; // 队空
    *val = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE; // 取模实现循环
    return true;
}

int main() {
    Queue q;
    init(&q);

    enqueue(&q, 100);
    enqueue(&q, 200);

    int val;
    dequeue(&q, &val); // val = 100 (先入先出)
    printf("出队元素: %d\n", val);

    return 0;
}

任何需要按顺序排队处理资源的场景，底层都离不开队列：

操作系统任务调度： CPU 在处理多线程或进程时，会按先后顺序将任务放入就绪队列。
网络数据包缓冲： 路由器收到数据包后，放入队列中依次转发。
消息队列（Message Queue）： 如 RabbitMQ、Kafka，用于分布式系统中异步解耦和流量削峰。
广度优先搜索算法（BFS）： 在图或树的遍历中，利用队列记录下一层需要访问的节点。