c语言实现队列

---

前言

栈的特点是元素后进先出(Last In First Out)，而对应的还有一种数据结构，该结构的特点是先进先出(First In First Out)，即为队列。

一、队列的特征

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

二、队列的实现

1、队列的设计

队列可以使用数组或链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。因为队列需要尾插头删，当数组头删时，需要全部元素向前移动一位，时间复杂度为O(N)，而使用链表来实现队列的话，头删和尾插元素的时间复杂度都是O(1)。

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

typedef int QDataType;
//队列的结点设计
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

//创建一个Queue结构体变量，就相当于创建了一个队列，该结构体变量中存的有该队列的头结点地址，尾结点地址
//所以当有该结构体变量的地址时，可以通过该地址改变队列的头结点地址和尾结点地址，即改变head指针和tail指针。
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2、队列的初始化

因为队列中需要有一个头指针用来记录队头结点的地址，一个尾指针用来记录队尾结点的地址。所以又创建了一个Queue结构体，该结构体中有两个QNode*类型的成员变量，即Queue结构体中定义了两个结构体指针变量，一个用来存储队列的队头结点的地址，一个用来存储队尾结点的地址。
结构体Queue里面就只有两个QNode * 类型的结构体指针,所以当想创建一个队列时，创建一个Queue类型的结构体变量s就好了，此时Queue类型的结构体变量s的成员head和tail里面存的都是随机的地址，所以需要初始化，则需要调用QueueInit()函数，并且将结构体变量s的地址传进去，因为只有传s的地址进去，函数里面才可以根据s的地址找到s的成员head和tail，然后才能改变head和tail里面存储的随机地址的值。

如果传的是s的话，那么函数的形参就设置为Queue pq,那么在函数中会临时创建一个Queue类型的结构体变量pq，然后将s的值拷贝到pq中，此时在函数中修改pq.head和pq.tail时，外面s的head和tail并不会改变，所以要传s的地址。
队列初始化就是通过s的地址 0x 1234找到s，然后改变s的成员变量head和tail的值为0x 0000。

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

在这里我们可以再看一下单链表的设计。
单链表中结构体的定义为

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
1
2
3
4
5
6

然后单链表在使用时，需要先创建一个SLTNode * 类型的结构体指针，然后再将该结构体指针的地址传入函数中。而函数中的形参都设计了二级指针来接收这个SLTNode * 类型的结构体指针的地址。这样设计是因为当单链表为空时，此时单链表的头结点指针ps就指向NULL，而当要给单链表插入元素时，如果只将ps传进去，那么在函数中形参只需设计为一级指针SLTNode*即可，但是这样设计的话，并不会改变ps的值，改变的只是函数中临时创建的和ps类型一致的一个指针变量的值。此时主函数的ps的值依旧为NULL，所以要向改变ps的值，只能将ps的地址传进去，然后函数中形参设计为二级指针，在函数中可以通过解引用ps的地址来找到ps，然后将ps的值设置为单链表结点的地址。

可以看到在前面的单链表中，我们用到了二级指针，但是为什么队列没有用二级指针呢？因为队列不止要有一个指针变量存储队头结点的地址，还需要一个指针变量来存储队尾结点的地址，而改变时需要改变存储队头结点的地址的指针head的值，也需要改变存储队尾结点的地址的指针tail的值。而改变这两个指针的值，就需要函数设计两个二级指针的形参，所以我们为了方便直接设计了一个结构体Queue，结构体的成员包含两个指针变量。
单链表的话就只需改变一个指向单链表头结点的指针的值，所以可以直接使用二级指针来实现。

3、元素的入队和出队

队列中元素在入队时我们要判断此时队列是否为空，如果队列为空的话，我们就需要将队头指针和队尾指针都指向入队的这个元素。如果队列不为空的话，此时就在队尾指针指向的队尾结点后插入这个新元素即可。然后将队尾指针指向这个新插入的结点，以保证队尾指针指向的总是队列的队尾结点。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = newNode;
		pq->tail = newNode;
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

队列中元素在出队时需要先判断队列是否为空，如果队列为空，则出队失败。判断队列是否为空，就是判断队列的队头指针或队尾指针的值是否为NULL。

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	/*if (pq->head == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}*/

	return pq->head == NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

然后在队列中有元素要出队时，先判断队列是否为空，不为空才可以让队列中队头指针指向的结点出队，并且当队列中只有一个结点时，要进行出队的话，这一个结点出队之后，虽然head指针指向了NULL，但是tail指针还指向了这个被释放空间的原来的队尾结点，所以此时tail为野指针，这就需要我们再判断当队列中只有一个结点要出队时，该结点完成出队后，需要将head指针和tail指针都置为NULL，以恢复初始时队列为空的状态。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//当队列中只有一个结点时，该结点出队后队列就为空了
	//所以需要将队列的头指针和尾指针都置为NULL
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = NULL;
		//虽然按照下面的处理pq->head也会为NULL，
		//但tail指针还指向已经释放空间的最后一个结点的地址，所以此时tail为野指针，所以需要特别处理，将tail置为NULL
		pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4、返回队头的数据和队尾的数据

队列还需要提供返回队头结点数据和队尾结点数据的函数，返回队头结点数据就是先判断队列是否为空，不为空的话将队头指针所指向结点的数据返回即可。

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

返回队尾结点数据就是将队尾指针所指向结点的数据返回。

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

5、返回队列的长度

返回队列的长度可以通过遍历队列，每遍历一个结点，就将长度加1，最后将队列长度返回即可。不过这样求队列长度的时间复杂度为O(N)。

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* curr = pq->head;
	while (curr != NULL)
	{
		size++;
		curr = curr->next;
	}

	return size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

还可以在设计队列时，将Queue结构体中再加一个成员size，用来记录队列的长度，当有元素入队时pq->size++，当有元素出队时pq->size–，这样队列长度直接通过pq->size就可以得到。

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;  //用来记录队列长度
}Queue;
1
2
3
4
5
6

6、队列的销毁

队列的销毁就是先将队列的结点都一一销毁，然后将pq->head和pq->tail都指向NULL，此时队列中申请的结点占用的空间都被释放，而且队列回到了最初的状态。

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* curr = pq->head;
	while (curr)
	{
		QNode* next = curr->next;
		free(curr);
		curr = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
	//在这里面将pq置为空没用，因为pq只是临时创建的一个Queue*类型的结构体指针
	//pq里面存的是Queue结构体变量的地址，在函数里面将pq置为NULL对外面没有影响。
	//只是让pq指向不了这个结构体变量了，但是这个结构体变量还存在，
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

三、循环队列

环形队列我们也可以通过一个例题来体会。
循环链表

四、队列和栈综合练习

在学习了队列和栈之后，我们可以用队列来实现栈，或用栈来实现队列，下面的链接为这两个问题的具体实现，可以点击链接进行学习。
用栈实现队列
用队列实现栈