数据布局初阶：队列

本篇博客告急讲解队列的相干知识。
目录
 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，这个布局体包罗了两个成员：
  

• QDataTpe data：用于存储节点的数据。
  
• struct QueueNode* next：一个指向布局体QueueNode的指针，用于指向下一个节点，从而形成链表布局。
  

  通过如许的界说，可以方便地创建和操作队列节点，为构建队列数据布局奠定了基础。
  1.2.2 界说队列的布局

1. //定义队列的结构
2. typedef struct Queue {
3.         QueueNode* phead;//队头
4.         QueueNode* ptail;//队尾
5.         int size;//记录有效数据个数
6. }Queue;

复制代码

 代码逻辑：
   界说了一个布局体Queue，此中包罗了三个成员：
  

• QueueNode* phead：一个指向QueueNode布局体的指针，用于表现队列的队头。
  
• QueueNode* ptail：一个指向QueueNode布局体的指针，用于表现队列的队尾。
  
• int size：用于记录队列中有效数据的个数。
  

  通过如许的界说，可以方便地对队列进行操作，如入队、出队等。
   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. }

复制代码

代码逻辑： 
   

• QDataTpe QueueFront(Queue* pq)：这个函数用于获取队列的队头数据。函数首先利用assert函数和QueueEmpty函数来查抄队列是否为空，如果队列为空则会产生断言错误。如果队列不为空，那么直接返回队头节点的data成员的值。
  
• QDataTpe QueueBack(Queue* pq)：这个函数用于获取队列的队尾数据。函数的查抄流程和QueueFront函数雷同，也是先查抄队列是否为空，如果不为空，那么直接返回队尾节点的data成员的值。
  

   2. 小结

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

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