赞
踩
队列(Queue)是一种先进先出(FIFO)的数据结构,它允许在尾部添加元素(入队操作),并从头部移除元素(出队操作)。队列在许多场景中都有应用,下面将给出一些常见的应用以及它们的C语言实现。
在打印机任务队列中,多个打印任务被放入队列中,打印机按照任务进入队列的顺序进行打印。
代码如下:
- #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;
- }
![](https://csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreWhite.png)
在图或树的遍历中,队列被用于实现广度优先搜索。
由于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;
- }
- }
- }
![](https://csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreWhite.png)
队列作为一种基础的数据结构,在多种场景下都有重要的应用。从简单的打印机任务队列到复杂的图遍历算法(如BFS),队列都发挥着关键作用。通过实现队列的基本操作(如入队、出队、判断是否为空或满),我们可以轻松地将队列用于各种实际问题中。在C语言中,我们可以使用数组或链表来实现队列,具体实现方式取决于具体需求(如是否需要动态调整队列大小)。
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。