数据结构之——队列详解-阿里云开发者社区

数据结构之——队列详解

2024-05-27 27

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构之——队列详解

前言：

我们前面已经学习了栈，今天我们来学习队列，队列和栈一样，相对来说比较简单，随后，会为大家准备OJ练习题，敬请期待！

一、什么是队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

这里简单给大家解释一下：

大家肯定都排过队（别说没有，我不信），大家在排好队先前前进时，是不是先站到队伍里的先走。队列的原理何其类似。因为，你可以猜一猜它为什么叫队列。可用下面图片帮助大家理解。

明白了，基础知识，那就一起来实现一下队列吧。

二、队列的实现

2.1 队列结构

和栈一样，我们队列的结构该如何设计呢？

队列一共有两种结构，分为：顺序结构和链式结构

队列的顺序结构

入队，不需要移动任何元素，时间复杂度为O(1)

出队，所有元素需要往前移动，时间复杂度为O(N)

队列的链式结构

首先我们定义两个指针，队头指针指向第一个节点，队尾指针指向尾节点

入队（尾插），时间复杂度为O(1)

出队（头删），时间复杂度为O(1)

这里，我们将采取链式结构，如若对顺序结构感兴趣可结合之前的栈进行实现。

我们要采用链式难道要用二级指针吗？一级已经够麻烦了，使用二级会更晕。所以，为了避免这种轻快，我们可采取结构体，如下代码：

1. typedef int QDataType;
2. // 链式结构：表示队列
3. typedef struct QListNode
4. {
5.  struct QListNode* next;
6.  QDataType data;
7. }QNode;
8. 
9. // 队列的结构 
10. typedef struct Queue
11. {
12.   QNode* phead;
13.   QNode* ptatil;
14.   int size;
15. }Queue;

这样即可避免二级指针。

2.2 队列初始化

1. // 初始化队列 
2. void QueueInit(Queue* q)
3. {
4.  assert(q);
5.  q->phead = q->ptatil = NULL;
6.  q->size = 0;
7. }

初始化只用将头和尾置为空即可。队列还未建立，所以，先不管。

2.3 队列销毁

1. // 销毁队列 
2. void QueueDestroy(Queue* q)
3. {
4.  assert(q);
5.  QNode* cur = q->phead;
6.  while (cur)
7.  {
8.    QNode* next = cur->next;
9.    free(cur);
10.     cur = next;
11.   }
12.   q->phead = q->ptatil = NULL;
13.   q->size = 0;
14. }

销毁时我们要释放的是指针所指向开辟空间，而不是指针本身。所以，使用一个while循来释放。

2.4 入队列

1. // 队尾入队列 
2. void QueuePush(Queue* q, QDataType data)
3. {
4.  assert(q);
5.  QNode* newnode = (QNode*)malloc(sizeof(QNode));
6.  if (newnode == NULL)
7.  {
8.    perror("malloc fail");
9.    return;
10.   }
11.   newnode->next = NULL;
12.   newnode->data = data;
13.   if (q->phead == NULL)//这里使用头节点，尾节点判断均可
14.   {
15.     q->phead = q->ptatil = newnode;
16.   }
17.   else
18.   {
19.     q->ptatil->next = newnode;//记住这里是尾节点，不是头节点！！！
20.     q->ptatil = newnode;
21.   }
22.   q->size++;
23. }

入队列时，我们要为其开辟一块空间也就是QNode，这就是队列的元素。要分为两种情况讨论，队列为空和队列不为空。

2.5 出队列

1. // 队头出队列 
2. void QueuePop(Queue* q)
3. {
4.  assert(q);
5.  assert(q->size != 0);
6.  if (q->phead->next == NULL)
7.  {
8.    q->phead = q->ptatil = NULL;
9.  }
10.   else
11.   {
12.     QNode* next = q->phead->next;
13.     free(q->phead);
14.     q->phead = next;
15.   }
16.   q->size--;
17. }

要注意：分两种情况进行讨论。

2.6 获取队列头部元素

1. // 获取队列头部元素 
2. QDataType QueueFront(Queue* q)
3. {
4.  assert(q);
5.  assert(q->phead);
6.  return q->phead->data;
7. }

这里，直接用头指针返回值即可。

2.7 获取队列尾部元素

1. // 获取队列队尾元素 
2. QDataType QueueBack(Queue* q)
3. {
4.  assert(q);
5.  assert(q->ptatil);
6.  return q->ptatil->data;
7. }

和上面一样，运用指针获取值即可。

2.8 获取队列中有效元素个数

1. int QueueSize(Queue* q)
2. {
3.  assert(q);
4.  return q->size;
5. }

2.9 检测队列是否为空

1. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
2. bool QueueEmpty(Queue* q)
3. {
4.  assert(q);
5.  return q->size == 0;
6. }

三、代码总览

Queue.h

1. #pragma once
2. #include<stdio.h>
3. #include<stdlib.h>
4. #include<stdbool.h>
5. #include<assert.h>
6. 
7. typedef int QDataType;
8. // 链式结构：表示队列
9. typedef struct QListNode
10. {
11.   struct QListNode* next;
12.   QDataType data;
13. }QNode;
14. 
15. // 队列的结构 
16. typedef struct Queue
17. {
18.   QNode* phead;
19.   QNode* ptatil;
20.   int size;
21. }Queue;
22. 
23. // 初始化队列 
24. void QueueInit(Queue* q);
25. // 队尾入队列 
26. void QueuePush(Queue* q, QDataType data);
27. // 队头出队列 
28. void QueuePop(Queue* q);
29. // 获取队列头部元素 
30. QDataType QueueFront(Queue* q);
31. // 获取队列队尾元素 
32. QDataType QueueBack(Queue* q);
33. // 获取队列中有效元素个数 
34. int QueueSize(Queue* q);
35. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
36. bool QueueEmpty(Queue* q);
37. // 销毁队列 
38. void QueueDestroy(Queue* q);
39.

Queue.c

1. #include"Queue.h"
2. 
3. // 初始化队列 
4. void QueueInit(Queue* q)
5. {
6.  assert(q);
7.  q->phead = q->ptatil = NULL;
8.  q->size = 0;
9. }
10. // 队尾入队列 
11. void QueuePush(Queue* q, QDataType data)
12. {
13.   assert(q);
14.   QNode* newnode = (QNode*)malloc(sizeof(QNode));
15.   if (newnode == NULL)
16.   {
17.     perror("malloc fail");
18.     return;
19.   }
20.   newnode->next = NULL;
21.   newnode->data = data;
22.   if (q->phead == NULL)
23.   {
24.     q->phead = q->ptatil = newnode;
25.   }
26.   else
27.   {
28.     q->ptatil->next = newnode;//记住这里是尾节点，不是头节点！！！
29.     q->ptatil = newnode;
30.   }
31.   q->size++;
32. }
33. // 队头出队列 
34. void QueuePop(Queue* q)
35. {
36.   assert(q);
37.   assert(q->size != 0);
38.   if (q->phead->next == NULL)
39.   {
40.     q->phead = q->ptatil = NULL;
41.   }
42.   else
43.   {
44.     QNode* next = q->phead->next;
45.     free(q->phead);
46.     q->phead = next;
47.   }
48.   q->size--;
49. }
50. // 获取队列头部元素 
51. QDataType QueueFront(Queue* q)
52. {
53.   assert(q);
54.   assert(q->phead);
55.   return q->phead->data;
56. }
57. // 获取队列队尾元素 
58. QDataType QueueBack(Queue* q)
59. {
60.   assert(q);
61.   assert(q->ptatil);
62.   return q->ptatil->data;
63. }
64. // 获取队列中有效元素个数 
65. int QueueSize(Queue* q)
66. {
67.   assert(q);
68.   return q->size;
69. }
70. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
71. bool QueueEmpty(Queue* q)
72. {
73.   assert(q);
74.   return q->size == 0;
75. }
76. // 销毁队列 
77. void QueueDestroy(Queue* q)
78. {
79.   assert(q);
80.   QNode* cur = q->phead;
81.   while (cur)
82.   {
83.     QNode* next = cur->next;
84.     free(cur);
85.     cur = next;
86.   }
87.   q->phead = q->ptatil = NULL;
88.   q->size = 0;
89. }

test.c

1. #include"Queue.h"
2. 
3. int main()
4. {
5.  Queue q;
6.  QueueInit(&q);
7.  QueuePush(&q, 1);
8.  QueuePush(&q, 2);
9.  QueuePush(&q, 3);
10.   QueuePush(&q, 4);
11.   while (!QueueEmpty(&q))
12.   {
13.     printf("%d ", QueueFront(&q));
14.     QueuePop(& q);
15.   }
16.   printf("\n");
17.   QueueDestroy(&q);
18.   return 0;
19. }

四、例题

来一道例题来练一练吧！

现有队列Q与栈S，初始时Q中的元素依次是 1,2,3,4,5,6(1在队头)，S 为空。若仅允许下列3种操作:①出队并输出出队元素;②出队并将出队元素入栈;③出栈并输出出栈元素，则不能得到的输出序列是()。

A. 1,2,5,6,4,3 B. 2,3,4,5,6,1 C. 3,4,5,6,1,2 D. 6.5.4.3.2.1

可得：答案为：C。

如果还有什么问题，可以私信也可在评论区留言！

完！

数据结构之——队列详解

前言：

一、什么是队列

二、队列的实现

2.1 队列结构

2.2 队列初始化

2.3 队列销毁

2.4 入队列

2.5 出队列

2.6 获取队列头部元素

2.7 获取队列尾部元素

2.8 获取队列中有效元素个数

2.9 检测队列是否为空

三、代码总览

Queue.h

Queue.c

test.c

四、例题

热门文章

最新文章

相关课程

相关电子书

数据结构之——队列详解

前言：

一、什么是队列

二、队列的实现

2.1 队列结构

2.2 队列初始化

2.3 队列销毁

2.4 入队列

2.5 出队列

2.6 获取队列头部元素

2.7 获取队列尾部元素

2.8 获取队列中有效元素个数

2.9 检测队列是否为空

三、 代码总览

Queue.h

Queue.c

test.c

四、例题

热门文章

最新文章

相关课程

相关电子书

三、代码总览