本篇博客带来栈的好兄弟——队列。

目录

一、 队列的概念与结构

二、 队列的框架定义

三、 队列的功能实现

3.1 队列的初始化

3.2 队列的销毁

3.3 队列插入数据

3.4 队列删除数据

3.5 队列的判空

3.6 取头部数据

3.7 取尾部数据

3.8 队列的大小

四、功能测试

五、总结

---

一、 队列的概念与结构

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

 

二、 队列的框架定义

队列也可以使用数组或链表实现，使用链表的结构实现更有一些，因为如果使用数组的结构，出队列在数组0下标处上出数据，效率会比较低。

接下来我们来看看此次要实现的队列基本操作。

#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>
 
 
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;
 
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
 
void QueueInit(Queue* pq);                //队列的初始化
void QueueDestroy(Queue* pq);             //队列的销毁
void QueuePush(Queue* pq, QDataType x);   //插入数据
void QueuePop(Queue* pq);                 //删除数据
bool QueueEmpty(Queue* pq);               //队列的判空
QDataType QueueFront(Queue* pq);          //队列头部数据
QDataType QueueBck(Queue* pq);            //队列尾部数据
int QueueSize(Queue* pq);                 //队列的大小

注意：

栈使用的是数组，数组是可以直接访问的。而如果我们使用链表实现队列，则要设置一个head和tail指针表示队头和对尾，其中head和tail都为普通的单链表节点结构，所以它们要设置next指针域和data数据域，这样才能实现队列的特性。

三、 队列的功能实现

3.1 队列的初始化

和之前实现的单链表初始化差不多，这里就不过多讲解了。

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

3.2 队列的销毁

因为是链表的形式，所以我们释放空间不能像数组一样直接整段释放，要使用while将每个节点释放掉。

void QueueDestroy(Queue* pq)
{
	assert(pq);
 
	QNode* Dest = pq->head;
	while (Dest)
	{
		QNode* temp = Dest->next;
		free(Dest);
		Dest = temp;
	}
	pq->head = pq->tail = NULL;
}

3.3 队列插入数据

队列插入数据的步骤：

①将newnode链接到head节点的next；②将newnode设置为新的tail节点。

这里我们注意，在我们初始化的时候，我们将head和tail节点都置为了NULL，所以在我们第一次插入数据的时候要做一次判断，如果(head==NULL)，则要将tail和head都设置为newnode节点，这样才能保证链表正常链接起来。

注释写的很详细，大家可以看看。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建一个节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//判断pq是不是一个空结点
	//如果是 则将newnode置为当前队列的第一个结点
	//如果不是  则将newnode链接到pq的下一个位置
	if (pq->tail == NULL)
	{   //两个节点都指向newnode 表示此时队列中就一个元素
		pq->head = pq->tail = newnode;
	}
	else 
	{
		//1.将newnode链接到tail的后面
		pq->tail->next = newnode;
		//2.将newnode置换为新的tail
		pq->tail = newnode;
	}
}

3.4 队列删除数据

上文就提到过，队列是先进先出，所以我们删除数据要从队头删除。

队列删除数据的步骤：

①保存head下一个节点的位置

②释放head节点

③将保存的节点设置为新的head。

注意：

        ①要先判断队列不能为空

        ②如果队列中仅剩一个节点的时候，我们按以上的步骤释放了head节点并将其置为了NULL，但是我们没有处理tail节点，此时tail节点就成了经典的野指针。所以我们要额外判断当节点仅剩一个的时候，即(pq->head->next==NULL),我们要释放head结点，并将其head和tail都置为NULL。

代码如下：

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//额外判断一下，解决如果仅剩一个结点了，pop的话导致tail为野指针
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

3.5 队列的判空

队列如何判空呢？

此时我们只用判断head是否为NULL即可，即(head->next==NULL);

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

3.6 取头部数据

注意： 这些取数据和删除数据的操作都要先判断队列是否为空。

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

3.7 取尾部数据

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

3.8 队列的大小

链表不数组可以通过计算下标来算长度，所以这里我们只能使用循环计算直到cur==NULL；

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

四、功能测试

还是和栈一样的测试方式来检查我们队列实现是否成功。

同样，队列是不能遍历的，所以我们也要采用取出一个队列头部数据，然后将头部数据弹出，直到队列为空。

 

五、总结

相比于栈，队列的性质与栈的截然不同，同样我们这里使用的链式结构与数组的形式也不同。

我感觉实现队列唯一的难点可能就是其中两层结构体的灵活使用吧，其他的与栈的实现很类似，大家可以把队列的框架定义看看，然后自己实现一下，这对于掌握结构体很有帮助，对队列的认识也会加深。

好了，本篇博客到此就结束了，接下来做几道题目之后就会开始树的学习，一段全新的征程，大家一起学习数据结构，一起加油。