qidao123.com技术社区-IT企服评测·应用市场

标题: 数据布局初阶：队列 [打印本页]
作者: 用多少眼泪才能让你相信    时间: 2025-4-18 11:35
标题: 数据布局初阶：队列
本篇博客告急讲解队列的相干知识。
目录
 1.队列
1.1 概念与布局
 1.2 队列头文件（Queue.h）
1.2.1 界说队列结点布局
1.2.2 界说队列的布局
 1.3 队列源代码（Queue.h）
1.3.1 队列的初始化
 1.3.2 队列的烧毁
 1.3.3 入队---队尾
 1.3.4 判空
1.3.5 出队--队头
1.3.6 取队头数据 和 取队尾数据


 1.队列

1.1 概念与布局

概念：只答应在一端进行插入数据操作，在另一端进行删除数据操作的特别线性表，队列具有先进先出FIFP（First in First Out）
入队列：进行插入操作的一端称作队尾
出队列：进行删除操作的一端称作队头
 队列也可以用数组和链表的布局实现，利用链表的布局实现更优一些，因为如果利用数组的布局，出队列在数组头上出数据，服从会比较低下。
 1.2 队列头文件（Queue.h）

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. #include<stdbool.h>
  7. //定义结点的结构
  8. typedef int QDataTpe;
  9. typedef struct QueueNode
  10. {
  11.         QDataTpe data;
  12.         struct QueueNode* next;
  13. }QueueNode;
  15. //定义队列的结构
  16. typedef struct Queue {
  17.         QueueNode* phead;//队头
  18.         QueueNode* ptail;//队尾
  19.         int size;//记录有效数据个数
  20. }Queue;
  22. void QueueInit(Queue* pq);
  23. //销毁队列
  24. void QueueDestroy(Queue* pq);
  26. //入队---队尾
  27. void QueuePush(Queue* pq, QDataTpe x);
  28. //出队---队头
  29. void QueuePop(Queue* pq);
  31. //取队头数据
  32. QDataTpe QueueFront(Queue* pq);
  33. //取队尾数据
  34. QDataTpe QueueBack(Queue* pq);
  36. bool QueueEmpty(Queue* pq);
  37. //队列有效元素个数
  38. int QueueSize(Queue* pq);
复制代码
1.2.1 界说队列结点布局

  1. //定义结点的结构
  2. typedef int QDataTpe;
  3. typedef struct QueueNode
  4. {
  5.         QDataTpe data;
  6.         struct QueueNode* next;
  7. }QueueNode;
复制代码
代码逻辑：
   首先，通过typedef界说了一个整数类型QDataTpe，这里现实上是将int类型取了一个别名QDataTpe。
  然后，界说了一个布局体QueueNode，这个布局体包罗了两个成员：
  
  通过如许的界说，可以方便地创建和操作队列节点，为构建队列数据布局奠定了基础。
  1.2.2 界说队列的布局

  1. //定义队列的结构
  2. typedef struct Queue {
  3.         QueueNode* phead;//队头
  4.         QueueNode* ptail;//队尾
  5.         int size;//记录有效数据个数
  6. }Queue;
复制代码
 代码逻辑：
   界说了一个布局体Queue，此中包罗了三个成员：
  
  通过如许的界说，可以方便地对队列进行操作，如入队、出队等。
   1.3 队列源代码（Queue.h）

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include"Queue.h"
  4. void QueueInit(Queue* pq)
  5. {
  6.         assert(pq);
  7.         pq->phead = pq->ptail = NULL;
  8. }
  9. //销毁队列
  10. void QueueDestroy(Queue* pq)
  11. {
  12.         assert(pq);
  13.         QueueNode* pcur = pq->phead;
  14.         while (pcur)
  15.         {
  16.                 QueueNode* next = pcur->next;
  17.                 free(pcur);
  18.                 pcur = next;
  19.         }
  20.         pq->phead = pq->ptail = NULL;
  21. }
  22. //入队---队尾
  23. void QueuePush(Queue* pq, QDataTpe x)
  24. {
  25.         assert(pq);
  26.         //newnode
  27.         QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  28.         if (newnode == NULL)
  29.         {
  30.                 perror("malloc fail!");
  31.                 exit(1);
  32.         }
  33.         newnode->data = x;
  34.         newnode->next = NULL;
  36.         //队列为空，newnode是队头也是队尾
  37.         if (pq->phead == NULL)
  38.         {
  39.                 pq->phead = pq->ptail = newnode;
  40.         }
  41.         else {
  42.                 //队列非空，直接插入到队尾
  43.                 pq->ptail->next = newnode;
  44.                 pq->ptail = pq->ptail->next;
  45.         }
  46.         pq->size++;
  47. }
  48. bool QueueEmpty(Queue* pq)
  49. {
  50.         assert(pq);
  51.         return pq->phead == 0;
  52. }
  53. //出队---队头
  54. void QueuePop(Queue* pq)
  55. {
  56.         assert(!QueueEmpty(pq));
  57.         //只有一个结点的情况
  58.         if (pq->phead == pq->ptail)
  59.         {
  60.                 free(pq->phead);
  61.                 pq->phead = pq->ptail = NULL;
  62.         }
  63.         else {
  64.                 QueueNode* next = pq->phead->next;
  65.                 free(pq->phead);
  66.                 pq->phead = next;
  67.         }
  68.         pq->size--;
  69. }
  70. //取队头数据
  71. QDataTpe QueueFront(Queue* pq)
  72. {
  73.         assert(!QueueEmpty(pq));
  74.         return pq->phead->data;
  75. }
  76. //取队尾数据
  77. QDataTpe QueueBack(Queue* pq)
  78. {
  79.         assert(!QueueEmpty(pq));
  80.         return pq->ptail->data;
  81. }
  83. //队列有效元素个数
  84. int QueueSize(Queue* pq)
  85. {
  86.         return pq->size;
  87. }
复制代码
1.3.1 队列的初始化

  1. void QueueInit(Queue* pq)
  2. {
  3.         assert(pq);
  4.         pq->phead = pq->ptail = NULL;
  5. }
复制代码
代码逻辑： 
   函数的参数是一个指向Queue布局体的指针pq。在函数内部，首先利用assert判定pq是否有效，首先利用assert函数查抄pq是否有效。
  然后，将队列的队头指针 pq -> phead 和 队尾指针 pq ->ptail 都初始化为NULL，表现初始状态下队列为空。
   1.3.2 队列的烧毁

  1. //销毁队列
  2. void QueueDestroy(Queue* pq)
  3. {
  4.         assert(pq);
  5.         QueueNode* pcur = pq->phead;
  6.         while (pcur)
  7.         {
  8.                 QueueNode* next = pcur->next;
  9.                 free(pcur);
  10.                 pcur = next;
  11.         }
  12.         pq->phead = pq->ptail = NULL;
  13. }
复制代码
代码逻辑： 
   函数的参数是一个指向Queue布局体的指针pq。首先利用assert函数查抄pq是否有效。
  然后，通过一个循环遍历队列的节点。在循环中，先保存当前节点的下一个节点的指针next，然后开释当前节点的内存空间，末了将当前节点指针移动到下一个节点。当循环竣事后，将队列的队头指针pq->phead和队尾指针pq->ptail都设置为NULL，表现队列已被烧毁。
   1.3.3 入队---队尾

  1. //入队---队尾
  2. void QueuePush(Queue* pq, QDataTpe x)
  3. {
  4.         assert(pq);
  5.         //newnode
  6.         QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  7.         if (newnode == NULL)
  8.         {
  9.                 perror("malloc fail!");
  10.                 exit(1);
  11.         }
  12.         newnode->data = x;
  13.         newnode->next = NULL;
  15.         //队列为空，newnode是队头也是队尾
  16.         if (pq->phead == NULL)
  17.         {
  18.                 pq->phead = pq->ptail = newnode;
  19.         }
  20.         else {
  21.                 //队列非空，直接插入到队尾
  22.                 pq->ptail->next = newnode;
  23.                 pq->ptail = pq->ptail->next;
  24.         }
  25.         pq->size++;
  26. }
复制代码
代码逻辑： 
   函数的参数是一个指向Queue布局体的指针pq和要入队的元素x。首先利用assert函数查抄pq是否有效。然后，利用malloc函数分配一个新的QueueNode节点newnode，并为其分配内存空间。如果内存分配失败（newnode为NULL），则输堕落误信息并退出程序。
  接下来，将入队元素的值赋给新节点的data成员，并将新节点的next指针设置为NULL。
  然后，通过判定队列是否为空来确定新节点的插入位置。如果队列为空，将新节点同时设置为队头和队尾；如果队列非空，将新节点插入到队尾，并更新队尾指针。
  末了，将队列的有效数据个数加1。
   1.3.4 判空

  1. bool QueueEmpty(Queue* pq)
  2. {
  3.         assert(pq);
  4.         return pq->phead == 0;
  5. }
复制代码
 代码逻辑同上篇博客雷同，不外多赘述。
1.3.5 出队--队头

  1. //出队---队头
  2. void QueuePop(Queue* pq)
  3. {
  4.         assert(!QueueEmpty(pq));
  5.         //只有一个结点的情况
  6.         if (pq->phead == pq->ptail)
  7.         {
  8.                 free(pq->phead);
  9.                 pq->phead = pq->ptail = NULL;
  10.         }
  11.         else {
  12.                 QueueNode* next = pq->phead->next;
  13.                 free(pq->phead);
  14.                 pq->phead = next;
  15.         }
  16.         pq->size--;
  17. }
复制代码
 代码逻辑：
   函数的参数是一个指向Queue布局体的指针pq。首先利用assert函数和QueueEmpty函数来查抄队列是否为空，如果队列为空则会产生断言错误。
  接下来，通过判定队列中节点的数目来确定出队的详细操作。如果队列中只有一个节点，那么开释该节点的内存空间，并将队头和队尾指针都设置为NULL。如果队列中有多个节点，那么保存队头节点的下一个节点的指针next，开释队头节点的内存空间，然后将队头指针更新为next。
  末了，将队列的有效数据个数减1。
  1.3.6 取队头数据 和 取队尾数据

  1. //取队头数据
  2. QDataTpe QueueFront(Queue* pq)
  3. {
  4.         assert(!QueueEmpty(pq));
  5.         return pq->phead->data;
  6. }
  7. //取队尾数据
  8. QDataTpe QueueBack(Queue* pq)
  9. {
  10.         assert(!QueueEmpty(pq));
  11.         return pq->ptail->data;
  12. }
复制代码
代码逻辑： 
   
   2. 小结

以上便是本篇博客关于队列的全部内容，如果能给各人带来知识，还请支持支持博主。


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/) Powered by Discuz! X3.4