十、数据结构——链式队列

这篇具有很好参考价值的文章主要介绍了十、数据结构——链式队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构中的链式队列

目录

一、链式队列的定义
二、链式队列的实现
三、链式队列的基本操作

  • ①初始化
    ②判空
    ③入队
    ④出队
    ⑤获取长度
    ⑥打印

四、循环队列的应用
五、总结
六、全部代码
七、结果

在数据结构中,队列(Queue)是一种常见的线性数据结构,遵循先进先出(First In First Out,FIFO)的原则。链式队列是队列的一种实现方式,它使用链表来存储队列中的元素。本篇博客将详细介绍链式队列的定义、实现和基本操作,并附带有带有注释的示例代码。

一、链式队列的定义

链式队列是通过链表实现的一种队列,它将队列的元素通过指针连接起来。链式队列不需要预先分配固定大小的存储空间,因此可以动态增长,更加灵活。

二、链式队列的实现

// 定义节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义链式队列
typedef struct {
    Node* front;
    Node* rear;
} LinkedQueue;

三、链式队列的基本操作

①初始化链式队列

// 初始化链式队列
void initLinkedQueue(LinkedQueue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

②判断队列是否为空

// 判断队列是否为空
int isEmpty(LinkedQueue* queue) {
    return queue->front == NULL;
}

③入队操作

// 入队操作
void enqueue(LinkedQueue* queue, TypeData value) {
    // 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(queue)) {
        // 队列为空,新节点成为队头
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        // 将新节点插入到队尾
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

④ 出队操作

// 出队操作
int dequeue(LinkedQueue* queue) {
    int value = -1;
    if (!isEmpty(queue)) {
        // 保存队头节点的值
        value = queue->front->data;

        // 删除队头节点
        Node* temp = queue->front;
        queue->front = queue->front->next;
        free(temp);

        // 队列为空时,更新rear指针
        if (queue->front == NULL) {
            queue->rear = NULL;
        }
    }
    return value;
}

⑤获取队列中元素的个数

// 获取队列的长度
int getQueueLength(LinkedQueue* queue) {
    Node* current = queue->front;
    int length = 0;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

⑥打印队列内元素

// 打印队列内的元素
void printQueue(LinkedQueue* queue) {
    Node* current = queue->front;
    printf("Queue: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

四、链式队列的应用

链式队列适用于在不确定队列大小的情况下,动态地存储数据。它可以用于解决生产者-消费者问题,以及在需要异步处理数据的情况下。

五、总结

①入队操作:
  • 当队列为空时,新节点既是队头也是队尾。
  • 当队列不为空时,将新节点插入到队尾,并更新rear指针为新节点。
  • 入队操作涉及动态内存分配,要注意释放节点内存以避免内存泄漏。
②出队操作:
  • 在出队操作之前,要先检查队列是否为空,避免出现空队列的错误。
  • 出队操作要删除队头节点,并更新front指针为下一个节点。
  • 如果队列为空,同时要更新rear指针为空。
③判断队列是否为空:
  • 需要根据front指针是否为空来判断队列是否为空。
④获取队列长度:
  • 需要遍历队列中的节点,并计算节点个数来获取队列长度。
⑤动态内存管理:
  • 在链式队列中,需要使用malloc函数为节点分配内存空间。
  • 在节点不再需要时,要使用free函数释放节点的内存空间,以避免内存泄漏。
⑥打印队列元素:
  • 可以通过遍历队列的节点,并输出节点的数据来打印队列中的元素。
⑦队列的初始化:
  • 在使用链式队列之前,要先对其进行初始化,将front和rear指针都设置为空。
⑧注意空队列和满队列:
  • 链式队列一般不会出现满队列的情况,但要注意空队列的处理,以避免出现空指针引用错误。
⑨链表的插入和删除:
  • 在链式队列中,入队操作涉及链表的插入,而出队操作涉及链表的删除。要确保插入和删除的指针操作正确,避免出现内存泄漏或者空指针错误。
⑩异常处理:
  • 在队列操作时,要考虑异常情况,如空队列出队、空指针操作等,要对这些情况进行适当的处理,避免程序崩溃或出现不可预料的错误。

六、全部代码

①listqueue.h

#ifndef _LISTQUEUE_H_
#define _LISTQUEUE_H_
#include <stdio.h>
#include <stdlib.h>
typedef int TypeData;
typedef struct Node {
    TypeData data;
    struct Node* next;
} Node;

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

// 初始化链式队列
void initLinkedQueue(LinkedQueue* queue);

// 判断队列是否为空
int isEmpty(LinkedQueue* queue);

// 入队操作
void enqueue(LinkedQueue* queue, TypeData value) ;

// 出队操作
int dequeue(LinkedQueue* queue);

// 获取队列的长度
int getQueueLength(LinkedQueue* queue)

// 打印队列内的元素
void printQueue(LinkedQueue* queue);

#endif

②listqueue.c

#include "listqueue.h"
// 初始化链式队列
void initLinkedQueue(LinkedQueue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

// 判断队列是否为空
int isEmpty(LinkedQueue* queue) {
    return queue->front == NULL;
}

// 入队操作
void enqueue(LinkedQueue* queue, TypeData value) {
    // 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(queue)) {
        // 队列为空,新节点成为队头
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        // 将新节点插入到队尾
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

// 出队操作
int dequeue(LinkedQueue* queue) {
    int value = -1;
    if (!isEmpty(queue)) {
        // 保存队头节点的值
        value = queue->front->data;

        // 删除队头节点
        Node* temp = queue->front;
        queue->front = queue->front->next;
        free(temp);

        // 队列为空时,更新rear指针
        if (queue->front == NULL) {
            queue->rear = NULL;
        }
    }
    return value;
}

// 获取队列的长度
int getQueueLength(LinkedQueue* queue) {
    Node* current = queue->front;
    int length = 0;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

// 打印队列内的元素
void printQueue(LinkedQueue* queue) {
    Node* current = queue->front;
    printf("Queue: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

③listqueue_main.c

#include "listqueue.h"
#include "listqueue.c"
int main() {
    LinkedQueue queue;
    initLinkedQueue(&queue);

    // 入队操作
    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    // 打印队列内的元素
    printQueue(&queue);

    // 获取队列长度
    int length = getQueueLength(&queue);
    printf("Queue length: %d\n", length);

    // 出队操作
    int value = dequeue(&queue);
    printf("Dequeued value: %d\n", value);

    // 打印出队后的队列
    printQueue(&queue);

    // 获取出队后的队列长度
    length = getQueueLength(&queue);
    printf("Queue length: %d\n", length);

    return 0;
}

七、结果

链式队列,数据结构,数据结构,链表,c语言,算法,linux文章来源地址https://www.toymoban.com/news/detail-733954.html

到了这里,关于十、数据结构——链式队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《数据结构与算法》之队列与链表复习

    我们在上一次学习了堆栈的数据结构以后,可以了解到它是受限制的操作,比如我们操作只能在栈顶,现在我们要学习的东西叫做队列,它也是受限制的一种数据结构,它的特点是队头只出数据,而队尾只入数据, 它的结构就和它的名字,像我们平时排队一样先来的人肯定要

    2024年02月08日
    浏览(53)
  • 数据结构(4) 链表(链式存储)

    顺序表优点:可随机存取,存储密度高,缺点:要求大片连续空间,改变容量不方便。 单链表优点:不要求大片连续空间,改变容量方便,缺点:不可随机存取,要耗费一定空间存放指针。 定义单链表的代码: 定义数据领和指针域 定义一个新节点 定义typedef来缩短函数书写

    2024年02月22日
    浏览(41)
  • 十、数据结构——链式队列

    一、链式队列的定义 二、链式队列的实现 三、链式队列的基本操作 ①初始化 ②判空 ③入队 ④出队 ⑤获取长度 ⑥打印 四、循环队列的应用 五、总结 六、全部代码 七、结果 在数据结构中,队列(Queue)是一种常见的线性数据结构,遵循先进先出(First In First Out,FIFO)的原

    2024年02月07日
    浏览(31)
  • AcWing 算法基础课二 数据结构 链表 栈 队列 并查集 哈希表

    链表题目:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 AcWing. 826.单链表 双链表 AcWing 827.双链表 AcWing 828.模拟栈 AcWing 3302.表达式求值 AcWing 829. 模拟队列 AcWing 830.单调栈 AcWing 154.滑动窗口 AcWing 831. KMP字符串 AcWing 835. Trie字符串统计 AcWing 143. 最大异或对 AcWing 836.合并集合

    2024年02月15日
    浏览(48)
  • C++数据结构与算法详解:链表、栈、队列、树、二叉树和图结构的实现与应用

    链表是一种常见的数据结构由一系列节点按顺序连接而成,一般每个节点包含一个数据元素和一个指向下一个节点的引用。 链表有多种类型: 单向链表:每个节点只有一个指向下一个节点的引用 双向链表:每个节点有一个指向前一个节点和一个指向后一个节点的引用 循环链

    2024年02月04日
    浏览(47)
  • 【脚踢数据结构】队列(顺序和链式)

    (꒪ꇴ꒪ ),Hello我是 祐言QAQ 我的博客主页:C/C++语言,Linux基础,ARM开发板,软件配置等领域博主🌍 快上🚘,一起学习,让我们成为一个强大的攻城狮! 送给自己和读者的一句鸡汤🤔: 集中起来的意志可以击穿顽石! 作者水平很有限,如果发现错误,可在评论区指正,感谢🙏

    2024年02月12日
    浏览(37)
  • 探索数据结构:链式队与循环队列的模拟、实现与应用

    队列(queue)是一种只允许在一端进行插入操作,而在另一端进行删除操作的线性表。其严格遵循 先进先出(First In First Out) 的规则,简称 FIFO 。 队头(Front) :允许删除的一端,又称队首。 队尾(Rear) :允许插入的一端。 队列与栈类似,实现方式有两种。一种是以 数组

    2024年04月08日
    浏览(82)
  • 【算法与数据结构】 C语言实现单链表队列详解

    前面我们学习了队列的顺序表的实现,本节将用单链表实现队列。 队列也可以数组和链表的结构实现, 使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低 。下面我们先复习一下队列的基本概念: 队列:只允许在一端进行插入

    2024年04月11日
    浏览(55)
  • 头歌(C语言)-数据结构与算法-队列-第1关:实现一个顺序存储的队列

    任务描述 相关知识 顺序存储的队列 顺序队列的主要操作 编程要求 测试说明 任务描述 本关任务:实现 step1/SeqQueue.cpp 中的 SQ_IsEmpty 、 SQ_IsFull 、 SQ_Length 、 SQ_In 和 SQ_Out 五个操作函数,以实现判断队列是否为空、是否为满、求队列长度、队列元素入队和出队等功能。 相关知

    2024年02月06日
    浏览(142)
  • 【C/C++数据结构与算法】C语言栈与队列

    目录 一、栈 二、队列 三、循环队列 特性: 顺序存储,后进先出 优点是可随机访问,尾部增删效率高 缺点是可能会浪费空间,不知道头部增删 特性: 链式存储,先进先出 优点是无空间浪费,头部增删效率高 缺点是不能随机访问,尾部增删效率低 特性: 顺序存储,先进先

    2024年02月09日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包