【数据结构】队列详解

1、什么是队列

1.1队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列遵循先进先出FIFO（First In First Out）的原则。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。

1.2生活中的队列

现实生活中，我们无论是去银行或是食堂都会排队，符合队列的先进先出原则。

2、队列的实现

2.1队列的结构

从结构角度看，队列既可以使用顺序表又可以使用单链表实现。
但是从实现角度观察，我们最优选择是单链表。

原因：
1.单链表的头删效率为O(1)比顺序表效率高;
2.单链表可以按需给空间。

那么，之前学习的带头双向循环链表用在队列是不是更优了？
会有效率及其他方面的提升，但是有些大材小用，提升的也不是很明显。这里我们只需要记住队头，队尾以及队列长度即可使用单链表完成。

2.2创建结构体

正如上面所说，我们只需要再创建一个结构体记录需要的值即可解决问题。

//创建结构体
typedef int QDataType;
//链式结构：表示队列
typedef struct QueueNode
{
	QDataType data;
	struct QDataNode* next;
}QNode;

//队列的结构
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.3队列接口

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队（尾插）
void QueuePush(Queue* pq, QDataType x);
//出队（头删）
void QueuePop(Queue* pq);
//取队头队尾数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//获取队列中有效元素个数
int QueueSize(Queue* pq);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.4初始化队列

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	//置空队头队尾
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
1
2
3
4
5
6
7
8
9
10

2.5队尾入队列

//入队列
//放入结构体中，指针属于结构体（改变的本身就是结构体指针），所以可以改变指针而不需要二级指针或者返回值
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->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode; //队尾指向新节点，新节点入队
		pq->tail = newnode;       //改变队尾指针指向
	}
	pq->size++; //队列长度加1
}
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

2.6队头出队列

//出队列
void QueuePop(Queue* pq)
{
    //断言判断队列是否具有出数据的资格
	assert(pq);
	assert(!QueueEmpty(pq));
	
	//若队列仅剩一个结点
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;     //记录队头结点，之后将其释放完成删除
		pq->head = pq->head->next; //改变队头指针指向
		free(del);
	}

	pq->size--; //队列长度减1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.7取队头数据

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);	
	assert(!QueueEmpty(pq));
	//队列不为空时，返回队头指针指向节点数据
	return pq->head->data;
}
1
2
3
4
5
6
7
8

2.8取队尾数据

//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//队列不为空时，返回队尾指针指向节点数据
	return pq->tail->data;
}

1
2
3
4
5
6
7
8
9

2.9队列判空

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	//通过队头队尾检测
	return pq->head == NULL && pq->tail == NULL;
}
1
2
3
4
5
6
7

2.10获取队列有效元素个数

//获取队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	 
	//遍历队列
	//int size = 0;
	//QNode* cur = pq->head;
	//while (cur)
	//{
	//	cur = cur->next;
	//	++size;
	//}
	//return size;
	//直接返回结构体内记录的队列长度
	return pq->size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.11销毁队列

由于队列所用的空间都是向内存申请的，所以需要我们使用完后进行释放（释放过程可以由临时指针代劳）

//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	//遍历链表，逐个释放
	while (cur != NULL) 
	{
		QNode* del = cur;
		cur = cur->next;

		free(del);
		del = NULL;//局部变量无需置空
	}
	//置空
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20