队列：先进先出的艺术

队列这东西，说白了就是现实生活中的排队。你去银行办业务，先来的人先办，后来的人后办。计算机里的队列也是这个道理——先进先出（FIFO）。

我刚开始学数据结构时，总觉得队列太简单了，不就是个排队吗？直到后来做嵌入式项目，才发现队列在资源受限的系统里有多重要。嗯，咱们今天就把队列彻底讲透。

队列的定义与抽象数据类型

队列是一种操作受限的线性表。它只允许在一端插入（队尾），在另一端删除（队首）。

你想想看，这和栈正好相反。栈是后进先出，队列是先进先出。这两个结构在实际开发中配合使用，能解决很多复杂问题。

队列的抽象数据类型（ADT）包含以下核心操作：

操作	描述
InitQueue(&Q)	初始化队列，构造一个空队列
DestroyQueue(&Q)	销毁队列，释放内存
EnQueue(&Q, e)	入队，将元素e插入队尾
DeQueue(&Q, &e)	出队，删除队首元素并用e返回
QueueEmpty(Q)	判断队列是否为空
QueueLength(Q)	返回队列中元素个数
GetHead(Q, &e)	读取队首元素，不删除

顺序队列（循环队列）的实现

顺序队列用数组实现。但有个坑——如果直接用数组，出队后前面的空间就浪费了。这就是所谓的"假溢出"问题。

怎么解决？循环队列。把数组首尾相连，形成一个环。

循环队列的关键在于判断队空和队满。这里有个经典做法：

• 队空条件：front == rear
• 队满条件：(rear + 1) % MAXSIZE == front
• 入队：rear = (rear + 1) % MAXSIZE
• 出队：front = (front + 1) % MAXSIZE

为什么要牺牲一个存储单元？因为如果不这样，队空和队满的条件就一样了，你没法区分。

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int front;  // 队首指针
    int rear;   // 队尾指针
} SqQueue;

// 初始化
void InitQueue(SqQueue *Q) {
    Q->front = Q->rear = 0;
}

// 入队
int EnQueue(SqQueue *Q, int e) {
    if ((Q->rear + 1) % MAXSIZE == Q->front) {
        return 0;  // 队满
    }
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return 1;
}

// 出队
int DeQueue(SqQueue *Q, int *e) {
    if (Q->front == Q->rear) {
        return 0;  // 队空
    }
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return 1;
}

链式队列的实现

链式队列用链表实现。它没有假溢出的问题，内存按需分配。

链式队列需要两个指针：front指向队首，rear指向队尾。入队操作在rear后面加节点，出队操作删除front指向的节点。

typedef struct QNode {
    int data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front;  // 队首指针
    QueuePtr rear;   // 队尾指针
} LinkQueue;

// 初始化
void InitQueue(LinkQueue *Q) {
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    Q->front->next = NULL;
}

// 入队
void EnQueue(LinkQueue *Q, int e) {
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
}

// 出队
int DeQueue(LinkQueue *Q, int *e) {
    if (Q->front == Q->rear) {
        return 0;  // 队空
    }
    QueuePtr p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p) {
        Q->rear = Q->front;  // 最后一个节点出队
    }
    free(p);
    return 1;
}

队列的应用：广度优先搜索（BFS）

广度优先搜索是队列最经典的应用之一。它的核心思想是：从起点出发，先访问所有距离为1的节点，再访问距离为2的节点，以此类推。

你想想看，这不就是排队吗？先来的先处理，处理完再把它的邻居加入队列。

BFS的伪代码：

void BFS(Graph G, int start) {
    Queue Q;
    InitQueue(&Q);
    visited[start] = 1;
    EnQueue(&Q, start);
    
    while (!QueueEmpty(Q)) {
        DeQueue(&Q, &v);
        // 访问节点v
        for (每个邻接点w) {
            if (!visited[w]) {
                visited[w] = 1;
                EnQueue(&Q, w);
            }
        }
    }
}

BFS的应用场景很多：

• 图的遍历
• 最短路径问题（无权图）
• 网络爬虫的广度优先抓取
• 社交网络的好友推荐

我个人习惯用BFS处理层级相关的问题。比如文件系统遍历，先遍历当前目录，再遍历子目录，这就是典型的BFS思路。

队列这个结构，看似简单，但用好了能解决很多实际问题。我建议你动手实现一遍循环队列和链式队列，然后写个BFS程序跑一跑。代码写多了，自然就理解了。