队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头
在这里插入图片描述

队列的链式存储实现

采用单链表来实现队列的链式结构，设置一个头指针和尾指针。通常将队头指针和队尾指针封装在一个结构体中，并将该结构体类型重新命名为链队列类型。

typedef int QDataType;
typedef struct QListNode
{
	struct QListNode *next;//数据域
	QDataType data;//指针域
}QNode;

typedef struct Queue
{
	QNode *phead;//头指针
	QNode *ptail;//尾指针
}Queue;

在这里插入图片描述

队列初始化

初始化比较简单

// 初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->front = NULL;
	pq->rear = NULL;

}

重点：入队列

在这里插入图片描述
入队列就是尾插，需要注意空队列。

// 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//开辟新结点
	QNode *newnode = (QNode *)malloc(sizeof(QNode));
	//判断是否开辟成功
	if (newnode == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//队列为空时
	if (pq->front == NULL)
	{
		pq->front = newnode;
		pq->rear = newnode;
	}
	else
	{
		pq->rear->next = newnode;
		pq->rear = newnode;
	}
}

打个断点调试
在这里插入图片描述
1，2，3就已经入队了。

重点：出队列

头删，保存下一个结点，free当前结点
在这里插入图片描述
错误的写法

从调试看出rear还在指向结点，虽然3已经free，但rear还在指向那里的空间。这个坑要单独处理。

void QueuePop(Queue* pq)
{
	assert(pq);
	//队列为空时就不能继续出了
	assert(!QueueEmpty(pq));

	if (pq->front->next == NULL)
	{
		free(pq->front);
		pq->front = pq->rear = NULL;
	}
	else
	{
		Queue* next = pq->front->next;
		free(pq->front);
		pq->front = next;
	}
}

获取队列头部元素

注意空队列

// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->front->data;
}

获取队列队尾元素

跟上面的一样

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

检测队列是否为空

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->front == NULL && pq->rear == NULL;
}

队列的销毁

// 销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode *cur = pq->front;
	while (cur)
	{
		Queue *next = cur->next;
		free(cur);
		cur = next;
	}
	pq->front = pq->rear = NULL;
}