• 数据结构与算法—队列


    目录

    一、队列的概念及结构

    二、队列的实现

    1、声明队列结构体

    2、初始化

    3、销毁

    4、入队列

    5、判断队列是否为空

    6、出队列

    7、输出队头

    8、输出队尾

    9、输出队列大小

     完整版代码

    Queue.h声明

    Queue.c函数

    test.c测试



    个人专栏持续更新:

    数据结构

    详解C语言

    有需要的看看,如果对你有帮助可以支持一波哦!!

    一、队列的概念及结构

    队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO (First In First Out)
    入队列:进行插入操作的一端称为队尾。
    出队列:进行删除操作的一端称为队头。

    二、队列的实现

    队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,需要数据依次向后移动,效率会比较低。

     1、声明队列结构体

    我们需要两个结构体:

    • 一个储存单个节点的信息(下一个节点的地址和数据),
    • 另一个用于存储队列的信息(头节点和尾节点的地址)。 
    1. typedef int QDataType;
    2. typedef struct QueueNode
    3. {
    4. struct QueueNode* next;
    5. QDataType data;
    6. }QNode;
    7. typedef struct Queue
    8. {
    9. QNode* phead;
    10. QNode* ptail;
    11. int size;
    12. }Queue;
    • 将数据类型定义别名为QueueNode,方便修改数据类型。

    QNode:节点结构体

    • 定义struct QueueNode类型指针指向当前节点的下一个节点。
    • data用于存储数据。
    • 定义结构体别名为QNode

    Queue:队列结构体

    • 包含两个QNode类型指针,分别指向头节点和尾节点。
    • int 类型 size用于统计当前队列大小。
    • 定义结构体别名为Queue。

     2、初始化

    1. void QueueInit(Queue* pq)
    2. {
    3. assert(pq);
    4. pq->phead = NULL;
    5. pq->ptail = NULL;
    6. pq->size = 0;
    7. }
    • assert判断队列地址是否为空,为空则报错。
    • 将头节点和尾节点初始化为空。
    • size初始化为0.

    3、销毁

    1. void QueueDestroy(Queue* pq)
    2. {
    3. assert(pq);
    4. QNode* cur = pq->phead;
    5. while (cur) {
    6. QNode* next = cur->next;
    7. free(cur);
    8. cur = next;
    9. }
    10. pq->phead = pq->ptail = NULL;
    11. pq->size = 0;
    12. }
    • assert判断队列地址是否为空,为空则报错。
    • 指针cur指向头节点,借助cur完成每个节点的销毁。
    • 定义next指向cur的下一个节点
    • 释放cur指向的空间,将cur更新为next。
    • 全部节点销毁后,将头节点和尾节点赋值为空,size更新为0.

    4、入队列

    1. void QueuePush(Queue* pq, QDataType x)
    2. {
    3. assert(pq);
    4. QNode* newnode = (QNode*)malloc(sizeof(QNode));
    5. if (newnode == NULL) {
    6. perror("malloc fail\n");
    7. return;
    8. }
    9. newnode->data = x;
    10. newnode->next = NULL;
    11. if (pq->ptail == NULL) {
    12. assert(pq->phead == NULL);
    13. pq->phead = pq->ptail = newnode;
    14. }
    15. else {
    16. pq->ptail->next = newnode;
    17. pq->ptail = newnode;
    18. }
    19. pq->size++;
    20. }
    • assert判断队列地址是否为空,为空则报错。
    • 为新节点 newnode 开辟空间。
    • 如果开辟失败则通过perror打印失败信息。
    • 将新节点的data赋值为参数 x ,新节点next赋值为空。
    • 如果尾节点为空,同时检查一下头节点是否为空,保证没有错误头尾节点都为空,则将头尾节点赋值为新节点 newnode 。
    • 如果队列不为空,则将新节点插入尾部,尾节点更新为新节点。
    • 最后size加一。

    5、判断队列是否为空

    1. bool QueueEmpty(Queue* pq)
    2. {
    3. assert(pq);
    4. return pq->size == 0;
    5. }
    • assert判断队列地址是否为空,为空则报错。
    • 返回值为1,队列为空;返回值为0,队列不为空。

    6、出队列

    1. void QueuePop(Queue* pq)
    2. {
    3. assert(pq);
    4. assert(!QueueEmpty(pq));
    5. if (pq->phead->next == NULL) {
    6. free(pq->phead);
    7. pq->phead = pq->ptail = NULL;
    8. }
    9. else {
    10. QNode* next = pq->phead->next;
    11. free(pq->phead);
    12. pq->phead = next;
    13. }
    14. pq->size--;
    15. }
    • assert判断队列地址是否为空,为空则报错。
    • assert判断队列是否为空,为空则报错,不能进行删除。
    • 如果删除头节点,则释放头节点的空间,将头尾节点赋值为空。
    • 否则,定义指针next指向头节点的下一个节点,
    • 释放头节点指向的空间,将头节点更新为next。
    • 最后队列大小size减一。

    7、输出队头

    1. QDataType QueueFront(Queue* pq)
    2. {
    3. assert(pq);
    4. assert(!QueueEmpty(pq));
    5. return pq->phead->data;
    6. }
    • assert判断队列地址是否为空,为空则报错。 
    • assert判断队列是否为空,为空则报错,不能进行删除。
    • 返回头节点的data。

    8、输出队尾

    1. QDataType QueueBack(Queue* pq)
    2. {
    3. assert(pq);
    4. assert(!QueueEmpty(pq));
    5. return pq->ptail->data;
    6. }
    • assert判断队列地址是否为空,为空则报错。 
    • assert判断队列是否为空,为空则报错,不能进行删除。
    • 返回头节点的data。

    9、输出队列大小

    1. int QueueSize(Queue* pq)
    2. {
    3. assert(pq);
    4. return pq->size;
    5. }
    • assert判断队列地址是否为空,为空则报错。 、
    • 返回队列大小size。 

     完整版代码

    Queue.h声明

    1. #include
    2. #include
    3. #include
    4. #include
    5. typedef int QDataType;
    6. typedef struct QueueNode
    7. {
    8. struct QueueNode* next;
    9. QDataType data;
    10. }QNode;
    11. typedef struct Queue
    12. {
    13. QNode* phead;
    14. QNode* ptail;
    15. int size;
    16. }Queue;
    17. void QueueInit(Queue* pq);
    18. void QueueDestroy(Queue* pq);
    19. void QueuePush(Queue* pq, QDataType x);
    20. bool QueueEmpty(Queue* pq);
    21. void QueuePop(Queue* pq);
    22. QDataType QueueFront(Queue* pq);
    23. QDataType QueueBack(Queue* pq);
    24. int QueueSize(Queue* pq);

    Queue.c函数

    1. #include "Queue.h"
    2. void QueueInit(Queue* pq)
    3. {
    4. assert(pq);
    5. pq->phead = NULL;
    6. pq->ptail = NULL;
    7. pq->size = 0;
    8. }
    9. void QueueDestroy(Queue* pq)
    10. {
    11. assert(pq);
    12. QNode* cur = pq->phead;
    13. while (cur) {
    14. QNode* next = cur->next;
    15. free(cur);
    16. cur = next;
    17. }
    18. pq->phead = pq->ptail = NULL;
    19. pq->size = 0;
    20. }
    21. void QueuePush(Queue* pq, QDataType x)
    22. {
    23. assert(pq);
    24. QNode* newnode = (QNode*)malloc(sizeof(QNode));
    25. if (newnode == NULL) {
    26. perror("malloc fail\n");
    27. return;
    28. }
    29. newnode->data = x;
    30. newnode->next = NULL;
    31. if (pq->ptail == NULL) {
    32. assert(pq->phead == NULL);
    33. pq->phead = pq->ptail = newnode;
    34. }
    35. else {
    36. pq->ptail->next = newnode;
    37. pq->ptail = newnode;
    38. }
    39. pq->size++;
    40. }
    41. bool QueueEmpty(Queue* pq)
    42. {
    43. assert(pq);
    44. return pq->size == 0;
    45. }
    46. void QueuePop(Queue* pq)
    47. {
    48. assert(pq);
    49. assert(!QueueEmpty(pq));
    50. if (pq->phead->next == NULL) {
    51. free(pq->phead);
    52. pq->phead = pq->ptail = NULL;//防止使用ptail造成对野指针的访问
    53. }
    54. else {
    55. QNode* next = pq->phead->next;
    56. free(pq->phead);
    57. pq->phead = next;
    58. }
    59. pq->size--;
    60. }
    61. QDataType QueueFront(Queue* pq)
    62. {
    63. assert(pq);
    64. assert(!QueueEmpty(pq));
    65. return pq->phead->data;
    66. }
    67. QDataType QueueBack(Queue* pq)
    68. {
    69. assert(pq);
    70. assert(!QueueEmpty(pq));
    71. return pq->ptail->data;
    72. }
    73. int QueueSize(Queue* pq)
    74. {
    75. assert(pq);
    76. return pq->size;
    77. }

    test.c测试

    1. #include"Queue.h"
    2. void TestQueue()
    3. {
    4. Queue q;
    5. QueueInit(&q);
    6. QueuePush(&q, 1);
    7. QueuePush(&q, 2);
    8. QueuePush(&q, 3);
    9. //while (!QueueEmpty(&q)) {
    10. // printf("%d", QueueFront(&q));
    11. // QueuePop(&q);
    12. //}
    13. //printf("\n");
    14. printf("%d\n", QueueBack(&q));
    15. QueueDestroy(&q);
    16. }
    17. int main()
    18. {
    19. TestQueue();
    20. return 0;
    21. }
  • 相关阅读:
    防火墙基本概念
    技术小知识:云计算服务下的IaaS,PaaS,SaaS⑥
    apollo分布式配置优先级学习
    DOPE修饰岩藻多糖 Fucoidan-DOPE 岩藻多糖-二油酰基磷脂酰乙醇胺
    ssm基于Java和MySql的产业信息管理系统的设计与实现毕业设计源码260839
    LCD DRM驱动框架分析一
    【数据结构初阶】Leetcode二叉树基础练习&&完全二叉树判断
    什么是GPT磁盘?介绍GPT(GUID 分区表)磁盘及其优势!
    MyBatis整合Spring的原理分析
    Spring Boot入门教程
  • 原文地址:https://blog.csdn.net/m0_73800602/article/details/134071613