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

目次


0  引言
1  打印机使命队列
2  广度优先搜索（BFS）
3  总结

---

0  引言

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

        在打印机使命队列中，多个打印使命被放入队列中，打印机按照使命进入队列的顺序进行打印。
        代码如下：

1. #include <stdio.h>  
2. #include <stdlib.h>  
3.   
4. #define MAX_SIZE 100  
5.   
6. typedef struct {  
7.     int data[MAX_SIZE];  
8.     int front, rear;  
9. } Queue;  
10.   
11. void initQueue(Queue *q) {  
12.     q->front = q->rear = -1;  
13. }  
14.   
15. int isFull(Queue *q) {  
16.     return q->rear == MAX_SIZE - 1;  
17. }  
18.   
19. int isEmpty(Queue *q) {  
20.     return q->front == -1;  
21. }  
22.   
23. void enqueue(Queue *q, int value) {  
24.     if (isFull(q)) {  
25.         printf("Queue is full\n");  
26.         return;  
27.     }  
28.     if (isEmpty(q)) q->front = 0;  
29.     q->rear++;  
30.     q->data[q->rear] = value;  
31. }  
32.   
33. int dequeue(Queue *q) {  
34.     if (isEmpty(q)) {  
35.         printf("Queue is empty\n");  
36.         return -1;  
37.     }  
38.     int value = q->data[q->front];  
39.     if (q->front == q->rear) q->front = q->rear = -1;  
40.     else q->front++;  
41.     return value;  
42. }  
43.   
44. int main() {  
45.     Queue q;  
46.     initQueue(&q);  
47.     enqueue(&q, 1);  
48.     enqueue(&q, 2);  
49.     enqueue(&q, 3);  
50.     printf("Dequeued: %d\n", dequeue(&q));  
51.     printf("Dequeued: %d\n", dequeue(&q));  
52.     return 0;  
53. }

复制代码

2  广度优先搜索（BFS）

        在图或树的遍历中，队列被用于实现广度优先搜索。
        由于BFS的实现较长，这里仅给出队列在BFS中的关键应用部分：
        代码如下：

1. // 假设graph是一个邻接表，visited是一个标记数组  
2. Queue q;  
3. initQueue(&q);  
4. enqueue(&q, startNode); // 将起始节点入队  
5. visited[startNode] = 1;  
6.   
7. while (!isEmpty(&q)) {  
8.     int currentNode = dequeue(&q);  
9.     // 访问当前节点  
10.     // ...  
11.   
12.     // 将当前节点的所有未访问邻居入队  
13.     for (int i = 0; i < graph[currentNode].size; i++) {  
14.         int neighbor = graph[currentNode].adj[i];  
15.         if (!visited[neighbor]) {  
16.             enqueue(&q, neighbor);  
17.             visited[neighbor] = 1;  
18.         }  
19.     }  
20. }

复制代码

3  总结

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。