队列的实现

 文章目录

前言

之前学习了栈，栈是后进先出的形式，队列和其不同使用的是先进先出（FIFO），所以我们应该使用适合尾插和头删的，这时我们就可以使用链表，我们创建的链表要多创建一个保存头指针和尾指针方便进行尾插。

一、队列是什么？

队列是在一端进行输入操作，一段删除操作的线性结构，有着先进入的就先删除的特性，也就为先进先出（FIFO）。

二、使用步骤

1.创建类型

创建一个链表的数据结构，再创建一个结构体用来包含链表的头和尾，以及队列存放了多少个数据。

代码如下（示例）：

typedef int typedata;
typedef struct Qnode
{
	typedata data;
	struct Qnode *next;
}Qnode;
typedef struct Queue
{
	Qnode* last;
	Qnode* head;
	typedata size;
}Queue;

2.初始化队列

初始化队列，将队列的前后指针都指向NULL，将大小赋值为0。

代码如下（示例）：

Queue* InitQueue(Queue* ps)
{
	assert(ps);
	ps->head = ps->last = NULL;
	ps->size = 0;
}

3.插入队列

创建一个链表Qnode的指针对其进行开辟空间的操作，将next赋值为NULL，分情况讨论，如果size为0或头节点为NULL说明其中没有数据，就直接将头节点和尾节点赋值尾新开辟的空间。如果有数据，直接将尾节点的下一个赋值为新开辟的空间，再将尾节点改变使其指向最后，size++。

代码如下（示例）：

void Queuepush(Queue* ps, typedata data)
{
	assert(ps);
	Qnode* node = (Qnode*)malloc(sizeof(Qnode));
	if (node == NULL)
	{
		perror("malloc fail");
		return;
	}
	node->data = data;
	node->next = NULL;
	if (ps->head == NULL)
	{
		ps->head = ps->last = node;
	}
	else
	{
		ps->last->next = node;
		ps->last = node;
	}
	ps->size++;
}

4.删除队列 

如果删除的化要看还有没有数据，如果size为0就说明无数据可减了，如果有只有一个数据的话直接将头节点释放将头尾都置为NULL即可，如果有多个就先存储头节点的下一个，将原来的头节点释放掉，头节点赋值存储的下一个完成头删。

代码如下（示例）：

void Queuepop(Queue* ps)
{
	assert(ps);
	assert(ps->head);
	if (ps->head->next == NULL)
	{
		free(ps->head);
		ps->head = ps->last = NULL;
	}
	else
	{
		Qnode* node = ps->head;
		ps->head = ps->head->next;
		free(node);
		node = NULL;
	}
	ps->size--;
}

5.判断队列是否为空

判断队列是否为空，可以看size是否为0，如果为0说明为空返回true，如果不为0说明不为空，返回false。

代码如下（示例）：

bool Empty(Queue* ps)
{
	assert(ps);
	return ps->size == 0;
}

6.队列队头数据 

直接将头节点的数据返回即可。

代码如下（示例）：

typedata FrontQueue(Queue* ps)
{
	assert(ps);
	return ps->head->data;
}

7.队列队尾数据 

直接将尾节点的数据返回即可。

代码如下（示例）：

typedata BackQueue(Queue* ps)
{
	assert(ps);
	return ps->last->data;
}

8.队列数据的个数

只需返回结构体中size就完成操作。

代码如下（示例）：

int Queuesize(Queue* ps)
{
	return ps->size;
}

9.销毁队列 

销毁队列先保存队列头节点的地址，使用循环遍历，如果当它尾NULL就为结束条件。最后记得将头节点和尾节点的地址都置为NULL，size置为0。

代码如下（示例）：

void Destroy(Queue* ps)
{
	assert(ps);
	Qnode* node = ps->head;
	while (node)
	{
		Qnode* next = node->next;
		free(node);
		node = next;
	}
	ps->head = ps->last = NULL;
	ps->size = 0;
}

10.实现案例 

总结

我们在实现队列的时候，要注意头节点和尾节点的使用，还记得判读在不同的情况下，应该使用何种方向进行相应的操作，希望这篇文章对您有所帮助。