【数据结构】队列的应用（详解）
目次0 引言
1 打印机使命队列
2 广度优先搜索（BFS）
3 总结
0 引言
队列（Queue）是一种先辈先出（FIFO）的数据结构，它答应在尾部添加元素（入队操作），并从头部移除元素（出队操作）。队列在许多场景中都有应用，下面将给出一些常见的应用以及它们的C语言实现。
1 打印机使命队列
在打印机使命队列中，多个打印使命被放入队列中，打印机按照使命进入队列的顺序进行打印。
代码如下：
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int data;
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 = value;
}
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
return -1;
}
int value = q->data;
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 = 1;
while (!isEmpty(&q)) {
int currentNode = dequeue(&q);
// 访问当前节点
// ...
// 将当前节点的所有未访问邻居入队
for (int i = 0; i < graph.size; i++) {
int neighbor = graph.adj;
if (!visited) {
enqueue(&q, neighbor);
visited = 1;
}
}
} 3 总结
队列作为一种基础的数据结构，在多种场景下都有紧张的应用。从简单的打印机使命队列到复杂的图遍历算法（如BFS），队列都发挥着关键作用。通过实现队列的根本操作（如入队、出队、判定是否为空或满），我们可以轻松地将队列用于各种实际题目中。在C语言中，我们可以利用数组或链表来实现队列，详细实现方式取决于详细需求（如是否需要动态调整队列大小）。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]