队列的实现与讲授

一.概念与结构

1.概念

只允许在⼀端举行插⼊数据操纵，在另⼀端举行删除数据操纵的特殊线性表，队列具有先辈先出FIFO(First In First Out)
​ 入队列：进⾏插⼊操纵的⼀端称为队尾
​ 出队列：进⾏删除操纵的⼀端称为队头
注意：与上文讲到的栈对比，栈是先辈后出，队列是先辈先出。
2.结构


队列也可以数组和链表的结构实现，使⽤链表的结构实现更优⼀些，由于假如使⽤数组的结构，出队列在数组头上出数据，服从会⽐较低。
数组头删时间复杂度：O(N) ** 数组尾插时间复杂度：O(1)
单链表头删时间复杂度：O(1) 单链表尾插时间复杂度：O(N)
 因此下战书队列的实现中，我们接纳链表的结构来举行。
二.队列的实现

queue.h

完备头文件如下。

2. #pragma once
3. #include <stdio.h>
4. #include <stdlib.h>
5. #include <assert.h>
6. #include <stdbool.h>
7. typedef int QDataType;
8. typedef struct QueueNode//队列节点的结构,即单链表节点的结构
9. {
10.         QDataType data;
11.         struct QueueNode* next;
12. }QNode;
13. typedef struct Queue//队列的结构,定义指向队列头尾的指针,以及队列节点的个数
14. {
15.         QNode* phead;
16.         QNode* ptail;
17.         QDataType size;
18. }Q;
20. void QueueInit(Q*);
22. //入队列,队尾
23. void QueuePush(Q*, QDataType);
25. //出队列,队头
26. void QueuePop(Q*);
28. //队列判空
29. bool QueueEmpty(Q*);
31. //取队头数据
32. QDataType QueueFront(Q*);
34. //取队尾数据
35. QDataType QueueBack(Q*);
37. //队列有效元素个数
38. int QueueSize(Q*);
40. void QueueDestroy(Q*);

复制代码

分析：
1.此处我们界说了两个结构体，一个是队列的根本结构QNode，一个是用来表现队列的队头，队尾和元素个数的Q。
2.Q存在的意义紧张是为了便于后续表现队列的队头，队尾时可以简化二级指针的个数，且更加清晰。

test.c

相干测试代码如下。

2. #define _CRT_SECURE_NO_WARNINGS 1
3. #include "Queue.h"
4. void QueueTest01()
5. {
6.         Q q;//定义队列
7.         QueueInit(&q);
8.         QueuePush(&q, 1);
9.         QueuePush(&q, 2);
10.         QueuePush(&q, 3);
11.         QueuePush(&q, 4);
12.         ///
13.         printf("head:%d\n", QueueFront(&q));
14.         printf("tail:%d\n", QueueBack(&q));
15.         printf("size:%d\n", QueueSize(&q));
16.         QueuePop(&q);
17.         QueueDestroy(&q);
18. }
20. int main()
21. {
22.         QueueTest01();
23.         return 0;
24. }

复制代码

队列的初始化

2. #define _CRT_SECURE_NO_WARNINGS 1
3. #include "Queue.h"
4. void QueueInit(Q* pq)
5. {
6.         assert(pq);
7.         pq->phead = pq->ptail = NULL;
8.         pq->size = 0;
9. }

复制代码

分析：
1.需注意，我们此处传入的是指针Q*而非QNode*。
2.别的置空断言操纵如常。
队列的烧毁

2. void QueueDestroy(Q* pq)
3. {
4.         assert(pq);
5.         assert(!QueueEmpty(pq));
6.         QNode* pcur = pq->phead;
7.         while (pcur)
8.         {
9.                 QNode* next = pcur->next;
10.                 free(pcur);
11.                 pcur = next;
12.         }
13.         pq->phead = pq->ptail = NULL;
14.         pq->size = 0;
15. }

复制代码

分析：
1.由于每个节点与之前的链表类似，都是动态开发的，因此我们通过Q*找到队列头phead，之后逐个开释节点即可。
2.依次开释之后置空并将元素个数置为0即可。
节点的创建

起首创建一个专门用来生产节点的函数，克制后续插入期间码的冗余。

2. QNode* BuyNode(QDataType x)
3. {
4.         QNode* newnode = (QNode*)malloc(sizeof(QNode));
5.         if (newnode == NULL)
6.         {
7.                 perror("malloc fail!");
8.                 exit(1);
9.         }
10.         newnode->data = x;
11.         newnode->next = NULL;
12.         return newnode;
13. }

复制代码

注意：在创建节点跋文得把size++。

队尾插入数据——入队列

2. void QueuePush(Q* pq, QDataType x)
3. {
4.         assert(pq);
5.         if (pq->phead == NULL)
6.                 pq->phead = pq->ptail = BuyNode(x);
7.         else
8.         {
9.                 pq->ptail->next = BuyNode(x);
10.                 pq->ptail = pq->ptail->next;
11.         }
12.         pq->size++;
13. }

复制代码

分析：与链表的尾插原理根本类似。
队列判空

在进入删除之前，起首必要判断队列数据个数是否为空。

2. bool QueueEmpty(Q* pq)
3. {
4.         assert(pq);
5.         return pq->phead == NULL && pq->ptail == NULL;
6. }

复制代码

此处通过利用size个数是否为0举行判空也可。
队头删除数据——出队列

2. void QueuePop(Q* pq)
3. {
4.         assert(pq);
5.         assert(!QueueEmpty(pq));
7.         //只有一个节点的情况,避免ptail变成野指针
8.         if (pq->ptail == pq->phead)
9.         {
10.                 free(pq->phead);
11.                 pq->phead = pq->ptail = NULL;
12.         }
13.         else
14.         {
15.                 QNode* next = pq->phead->next;
16.                 free(pq->phead);
17.                 pq->phead = next;
18.         }
19.         pq->size--;
20. }

复制代码

分析：
1.起首判断队列数据是否为空。
2.之后思量两种情况，假如队列只有一个节点，那么直接删除之后必要将队头和队尾都置为空。
3，假如队列不止存在一个节点，同链表的删除原理类似。

返回队头数据

2. QDataType QueueFront(Q* pq)
3. {
4.         assert(pq);
5.         assert(!QueueEmpty(pq));
6.         return pq->phead->data;
7. }

复制代码

返回队尾数据

2. QDataType QueueBack(Q* pq)
3. {
4.         assert(pq);
5.         assert(!QueueEmpty(pq));
6.         return pq->ptail->data;
7. }

复制代码

输出队列数据个数

2. int QueueSize(Q* pq)
3. {
4.         assert(pq);
6.         //不规范且时间复杂度O(n)
7.         //int size = 0;
8.         //QNode* pcur = pq->phead;
9.         //while (pcur)
10.         //{
11.         //        size++;
12.         //        pcur = pcur->next;
13.         //}
14.         //return size;
17.         return pq->size;
19. }

复制代码

分析：
1.假如我们不在最初引入变量size记载数据个数，由于队列是链表结构无法直接通过下标访问元素个数，必要逐个遍历记载，时间复杂度为O（n）。
2.直接返回size的话就可以镌汰时间斲丧。
三.完备代码

2. #define _CRT_SECURE_NO_WARNINGS 1
3. #include "Queue.h"
4. void QueueInit(Q* pq)
5. {
6.         assert(pq);
7.         pq->phead = pq->ptail = NULL;
8.         pq->size = 0;
9. }
11. QNode* BuyNode(QDataType x)
12. {
13.         QNode* newnode = (QNode*)malloc(sizeof(QNode));
14.         if (newnode == NULL)
15.         {
16.                 perror("malloc fail!");
17.                 exit(1);
18.         }
19.         newnode->data = x;
20.         newnode->next = NULL;
21.         return newnode;
22. }
24. void QueuePush(Q* pq, QDataType x)
25. {
26.         assert(pq);
27.         if (pq->phead == NULL)
28.                 pq->phead = pq->ptail = BuyNode(x);
29.         else
30.         {
31.                 pq->ptail->next = BuyNode(x);
32.                 pq->ptail = pq->ptail->next;
33.         }
34.         pq->size++;
35. }
37. bool QueueEmpty(Q* pq)
38. {
39.         assert(pq);
40.         return pq->phead == NULL && pq->ptail == NULL;
41. }
43. void QueuePop(Q* pq)
44. {
45.         assert(pq);
46.         assert(!QueueEmpty(pq));
48.         //只有一个节点的情况,避免ptail变成野指针
49.         if (pq->ptail == pq->phead)
50.         {
51.                 free(pq->phead);
52.                 pq->phead = pq->ptail = NULL;
53.         }
54.         else
55.         {
56.                 QNode* next = pq->phead->next;
57.                 free(pq->phead);
58.                 pq->phead = next;
59.         }
60.         pq->size--;
61. }
63. QDataType QueueFront(Q* pq)
64. {
65.         assert(pq);
66.         assert(!QueueEmpty(pq));
67.         return pq->phead->data;
68. }
69. QDataType QueueBack(Q* pq)
70. {
71.         assert(pq);
72.         assert(!QueueEmpty(pq));
73.         return pq->ptail->data;
74. }
76. int QueueSize(Q* pq)
77. {
78.         assert(pq);
80.         //不规范且时间复杂度O(n)
81.         //int size = 0;
82.         //QNode* pcur = pq->phead;
83.         //while (pcur)
84.         //{
85.         //        size++;
86.         //        pcur = pcur->next;
87.         //}
88.         //return size;
91.         return pq->size;
93. }
95. void QueueDestroy(Q* pq)
96. {
97.         assert(pq);
98.         assert(!QueueEmpty(pq));
99.         QNode* pcur = pq->phead;
100.         while (pcur)
101.         {
102.                 QNode* next = pcur->next;
103.                 free(pcur);
104.                 pcur = next;
105.         }
106.         pq->phead = pq->ptail = NULL;
107.         pq->size = 0;
108. }

复制代码

以上就是关于队列的概念，结构和用链表方式实现队列的讲授，欢迎各位大佬前来支持斧正！！！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金