数据结构之队列

队列 (Queue)

1. 概述

队列（Queue）是一种特殊的线性表，只允许在表的一端进行插入操作，而在表的另一端进行删除操作。插入操作称为入队（enqueue），删除操作称为出队（dequeue）。队列遵循先进先出（First In First Out, FIFO）的原则。

2. 队列的定义

队列是一种线性表，只允许在一端进行插入操作，在另一端进行删除操作。插入的一端称为队尾（Rear），删除的一端称为队头（Front）。

3. 队列的基本操作

队列的基本操作包括初始化队列、判断队列空、判断队列满、入队、出队和取队头元素。

3.1 顺序队列

顺序队列是用一组地址连续的存储单元依次存放从队头到队尾的队列元素。

定义顺序队列结构

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int front;
    int rear;
} SeqQueue;

初始化队列

void InitQueue(SeqQueue *Q) {
    Q->front = 0;
    Q->rear = 0;
}

判断队列空

bool QueueEmpty(SeqQueue Q) {
    return Q.front == Q.rear;
}

判断队列满

bool QueueFull(SeqQueue Q) {
    return (Q.rear + 1) % MAXSIZE == Q.front;
}

入队

bool Enqueue(SeqQueue *Q, int e) {
    if (QueueFull(*Q)) return false;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return true;
}

出队

bool Dequeue(SeqQueue *Q, int *e) {
    if (QueueEmpty(*Q)) return false;
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return true;
}

取队头元素

bool GetFront(SeqQueue Q, int *e) {
    if (QueueEmpty(Q)) return false;
    *e = Q.data[Q.front];
    return true;
}

3.2 链队列

链队列是用链表来存储队列中的元素。

定义链队列节点结构

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));
    if (!Q->front) exit(1);
    Q->front->next = NULL;
}

判断队列空

bool QueueEmpty(LinkQueue Q) {
    return Q.front == Q.rear;
}

入队

bool Enqueue(LinkQueue *Q, int e) {
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if (!p) return false;
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return true;
}

出队

bool Dequeue(LinkQueue *Q, int *e) {
    if (QueueEmpty(*Q)) return false;
    QueuePtr p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p) Q->rear = Q->front;
    free(p);
    return true;
}

取队头元素

bool GetFront(LinkQueue Q, int *e) {
    if (QueueEmpty(Q)) return false;
    *e = Q.front->next->data;
    return true;
}

4. 队列的应用

队列在计算机科学中有广泛的应用，例如：

操作系统中的任务调度：使用队列实现任务的先进先出调度。
网络数据缓冲：在网络通信中，使用队列保存接收到的数据包。
树和图的广度优先搜索：在树和图的遍历中使用队列实现广度优先搜索。
打印队列：管理打印任务的顺序。

5. 示例代码

下面是使用队列实现广度优先搜索（BFS）的示例代码：

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

#define MAXVEX 100

typedef struct {
    int data[MAXVEX];
    int front;
    int rear;
} SeqQueue;

void InitQueue(SeqQueue *Q) {
    Q->front = 0;
    Q->rear = 0;
}

bool QueueEmpty(SeqQueue Q) {
    return Q.front == Q.rear;
}

bool Enqueue(SeqQueue *Q, int e) {
    if ((Q->rear + 1) % MAXVEX == Q->front) return false;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXVEX;
    return true;
}

bool Dequeue(SeqQueue *Q, int *e) {
    if (QueueEmpty(*Q)) return false;
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXVEX;
    return true;
}

void BFS(int graph[MAXVEX][MAXVEX], int n, int start) {
    bool visited[MAXVEX] = {false};
    SeqQueue Q;
    InitQueue(&Q);
    printf("%d ", start);
    visited[start] = true;
    Enqueue(&Q, start);
    while (!QueueEmpty(Q)) {
        int v;
        Dequeue(&Q, &v);
        for (int i = 0; i < n; i++) {
            if (graph[v][i] == 1 && !visited[i]) {
                printf("%d ", i);
                visited[i] = true;
                Enqueue(&Q, i);
            }
        }
    }
}

int main() {
    int graph[MAXVEX][MAXVEX] = {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 0, 1, 1, 0},
        {1, 0, 0, 0, 1, 0},
        {0, 1, 0, 0, 0, 1},
        {0, 1, 1, 0, 0, 1},
        {0, 0, 0, 1, 1, 0}
    };
    int n = 6;
    BFS(graph, n, 0);
    return 0;
}

上述代码实现了使用顺序队列进行广度优先搜索（BFS）的功能。通过队列保存待访问的节点，依次访问每个节点，并将其未访问的邻接节点加入队列，从而实现广度优先搜索。