行业资讯

C语言队列怎么实现

发布时间：2022-04-01 11:08:50 作者：iii
来源：亿速云 阅读：206

C语言队列怎么实现

队列（Queue）是一种常见的数据结构，它遵循先进先出（FIFO, First In First Out）的原则。队列在计算机科学中有广泛的应用，例如任务调度、缓冲区管理、广度优先搜索等。本文将详细介绍如何在C语言中实现队列，包括队列的基本概念、实现方式、常见操作以及应用场景。

1. 队列的基本概念

1.1 队列的定义

队列是一种线性数据结构，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。队列中的元素按照进入队列的顺序排列，最先进入队列的元素最先被删除。

1.2 队列的操作

队列通常支持以下几种基本操作：

1.3 队列的类型

队列可以分为以下几种类型：

本文将重点介绍普通队列和循环队列的实现。

2. 队列的实现方式

在C语言中，队列可以通过数组或链表来实现。下面我们将分别介绍这两种实现方式。

2.1 使用数组实现队列

使用数组实现队列是最简单的方式，但需要注意数组的大小是固定的，因此队列的容量也是有限的。为了充分利用数组空间，通常会使用循环队列的概念。

2.1.1 普通队列的实现

普通队列的实现相对简单，但存在一个问题：当队列的尾部到达数组的末尾时，即使数组的前面有空闲空间，也无法继续插入元素。这会导致空间的浪费。

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

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

// 判断队列是否已满
int isFull(Queue *q) {
    return q->rear == MAX_SIZE - 1;
}

// 入队
void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("队列已满，无法入队\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
}

// 出队
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("队列为空，无法出队\n");
        return -1;
    }
    int item = q->items[q->front];
    q->front++;
    if (q->front > q->rear) {
        q->front = q->rear = -1;
    }
    return item;
}

// 查看队首元素
int peek(Queue *q) {
    if (isEmpty(q)) {
        printf("队列为空\n");
        return -1;
    }
    return q->items[q->front];
}

// 获取队列的大小
int size(Queue *q) {
    if (isEmpty(q)) {
        return 0;
    }
    return q->rear - q->front + 1;
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("队首元素: %d\n", peek(&q));
    printf("队列大小: %d\n", size(&q));

    printf("出队元素: %d\n", dequeue(&q));
    printf("出队元素: %d\n", dequeue(&q));

    printf("队首元素: %d\n", peek(&q));
    printf("队列大小: %d\n", size(&q));

    return 0;
}

2.1.2 循环队列的实现

循环队列通过将数组的首尾相连，形成一个环形结构，从而解决了普通队列的空间浪费问题。

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 5

typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
} CircularQueue;

// 初始化循环队列
void initCircularQueue(CircularQueue *q) {
    q->front = -1;
    q->rear = -1;
}

// 判断循环队列是否为空
int isEmpty(CircularQueue *q) {
    return q->front == -1;
}

// 判断循环队列是否已满
int isFull(CircularQueue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

// 入队
void enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        printf("队列已满，无法入队\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->items[q->rear] = value;
}

// 出队
int dequeue(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("队列为空，无法出队\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX_SIZE;
    }
    return item;
}

// 查看队首元素
int peek(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("队列为空\n");
        return -1;
    }
    return q->items[q->front];
}

// 获取队列的大小
int size(CircularQueue *q) {
    if (isEmpty(q)) {
        return 0;
    }
    if (q->rear >= q->front) {
        return q->rear - q->front + 1;
    } else {
        return MAX_SIZE - q->front + q->rear + 1;
    }
}

int main() {
    CircularQueue q;
    initCircularQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);
    enqueue(&q, 50);

    printf("队首元素: %d\n", peek(&q));
    printf("队列大小: %d\n", size(&q));

    printf("出队元素: %d\n", dequeue(&q));
    printf("出队元素: %d\n", dequeue(&q));

    enqueue(&q, 60);
    enqueue(&q, 70);

    printf("队首元素: %d\n", peek(&q));
    printf("队列大小: %d\n", size(&q));

    return 0;
}

2.2 使用链表实现队列

使用链表实现队列可以避免数组实现中的空间限制问题，因为链表的长度可以动态增长。链表实现的队列通常包含两个指针：一个指向队列的头部（front），另一个指向队列的尾部（rear）。

#include <stdio.h>
#include <stdlib.h>

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

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

// 初始化链表队列
void initLinkedListQueue(LinkedListQueue *q) {
    q->front = NULL;
    q->rear = NULL;
}

// 判断链表队列是否为空
int isEmpty(LinkedListQueue *q) {
    return q->front == NULL;
}

// 入队
void enqueue(LinkedListQueue *q, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(q)) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出队
int dequeue(LinkedListQueue *q) {
    if (isEmpty(q)) {
        printf("队列为空，无法出队\n");
        return -1;
    }
    Node *temp = q->front;
    int item = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return item;
}

// 查看队首元素
int peek(LinkedListQueue *q) {
    if (isEmpty(q)) {
        printf("队列为空\n");
        return -1;
    }
    return q->front->data;
}

// 获取队列的大小
int size(LinkedListQueue *q) {
    int count = 0;
    Node *current = q->front;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

int main() {
    LinkedListQueue q;
    initLinkedListQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("队首元素: %d\n", peek(&q));
    printf("队列大小: %d\n", size(&q));

    printf("出队元素: %d\n", dequeue(&q));
    printf("出队元素: %d\n", dequeue(&q));

    printf("队首元素: %d\n", peek(&q));
    printf("队列大小: %d\n", size(&q));

    return 0;
}

3. 队列的应用场景

队列在计算机科学中有广泛的应用，以下是一些常见的应用场景：

3.1 任务调度

在操作系统中，任务调度通常使用队列来管理等待执行的进程。操作系统将进程按照优先级或其他规则放入队列中，然后按照队列的顺序依次执行。

3.2 缓冲区管理

在网络通信中，数据包的传输通常需要缓冲区来临时存储数据。队列可以用于管理这些缓冲区，确保数据包按照顺序传输。

3.3 广度优先搜索（BFS）

在图论中，广度优先搜索算法使用队列来存储待访问的节点。算法从起始节点开始，依次访问其邻居节点，并将这些邻居节点放入队列中，直到所有节点都被访问。

3.4 打印任务管理

在打印机任务管理中，打印任务通常按照先到先服务的原则进行处理。队列可以用于管理这些打印任务，确保任务按照顺序执行。

4. 总结

本文详细介绍了如何在C语言中实现队列，包括使用数组和链表两种方式。我们还讨论了队列的基本概念、常见操作以及应用场景。队列作为一种重要的数据结构，在计算机科学中有着广泛的应用。通过理解队列的实现原理和应用场景，我们可以更好地解决实际问题。

无论是使用数组还是链表实现队列，都有其优缺点。数组实现的队列简单直观，但容量有限；链表实现的队列可以动态增长，但需要额外的内存管理。在实际应用中，我们可以根据具体需求选择合适的实现方式。

希望本文对你理解和使用队列有所帮助！

推荐阅读：
  1. 使用C语言怎么实现链队列
  2. C语言实现链队列代码

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。

c语言

上一篇：C#怎么生成带注释的dll并引用

下一篇：Kubernetes部署并配置Deploymen、网络映射、副本集的方法

相关阅读

您好，登录后才能下订单哦！

密码登录
登录注册
获取短信验证码
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》
产品服务
地区划分
帮助支持
关于我们
行业资讯-文章归档 问答-问答归档
广州亿速云计算有限公司

7*24小时在线电话：400-100-2938

7*24小时在线QQ：800811969

Copyright © Yisu Cloud Ltd. All Rights Reserved. 2018 版权所有
粤ICP备17096448号-1 粤公网安备 44010402001142号