队列的简单实现

一、什么是队列

首先我们既然想要实现队列就得明白什么是队列；
队列： 只允许在一端插入数据，在另一端删除数据的特殊线性表；队列具有先进先出的特点；其中插入数据的操作叫做入队列，删除数据的操作叫做出队列

二、队列的分类

分类：
1、链式结构；
2、顺序结构；

这一点上始于栈是一样的，但是我们知道，栈我们通常使用顺序表实现；而对于队列来说我们通常使用链式结构实现；
why?

就说假设我们利用顺序结构实现队列；顺序表的头作为队头，尾巴作为队尾；
那么我们的入队操作是不是就相当于尾插，这一点没问题，效率很高，时间复杂度为O（1），同理我们还有进行出队操作啊，也就是说相当于顺序表的头删，我们通过前面的学习可以知道，顺序表尾插尾删效率很高，但是对于头插、头删效率就表现的不尽人意，因为头删的话需要我们挪动数据，时间复杂度就是O（N），不是很高效；当然如果你想以顺序表的尾作为队列的头的话，那么出队 操作时间复杂度还是O（N），不是很理想；
这也是我们不打算利用顺序表实现队列的一个重要原因！！！
那么为什么要选择利用链式结构？
假设我们是利用单链表的方实现的，我们都知道单链表是不能回走的，那么我们就肯定不会选择单链表的尾作为队列的头，因为这样的话，那么队列的出队操作时间复杂度就是O（N）了，划不来！！！；
为此我们肯定会首选将单链表的尾巴最为队列的尾巴，那吗这时候出队操作时间复杂度不就是O（1）；那么这时候就会右小伙伴会问了，那么我入队的操作时间复杂度不就是O（N）嘛，因为我单链表需要找尾才能就行插入，那不和顺序表有啥子区别！！这不就来了，队列的数据结构设计：
我们可以定义一个头指针和尾指针分别来记录队列的头和尾啊，这么一来我不就天然的知道尾指针，就不用去找尾巴了，入队和出队的时间复杂度也是更加方便了，同时空间上也得到了更加充分的利用，但是如果用这样的方法去定义顺序表的话，那么我的头指针尾指针都在变，那么势必会照成我顺序表的起始指针会丢失，那么我到时候释放的时候就找不到整块顺序表的起始指针了，就会照成内存泄漏，这因小失大的操作我们自然不会去选择，为此我们才会钟爱于利用链式结构去实现队列；

三、队列的数据结构

上面我们已经阐述了为什么要实现链式结构队列，同时也说明了要想让入队和出队的时间复杂度达到O（1）；
就必须定义一个头指针和尾指针来记录队列的队头和队尾，为此我们给出以下数据结构：

由于我们需要同时记录两个指针的变化，为此我们需要将两个指针定义在结构体里面；
相当于我们只要知道了这两个指针就能操作整个队列；

四、队列的基本操作

1、初始化队列

队列为空的条件：
frontNULL；//头指针
rearNULL；//尾指针
为此刚开始时队列一定为空，我们就像这样初始化了：

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

2、销毁队列

初始话和销毁是伴生关系，为此我们将队列的销毁也一同处理了：

//销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)//这里要注意结束条件不是cur==q->rear;如果是这样的话就会照成rear节点没有释放，需要单独处理，很是麻烦，这样代码就变得很挫了；
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->front = NULL;
	q->rear = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3、入队

刚开始我们的队列是空的，那么rearfrontNewNode//新节点地址；
当我们队列不为空了，那么就需要连接在rear的后面了；
为此这里有两种情况，我们分开处理就好了：

//开辟新节点
static QNode* BuyQNode(QDataType x)
{
	QNode* NewNode = (QNode*)malloc(sizeof(QNode));
	if (!NewNode)
	{
		printf("malloc fail!\n");
		exit(EXIT_FAILURE);
	}
	NewNode->next = NULL;
	NewNode->val = x;
	return NewNode;
}
//入队列
void QueuePush(Queue* q,QDataType x)
{
	assert(q);
	QNode* NewNode = BuyQNode(x);
	if (q->rear == NULL)
	{
		q->front = q->rear = NewNode;
	}
	else
	{
		q->rear->next = NewNode;
		q->rear = NewNode;
	}
}
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

4、出队

入队讲完了，咱们接着讲讲出队，这出队操作啊也就是单链表的头删：
只需要释放点front所指的位置，并且更新front指针就行了，但是这会照成一个问题，要是我一直出队一直出，那么最后肯定会删光对吧：

正如上面这幅图（只剩最后一个节点），要是我还接着出队列，那么队列的是不是就为空啊：

最后是不是就会造成这副模样，可是我们有没有发现我们出队的时候一直是改变的头指针唉，像这样删的话，最后我的尾指针会指向一个已经内释放的节点，有野指针的嫌疑，同时我们对于队列判空的条件（front==NULL&&rear==NULL）就不在适用了，这造成的一一系列连锁反应，就会让我们优雅的程序出现致命的错误！！！，为此向上述情况我们需要特殊处理，当front删完一个节点过后我们都要判断一下front等不等于NULL，如果是，那说明刚才删除的是最后一个节点，为了不照成野指针的麻烦，我们需要将rear也置空！！！；如果不是，则说明刚才删除的不是最后一个节点，我们无需对rear进行过多处理；
为此我们的出队代码如下：

//出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(QueueEmpty(q)==false);//判空
	QNode* next = q->front->next;
	free(q->front);
	q->front = next;
	if (q->front == NULL)//删除节点过后front指针指向NULL，表示无节点可删
		q->rear = q->front;
}
1
2
3
4
5
6
7
8
9
10
11

5、队列判空

//队列判空
bool QueueEmpty(Queue* q)
{
	assert(q);
	return (q->front == q->rear && q->front == NULL);
}
1
2
3
4
5
6

6、获取队头元素

我们知道头指针，只需判断一下队列为不为空（因为我们要有数据可取才行！！！），就可以取数据了；

//获取队头元素
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->val;
}
1
2
3
4
5
6
7

7、获取队尾元素

这不我们定义尾指针的好处不就来了！！要是我们没有这个尾指针，就得自己找尾，时间复杂度难免会O（N），但是现在简直方便的变态！！！时间复杂度O（1）！！！

//获取队尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->val;
}
1
2
3
4
5
6
7

8、获取队列元素

常见错误：
直接用尾指针减去头指针；
注意这不是顺序表，用尾指针减去头指针不是元素个数，是个随机值，指针不是一定是连续的，这里的节点是一个一个开辟的，其地址自然也是随机的，这么多数据的地址不可能全部都是连在一起的，为此尾指针减去头指针的做法是不可取的！！！
那么比较常见的方法：
1、在结构里面里面直接价格成员size，用来记录有效元素个数；\这样求队列元素时间复杂度:O(1);
2、不用定义成员变量，直接遍历整个链表，只不过这个时间复杂度就有点大了，时间复杂度:O(N);
由于我们刚开始的时候没有定义size这个成员变量，我们这里就才有遍历的方法取求解了:

//获取队列元素个数
size_t QueueSize(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	size_t count = 0;
	while (cur)
	{
		QNode* next = cur->next;
		count++;
		cur = next;
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

总结

头文件

#pragma once
#include
#include
#include
#include
// 链式结构：表示队列 
typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType val;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
}Queue;
 
//初始化队列
void QueueInit(Queue*q);
//销毁队列
void QueueDestroy(Queue*q);
//入队列
void QueuePush(Queue*q,QDataType x);
//出队列
void QueuePop(Queue*q);
//获取队头元素
QDataType QueueFront(Queue*q);
//获取队尾元素
QDataType QueueBack(Queue* q);
//获取队列元素个数
size_t QueueSize(Queue*q);
//队列判空
bool QueueEmpty(Queue*q);
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

基本操作

#include"Queue.h"

//初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
}
//销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->front = NULL;
	q->rear = NULL;
}

//开辟新节点
static QNode* BuyQNode(QDataType x)
{
	QNode* NewNode = (QNode*)malloc(sizeof(QNode));
	if (!NewNode)
	{
		printf("malloc fail!\n");
		exit(EXIT_FAILURE);
	}
	NewNode->next = NULL;
	NewNode->val = x;
	return NewNode;
}
//入队列
void QueuePush(Queue* q,QDataType x)
{
	assert(q);
	QNode* NewNode = BuyQNode(x);
	if (q->rear == NULL)
	{
		q->front = q->rear = NewNode;
	}
	else
	{
		q->rear->next = NewNode;
		q->rear = NewNode;
	}
}
//出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(QueueEmpty(q)==false);//判空
	QNode* next = q->front->next;
	free(q->front);
	q->front = next;
	if (q->front == NULL)//删除节点过后front指针指向NULL，表示无节点可删
		q->rear = q->front;
}
//队列判空
bool QueueEmpty(Queue* q)
{
	assert(q);
	return (q->front == q->rear && q->front == NULL);
}
//获取队头元素
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->val;
}
//获取队尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->val;
}
//获取队列元素个数
size_t QueueSize(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	size_t count = 0;
	while (cur)
	{
		QNode* next = cur->next;
		count++;
		cur = next;
	}
	return count;
}
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