数据结构之实现队列

前言

之前谈到了栈的实现，现在来说说另一种数据结构——队列的实现。队列这种结构也是线性的，本文将会对队列的实现进行简单讲解，为以后学习其他数据结构打下牢固的基础。

---

1.队列的相关介绍

1.队列的定义

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

队列和栈这种结构有点相反，栈只能再一端入数据和出数据，队列的一端入数据，另一端出数据。队列可以形象的理解为排队做核酸。队头的人做完核酸就走了，相当于队列出数据，后面来做核酸的人，接着队尾按次序排队就相当于队列入数据。

---

2.队列的实现方式

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

队列因为一端出数据，另一端进数据。如果采用数组来实现肯定是代价更大一点的，因为在出数据以后需要挪动数据，更新队头的元素，如果采用链表来实现，就不用担心这个问题了。插入数据和删除数据只需要更新头节点和尾节点即可。

---

2.队列具体实现

1.队列声明定义

刚才提到了使用链表来实现队列比较好，队列采用链表实现的话，那么队列的每个数据是存储在节点中的，那么就定义创建队列节点结构体，有了节点，相当于队列的身体创建好了，那么怎么维护这个队列呢？我们在创建队列结构体，队列结构体来表示一个完整的队列，用于维护整个队列。

代码示例

typedef int QDataType;
//定义队列节点
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;
//定义队列
typedef struct Queue
{
	QueueNode* head;//维护队头
	QueueNode* tail;//维护队尾
	int sz;//记录队列元素个数
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

队列节点的结构和普通单链表的节点一样，队列结构体中成员有头节点和尾节点分别用来维护队列头和队列尾。同时，还有一个整型变量来用来记录队列中数据个数。为啥不像链表那样直接只定义节点，为啥还要单独创建一个队列结构体呢？因为队列是需要访问队尾和队头元素的而且队头和队尾是需要更新的，如果只是单单定义节点，在访问队尾和更新队尾时，是要进行遍历的，这显得不是和方便。虽然双向循环链表可以快速找到头和尾，但是也略显麻烦了，如果是定义了队列结构，用结构中的成员来维护队尾队头，这个队列就被很好的管理起来了，而且很方便，也不是太繁琐。

---

2.队列的接口

void QueueInit(Queue* q);//初始化队列
void QueuePush(Queue* q, QDataType data);//元素队尾入列
void QueuePop(Queue* q);//元素对头出列
QDataType QueueFront(Queue* q);//获取队列头部元素
QDataType QueueBack(Queue* q);//获取队列队列尾元素
int QueueSize(Queue* q);//获取队列元素个数
int QueueEmpty(Queue* q);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
void QueueDestroy(Queue* q);// 销毁队列

1
2
3
4
5
6
7
8
9

这些接口和栈的接口其实都是差不多的，多了一个获取队头元素的接口，栈只有获取栈顶元素的接口。*

---

1.初始化接口

void QueueInit(Queue* q)//初始化队列
{
	assert(q);
	q->head = NULL;
	q->tail = NULL;
	q->sz = 0;
	return;
}
1
2
3
4
5
6
7
8

初始化的时候队头和队尾都是空，sz也位空。

---

2.数据的插入和删除

数据的插入就从队尾开始插入，用尾插处理就好了，数据的删除就是从队头出了数据后要将原队列头节点给删除了，并且更新队头。

Push代码示例

void QueuePush(Queue* q, QDataType data)//队尾入列
{
	    assert(q);
		QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
		if (newnode==NULL)
		{
			perror("QueuePush:");
			exit(-1);
		}
		newnode->data = data;
		newnode->next = NULL;
		if (q->head == NULL)
		{
			q->head = q->tail = newnode;//只有一个队列节点时，头尾都是自己
			
		}
		else  
		{   
			q->tail->next = newnode;
			q->tail = newnode;
			
		}
		q->sz++;
		return;
}
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

队尾插入就是尾插，当头的空的时候单独处理一下就好了。因为只有这个接口需要malloc节点，所以就没有单独封装一个接口来实现节点空间的申请。每次增加一个节点时，sz自增计数。

---

Pop代码示例

void QueuePop(Queue* q)//队头元素出列
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->head->next == NULL)//队列只有一个节点
	{   free(q->head);
		q->head = NULL;
		q->tail=NULL;
	}
	else
	{
		QueueNode* del = q->head;
		q->head = q->head->next;
		free(del);
	}
	q->sz--;
	return;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

删除数据就是释放队列的原头节点，在释放之前应该先将头节点进行更新，因为队列是从队头开始出数据，所以只用队头节点进行释放。但是要注意一点当队列的节点只有一个时，应该单独处理一下，因为如果不处理头节点指向的空间已经被free释放掉了，head->next肯定会访问已经释放的空间，这样就会引发程序崩溃。单独处理时我们直接将这个节点释放后，队头和队尾给置为空就可以了。同时每次删除以后sz需要自减一下。

---

3.获取队头元素和队尾元素

队头和队尾的元素的获取就很简单了，队列结构中有头指针和尾指针来维护队头和队尾。这样就可以直接访问队头节点和队尾节点了。

队头元素的获取 代码示例

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

直接返回头队列中头节点指向的data值就好了，但是要注意当队列为空的时候就不能出数据了，需要进行断言，关于这个判空函数下面将会介绍。

---

队列尾元素的获取 代码示例

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

这个和获取队头元素基本上一样，将头指针改成尾指针就好了。这也说明了我们将队列的结构设计成这样的好处，访问头尾位置的时候非常方便。

---

4.获取队列元素个数和队列判空以及队列

获取元素个数 代码示例

int QueueSize(Queue* q)//获取队列元素个数
{   
	assert(q);
	return q->sz;
}
1
2
3
4
5

这个直接返回sz即可，sz就是表示的队列元素个数。

---

队列判空 代码示例

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

如果sz为0就是队列为空，这个用布尔值判断比较好，之前也说过C语言使用布尔值引入相应的头文件即可。因为我们是通过sz的值判断队列是否为空，使所以在Pop单独处理一个节点时，尾指针不用置为空也可以。不过为了养成良好的代码习惯，最好还是置为空。

---

销毁队列 代码判空

这个就是还是挨个遍历free释放即可。

队列销毁 代码示例

void QueueDestroy(Queue* q)// 销毁队列
{
	assert(q);
	QueueNode* cur = q->head;
	while (cur)
	{
		QueueNode* Next = cur->next;
		free(cur);
		cur = Next;
	}
	q->head = NULL;
	q->tail = NULL;
	q->sz = 0;
	return;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这个实现起来也是比较简单的

---

3.总结

在我们学习实现链表后，这个队列和栈的实现总体来说没那么难，很多接口的实现有都有些相似之处。

学习是一个积累过程，编程是需要不断练习的，熟能生巧！