【数据结构】队列的应用（详解）

目录

0  引言

1  打印机任务队列

2  广度优先搜索（BFS）

3  总结

---

0  引言

        队列（Queue）是一种先进先出（FIFO）的数据结构，它允许在尾部添加元素（入队操作），并从头部移除元素（出队操作）。队列在许多场景中都有应用，下面将给出一些常见的应用以及它们的C语言实现。

1  打印机任务队列

        在打印机任务队列中，多个打印任务被放入队列中，打印机按照任务进入队列的顺序进行打印。

        代码如下：

#include <stdio.h>  
#include <stdlib.h>  
  
#define MAX_SIZE 100  
  
typedef struct {  
    int data[MAX_SIZE];  
    int front, rear;  
} Queue;  
  
void initQueue(Queue *q) {  
    q->front = q->rear = -1;  
}  
  
int isFull(Queue *q) {  
    return q->rear == MAX_SIZE - 1;  
}  
  
int isEmpty(Queue *q) {  
    return q->front == -1;  
}  
  
void enqueue(Queue *q, int value) {  
    if (isFull(q)) {  
        printf("Queue is full\n");  
        return;  
    }  
    if (isEmpty(q)) q->front = 0;  
    q->rear++;  
    q->data[q->rear] = value;  
}  
  
int dequeue(Queue *q) {  
    if (isEmpty(q)) {  
        printf("Queue is empty\n");  
        return -1;  
    }  
    int value = q->data[q->front];  
    if (q->front == q->rear) q->front = q->rear = -1;  
    else q->front++;  
    return value;  
}  
  
int main() {  
    Queue q;  
    initQueue(&q);  
    enqueue(&q, 1);  
    enqueue(&q, 2);  
    enqueue(&q, 3);  
    printf("Dequeued: %d\n", dequeue(&q));  
    printf("Dequeued: %d\n", dequeue(&q));  
    return 0;  
}

2  广度优先搜索（BFS）

        在图或树的遍历中，队列被用于实现广度优先搜索。

        由于BFS的实现较长，这里仅给出队列在BFS中的关键应用部分：

        代码如下：

// 假设graph是一个邻接表，visited是一个标记数组  
Queue q;  
initQueue(&q);  
enqueue(&q, startNode); // 将起始节点入队  
visited[startNode] = 1;  
  
while (!isEmpty(&q)) {  
    int currentNode = dequeue(&q);  
    // 访问当前节点  
    // ...  
  
    // 将当前节点的所有未访问邻居入队  
    for (int i = 0; i < graph[currentNode].size; i++) {  
        int neighbor = graph[currentNode].adj[i];  
        if (!visited[neighbor]) {  
            enqueue(&q, neighbor);  
            visited[neighbor] = 1;  
        }  
    }  
}

3  总结

        队列作为一种基础的数据结构，在多种场景下都有重要的应用。从简单的打印机任务队列到复杂的图遍历算法（如BFS），队列都发挥着关键作用。通过实现队列的基本操作（如入队、出队、判断是否为空或满），我们可以轻松地将队列用于各种实际问题中。在C语言中，我们可以使用数组或链表来实现队列，具体实现方式取决于具体需求（如是否需要动态调整队列大小）。