C语言数据结构系列队列篇

C语言数据结构系列队列篇攻略

简介

队列（Queue）是一种先进先出（First In First Out, FIFO）的线性数据结构，类似于排队买票的过程。本篇攻略将带您从以下三个方面深入浅出地了解C语言数据结构系列队列篇：

• 队列的特点；
• 队列的实现；
• 队列的应用。

队列的特点

队列有两个特殊的端点，队头（front）和队尾（rear）。队头指示队列的头部元素，队尾指示队列的尾部元素。当元素进入队列时，其被添加到队列的末尾处；当元素离开队列时，其从队列的前端删除。下面是队列的几个特点：

• 插入（Insert）操作在队尾进行；
• 删除（Delete）操作在队头进行；
• 队列只允许在一端进行插入操作，在另一端进行删除操作；
• 队列先进先出，即先插入队列的元素先删除；
• 具有一定的局限性，一般只能从队列头或尾访问元素。

队列的实现

顺序队列

Queue是一种先进先出（FIFO）的数据结构。最简单的实现队列的方式是使用顺序结构，如数组。数组的优点是简单易实现，缺点是当队列元素进行删除操作后，其余元素位置会向前移一位并占用原来的位置，这会造成空间的浪费。下面是顺序队列的示意代码：

#define MAXQUEUE 10 // 队列的最大元素个数
typedef struct{
    int data[MAXQUEUE];
    int rear,front;
    int size; // 队列中实际元素个数
}Queue;

void initQueue(Queue *q){
    q->rear = -1;
    q->front = -1;
    q->size = 0;
}

// 判断队列是否为空
bool isEmpty(Queue *q){
    return (q->size == 0);
}

// 判断队列是否已满
bool isFull(Queue *q){
    return (q->size == MAXQUEUE);
}

// 入队操作（在队尾插入元素）
bool enqueue(Queue *q, int x){
    if (isFull(q)){
        printf("Error：队列已满，插入失败！");
        return false;
    }else{
        q->rear++;
        q->data[q->rear] = x;
        q->size++;
        return true;
    }
}

// 出队操作（在队头删除元素）
bool dequeue(Queue *q, int *x){
    if (isEmpty(q)){
        printf("Error：队列已空，删除失败！");
        return false;
    }else{
        q->front++;
        *x = q->data[q->front];
        q->size--;
        return true;
    }
}

// 获取队头元素
bool getHead(Queue *q, int *x){
    if (isEmpty(q)){
        printf("Error：队列已空！");
        return false;
    }else{
        *x = q->data[q->front+1];
        return true;
    }
}

链式队列

链表是另一种实现队列的方式，链表就是将结点放在任意的内存位置上，通过指针相互连接。链表的优点是没有浪费空间，缺点是需要动态地分配和释放内存存储队列元素。链表也是一种重要的数据结构，下面是链式队列的示意代码：

typedef struct node{
    int data;
    struct node *next;
}Node;

typedef struct {
    Node *front;
    Node *rear;
}Queue;

void initQueue(Queue *q){
    q->front = q->rear = NULL;
}

// 判断队列是否为空
bool isEmpty(Queue *q){
    return (q->front == NULL);
}

// 入队操作（在队尾插入元素）
void enqueue(Queue *q, int x){
    Node *s = (Node*)malloc(sizeof(Node));
    s->data = x;
    s->next = NULL;
    if (q->rear == NULL){
        q->front = q->rear = s;
    }else{
        q->rear->next = s;
        q->rear = s;
    }
}

// 出队操作（在队头删除元素）
int dequeue(Queue *q){
    int x;
    Node *p;
    if (q->front == NULL){
        printf("Error：队列为空！");
        return false;
    }
    x = q->front->data;
    p = q->front;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(p);
    return x;
}

// 获取队头元素
int getHead(Queue *q){
    if (q->front == NULL){
        printf("Error：队列为空！");
        exit(1);
    }
    return q->front->data;
}

队列的应用

BFS广度优先算法

BFS（Breadth-First-Search）也叫广度优先搜索，最短路径是一个重要的应用。BFS算法的核心是从起点开始不断地将其周围的节点加入队列，然后每次从队列首部取出一个节点，如果这个节点是终点，则搜索成功结束；否则继续将该节点周围的节点加入队列，如此往复，直至队列为空或找到终点。下面是BFS算法的示例代码：

#define MAXN 100 // 图的最大节点数
#define INF 0x3f3f3f // 无穷大
int n, e[MAXN][MAXN], dis[MAXN]; // n 为节点数，e 为图的临界矩阵，dis 为起点到其它节点的距离

// BFS广搜模板
void BFS(int s){
    Queue q;
    bool vis[MAXN] = {false}; // 访问标记
    initQueue(&q);
    enqueue(&q, s); // 起点入队
    vis[s] = true; // 标记起点已访问
    while (!isEmpty(&q)){
        int v = dequeue(&q); // 队首元素出队
        for (int i = 0; i < n; i++){
            if (e[v][i] != INF && !vis[i]){ // 如果v和i之间有边并且i未访问过
                dis[i] = dis[v] + 1; // 计算起点到i的距离
                vis[i] = true; // 标记节点i已访问过
                enqueue(&q, i); // 节点i入队
            }
        }
    }
}

循环队列

循环队列是一种环形队列，队尾指针总是在队头指针的左边。当队列头尾相连时，队列到达数组的末尾后就从数组的头重新开始。下面是循环队列的示例代码：

typedef struct{
    int data[MAXQUEUE];
    int front, rear; // 队头和队尾指针
    int size; // 队列中实际元素个数
}Queue;

// 判断队列是否为空
bool isEmpty(Queue *q){
    return (q->front == q->rear);
}

// 判断队列是否已满
bool isFull(Queue *q){
    return (q->rear+1) % MAXQUEUE == q->front;
}

// 入队操作（在队尾插入元素）
bool enqueue(Queue *q, int x){
    if (isFull(q)){
        printf("Error：队列已满，插入失败！");
        return false;
    }else{
        q->rear = (q->rear + 1) % MAXQUEUE;
        q->data[q->rear] = x;
        q->size++;
        return true;
    }
}

// 出队操作（在队头删除元素）
bool dequeue(Queue *q, int *x){
    if (isEmpty(q)){
        printf("Error：队列已空，删除失败！");
        return false;
    }else{
        q->front = (q->front + 1) % MAXQUEUE;
        *x = q->data[q->front];
        q->size--;
        return true;
    }
}

// 获取队头元素
bool getHead(Queue *q, int *x){
    if (isEmpty(q)){
        printf("Error：队列已空！");
        return false;
    }else{
        *x = q->data[(q->front + 1) % MAXQUEUE];
        return true;
    }
}

总结

本篇攻略介绍了队列的特点、实现方法和应用。C语言是很实用的一门编程语言，队列是C语言数据结构中重要的一部分。队列可以理解为排队的过程，插入操作在队尾进行，删除操作在队头进行，先进先出。我们可以用数组或链表实现队列，数组简单易懂，链表存储元素无需按顺序排列。如果不想浪费内存，我们可以使用链式队列，如果空间耗用率不是太高，可以使用顺序队列。在算法实现中，BFS广度优先搜索用于解决最短路径等问题，循环队列可以优化队列的操作，提高效率。理解队列的特点、实现方法和应用，有助于提高编程技巧和程序设计水平。