前言

  前面学习了栈，特点是后进先出，今天讲解的队列与其恰恰相反，是先进先出，先进来的数据先出去。

1.队列

1.1 队列的概念及结构

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

1.2 队列的实现

  队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

1. front == NULL，tail = = NULL说明队列为空。
2. 当插入第一个元素时front与tail同时指向第一个元素。
3. 当入队列时，就是单链表的尾插。
4. 当出队列时，就是单链表的头删。

2. 各功能的解析及实现

2.1 队列的创建

  我们采用链表的方式进行实现，因为如果用数组的话，在进行出队列操作时，需要将全部元素都往前移一位，实际上就是将第一个元素覆盖了，比较繁琐，效率没有链表高，所以此处采用链表的方式进行实现。

typedef int Datatype;
//链式结构表示队列
typedef struct QListNode
{
Datatype data;
struct Queue* next;
}QNode;

typedef struct Queue
{
QNode* front;
QNode* tail;
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13

  我们定义了两个结构体，一个就是每个元素的内容，一个数据域以及一个指针域。另一个是指向元素的指针，因为在队列里需要用到两个，所以直接封装起来用比较好一些。同时封装到一个结构体内，我们就可以指针传递结构体的指针就可以了，就不需要传递单个（单独的front或者tail）的二级指针。（如果不太理解的话，可以将后续的代码与单链表这篇博客里面的代码进行比较观看，可以更好的理解为什么这里是传递一级指针，而单链表中传递的是二级指针。

2.2 初始化队列

  将指针置空即可，防止出现野指针问题。

void QueueInit(Queue* pq)
{
assert(pq);
pq->front = NULL;
pq->tail = NULL;
}
1
2
3
4
5
6

2.3 队尾入队列

  每次入队列都开辟一个新空间存放元素，然后再进行尾插就完成了。需要注意的是当插入第一个元素的时候是将新结点的地址给了front与tail，而不是进行尾插。因此此时的front与tail是空指针，是不能对他们进行解引用的。

void QueuePush(Queue* pq, Datatype x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
printf("开辟失败！！");
return;
}
newnode->next = NULL;
newnode->data = x;

if (pq->front == NULL)
{
pq->tail = newnode;
pq->front = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = pq->tail->next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.4 队头出队列

  删除队头元素，我们只需要保存第二个元素的地址，然后将队头元素的空间进行释放即可，然后再将front移到第二个元素的位置。需要注意的是，当队列中仅剩一个结点时，front与tail指向的是同一块空间，当对front进行释放时，tail也会被释放，如图：
  此时tail就是一个野指针，指向一块已经被释放的空间，因此我们需要加一个判断，也就是当front == NULL时，tail也要被置为NULL。

void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));

QNode* next = pq->front->next;
free(pq->front);
pq->front = next;
if (pq->front == NULL)
{
pq->tail = NULL;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.5 获取队头元素

  唯一需要注意的就是需要判断一下队列是否为空即可。

Datatype QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->front->data;
}
1
2
3
4
5
6

2.6 获取队尾元素

  唯一需要注意的就是需要判断一下队列是否为空即可。

Datatype QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
1
2
3
4
5
6

2.7 队列中有效元素个数

  从头遍历依次计算即可。

int QueueSize(Queue* pq)
{
assert(pq);
int count = 0;
QNode* cur = pq->front;
while (cur)
{
count++;
cur = cur->next;
}
return count;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.8 检查队列是否为空

  队列为空的状态就是front是空指针，没有指向元素。

bool QueueEmpty(Queue* pq)
{
assert(pq);
if (pq->front == NULL)
{
return true;
}
return false;
}
1
2
3
4
5
6
7
8
9

2.9 销毁队列

  只需要提前保存准备释放结点的下一个结点地址，然后不断循环进行释放就可以了。

void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->front;
while (cur != NULL)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->front = NULL;
pq->tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.代码实现

3.1 Queue.h

  包含队列的创建以及各个功能函数的声明。

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int Datatype;

//链式结构表示队列
typedef struct QListNode
{
Datatype data;
struct Queue* next;
}QNode;

typedef struct Queue
{
QNode* front;
QNode* tail;
}Queue;

// 初始化队列
void QueueInit(Queue* pq);

// 队尾入队列
void QueuePush(Queue* pq, Datatype data);

// 队头出队列
void QueuePop(Queue* pq);

// 获取队列头部元素
Datatype QueueFront(Queue* pq);

// 获取队列队尾元素
Datatype QueueBack(Queue* pq);

// 获取队列中有效元素个数
int QueueSize(Queue* pq);

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq);

// 销毁队列
void QueueDestroy(Queue* pq);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

3.2 Queue.c

  各个功能函数的实现。

#include"Queue.h"

void QueueInit(Queue* pq)
{
assert(pq);

pq->front = NULL;
pq->tail = NULL;
}

void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->front;
while (cur != NULL)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->front = NULL;
pq->tail = NULL;
}

void QueuePush(Queue* pq, Datatype x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
printf("开辟失败！！");
return;
}
newnode->next = NULL;
newnode->data = x;

if (pq->front == NULL)
{
pq->tail = newnode;
pq->front = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = pq->tail->next;
}
}

void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));

QNode* next = pq->front->next;
free(pq->front);
pq->front = next;
if (pq->front == NULL)
{
pq->tail = NULL;
}
}


Datatype QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->front->data;
}

Datatype QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}

int QueueSize(Queue* pq)
{
assert(pq);
int count = 0;
QNode* cur = pq->front;
while (cur)
{
count++;
cur = cur->next;
}
return count;
}

bool QueueEmpty(Queue* pq)
{
assert(pq);
if (pq->front == NULL)
{
return true;
}
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

3.3 test.c

  对队列功能的测试。

#include"Queue.h"

void test()
{
Queue q;
QueueInit(&q);

QueuePush(&q, 1);//测试:入队列
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);

printf("%d\n",QueueFront(&q));//测试:获取队头元素

printf("%d\n", QueueSize(&q));//测试:统计元素个数

QueueDestroy(&q);
}

void test1()
{
Queue q;
QueueInit(&q);

QueuePush(&q, 1);//测试:入队列
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);

while (!QueueEmpty(&q))
{
Datatype x = QueueFront(&q);
printf("%d ", x);
QueuePop(&q);   //测试:出队列
}
printf("\n");

QueueDestroy(&q);
}
int main()
{
test();
//test1();
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

4.总结

  与栈差不多，一个是用数组实现的，一个是用链表实现的，一个是后进先出，一个先进先出。难度差距不大，重点依旧是放在做题方面感觉较好。
  那么队列的讲解就先告一段落了，如果发现文章哪里有问题可以在评论区提出来或者私信我嗷。接下来我会继续深入学习数据结构的其他知识，开启新的篇章，那么本期就到此结束，让我们下期再见！！觉得不错可以点个赞以示鼓励喔！！