数据结构初阶 队列

一. 队列的基本介绍

1. 基本概念

队列是基本数据结构的一种 它符合先进先出的原则

 我们来看图

大概就是这样子的一种情况 

我们想想看 应该用数组还是链表来实现这个结构方便一点呢

我想同学们心里现在肯定已经有了答案了

肯定不是数组

为什么呢？

因为我们如果用数组头作为队头的话 每次删数据就要往前移动很多组其他的数据

这里有同学肯定会有这样子的疑问？

不移动可不可行呢？

当然不可以 ！

队列这种数据结构已经规定死了就是头出 尾进

所以说我们使用链表来实现这个数据结构

2. 代码表示

typedef int QDateType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDateType date;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

仔细看

我们这里使用QueueNode来表示储存数据的一个个节点

使用Queue来表示两个指针 头和尾

可以看图理解快一点

二. 接口函数的实现 

1. 队列初始化

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

队列初始化实际上就是将队列的两个指针置空

我们来看看效果

这里没有传二级指针进去到底能不能将一级指针置空

成功将两个指针置空了

这是为什么呢？

因为我们的头和尾指针实际上是储存在一个结构体里面的

当我们将结构体的地址传进去的时候 结构体指针能够访问到结构体内部的内容（这两个指针）并且可以修改它们

2. 插入数据

这里插入数据我们要考虑两种情况

1.如果head和tail指针指向NULL，就需要将newnode赋给head和tail指针

2.head和tail不指向NULL，就将newnode的地址赋给tail->next，再将tail移到newnode即可

代码如下：

//队进
void QueuePush(Queue* pq, QDateType x)
{
	assert(pq);
	//开辟新节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	//赋值
	newnode->next = NULL;
	newnode->date = x;
	//判断是否为空
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	//个数要++
	pq->size++;
}

 看看效果怎么样

可以运行

3. 删除数据

这里我们要注意的是

由于队列结构的特殊性

我们在打印数据的时候必须要删除数据

所以我们先写删除数据的接口函数

代码表示如下

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head!=NULL);
	//只有一个节点
	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;//迭代
	}
	//个数要--
	pq->size--;
}

看看效果：

可以运行

4. 摧毁队列

直接看代码：

void QueueDestroy(Queue* pq)
{
	assert(pq);
	//两个结构体依次销毁 先销毁QNode
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//再置空Queue
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

注意：两个结构体要依次销毁，类似（套娃） 

我们来看看效果

5. 判断为空

这个也很简单和栈差不多

这里就直接给代码了

//判断为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}

6.返回大小

这个也很简单，因为我们在Queue结构体中已经定义过size了，我们直接返回就可以

直接看代码：

//大小
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

7. 返回头数据

这个很简单 返回head的值就可以了

注意断言的使用

//对头
QDateType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->date;
}

8.返回尾数据

一样的简单

也要注意断言的使用

//队尾
QDateType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->date;
}

以上便是本文所有内容了，如有错误请各位大佬不吝赐教，感谢留言