数据结构之“队列”

1.队列的概念

1.1 栈也是一种特殊的线性表。

1.2 栈和队列的区别：

（1）几端
在栈中，出数据和入数据都是在固定的一端（栈顶）。而在队列中(两端)，出数据在一端，入数据在另一端 。

（2）先后
栈：先进后出
队列：先进先出 （意思是先进来的元素，从它开始出去）

1.3 入和出

入队列：插入数据----->这一端称为队尾
出队列：删除数据----->这一端称为队头

两端都需要操作，所以两头都是空的。

1.4 底层

栈的底层是数组，队列的底层是什么呢？（单链表）

2. 队列的操作

2.1 队列的定义

之前学习的其余类型，只需要一个结构体就可以定义好。但是队列需要两个结构体嵌套使用才可以。

定义队列需要一个结构体（里面是头phead和尾ptail），队列里面的数据是一个一个的结点类型（所以需要有结点类型的结构:里面保存了数据+下一个结点地址）。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int Datatype;

//定义队列结点的结构
typedef struct QueueNode
{
	Datatype data;
	struct QueueNode* next;
}QueueNode;
//定义队列的结构
typedef struct Queue
{
	struct QueueNode* phead;  //对头删(出)
	struct QueueNode* ptail;  //队尾插(入)
}Queue;

2.2 队列的初始化Init

初始化时，phead和ptail都置为空。

2.3 入队列

如果队列为空，那么新插入的结点既是phead，又是ptail。
如果队列不为空，新插入的结点在ptail之后即可。

void QueuePush(Queue* pq, Datatype x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	//记得给新结点初始化（赋值）
	newnode->data = x;
	newnode->next = NULL;
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	if (pq->phead == NULL) //队列为空
	{
		pq->phead = pq->ptail = newnode;
	}
	else if (pq->phead != NULL) //队列不为空
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
}

2.4 出队列

出队列，想要把队头的那个数据出掉，需要先把第二个数据保存下来（否则等一会找不到新的队头了），存下之后再将phead释放掉。

在出队列时要考虑队列是否为空。
队列为空：不能出数据。
队列不为空：ok

还需要判断是否只剩下一个结点：只剩下一个指针，头结点指向下一个，即NULL。那尾结点怎么办，将会成为野指针。x

如果只有一个结点，将头尾释放即可。

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead&& pq->ptail == NULL;
}
//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	//只有一个结点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		//队列不为空且结点大于1个，继续出队列
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead->data = pq->phead->next = NULL;
		pq->phead = next;//不要忘记让phead等于下一个结点
	}
}

2.5 取队头数据

对头数据是QueueNode里的data，类型是Datatype。所以这个函数的返回类型是Datatype。

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

2.6 取队尾数据

Datatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

2.7 获取队列有效元素的个数

通过循环来求得个数–可以。
还可以在队列的结构中加入:int size;在入队列时size++，出队列时size–。这样子最后得到的size就是元素个数了。

typedef struct Queue
{
	struct QueueNode* phead;
	struct QueueNode* ptail;
	int size;  //记录个数
}Queue;

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

2.8 销毁队列