
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;//队列数据
	struct QueueNode* next;//指向下一个队列块
}QNode;
typedef struct Queue
{
	QNode* front;//队列头
	QNode* rear;//队列尾
	int size;//队列长度
}Queue;

五.链式队列功能的实现

5.1 初始化队列

初始化队列，就是给队列的每个成员赋初值。

由于front和rear是指针，因此我们初始化为空。

由于size是整型，因此我们初始化为0.


void QueueInit(Queue* q)
{
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}

5.2 判断队列是否为空

判断一个队列是否为0的方式有很多，

可以通过判断size是否为0判断；

也可以通过队列头和队列尾的指针来判断。

这里我们通过size是否等于0来判断。


bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->size;
}

5.3 获取队头元素

获取队列的头元素，只要保证队列存在并且不为空即可。

队列的头元素就是队列头指针的data，我们访问即可。


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

5.4 获取队尾元素

队列的尾部数据的获取，和获取队头数据类似，直接返回队尾指针即可。


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

5.5获取队列长度

直接返回size即可。


//获取队列长度
int QueueSize(Queue* q)
{
    assert(q);
	return q->size;
}

5.6 入队

入队列，首先我们应动态申请一个链表结点。

之后我们就可以自行初始化链表结点的值了。

再然后我们要分为两种情况了，

第一种情况是链表没有结点，这时我们的结点入队列对队头和队尾都会产生影响；

第二种情况是链表中已有结点，这时我们的结点入队列只会对队尾产生影响。

因此我们在这里需要通过分支结构处理这个问题。

由于这两种情况都需要处理size，为了防止代码冗长，我们将size的自增语句写在分支结构之外。


void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	//初始化新结点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	//队列为空
	if (q->front == q->rear == NULL)
	{
		//更新信息
		q->front = q->rear = newnode;
		//q->size++;
	}
	else
	{
		//更新信息
		q->rear->next = newnode;
		q->rear = newnode;
		//q->size++;
	}
	q->size++;
}

5.7出队

在已经讲解了入队列之后，我们再讲解一下出队列。

出队列首先要确保队列中已有队列结点，否则将无队列结点可出。

出队列也分为两种情况，

第一种情况是队列中只有一个结点，我们需要释放掉这个结点并将队列的头指针和尾指针置空；

第二种情况是队列中有好多个结点，这时我们释放掉队列头的结点之后，更新队头即可。


//出队
//1.考虑情况要全面
//2.在更新队列时，要将数据结构中受到影响的成员全部更新
//3.如果分不清谁受到了影响，就逐个排查。
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->front);
	if (q->size == 1)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	else
	{
		QNode* ret = q->front->next;
		free(q->front);
		q->front = ret;
	}
	q->size--;
}

在有多个结点的情况下，我们在出队时，需要注意的是需要定义一个指针保存队头的下一个结点，否则在更新时则无从下手。

5.8 打印队列元素

与链表的打印方式一样，打印即可。


void QueuePrint(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	printf("队头->");
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("队尾");
}

5.9 销毁队列

与链表的销毁方法一样，销毁即可。


void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* ret = q->front;
	while (ret)
	{
		QNode* next = ret->next;
		free(ret);
		ret = next;
	}
	q->front = q->rear = NULL;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/626141