1.概念

百度百科中，这样解释

总结一下：队列（Queue）符合先进先出原则，只允许在⼀端进行插入数据操作，在另一端进行删除数据操作的特殊线性表

2.队列的定义

同栈一样，我们先思考一下底层使用数组来实现还是用链表。
入队列时：
数组可以直接入队列，没有太多浪费。
链表可以设计一个ptail指针，也直接插入即可。

出队列时：
数组头上出数据，效率会比较低。
链表直接头删，效率高。
综上，我们使用链表来实现。

//定义节点结构
typedef int QDataType;
typedef struct QueueNode {
	QDataType data;
	struct QueueNode* next;
}QueueNode;

除了结点以外，我们需要定义队列本身。
它由两个指针构成，一个指向链表的头结点，一个指向尾结点。

//定义队列
typedef struct Queue {
	QueueNode* phead;//队头
	QueueNode* ptail;//队尾
}Queue;

初始化队列：

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

3.入队列

//入队列
void QueuePush(Queue* pq, QDataType x) {
	assert(pq);
	//创建新节点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL) {
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//队列为空
	if (pq->phead == NULL) {
		pq->phead = pq->ptail = newnode;
	}
	else {
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
}

注意：必须时刻保持phead与ptail分别指向队头与队尾。

4.出队列

//出队列
void QueuePop(Queue* pq) {
	assert(!QueueEmpty(pq));
	//队列中只有一个节点
	if (pq->phead == pq->ptail) {
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else {
		Queue* next = pq->phead->next;//next指针存储新的头结点以便改变phead
		free(pq->phead);
		pq->phead = next;
	}
}

检查队列是否为空：

bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->phead == NULL;
}

4.队列的销毁

//销毁
void QueueDestroy(Queue* pq) {
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur) {
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
}

因为队列底层是由链表实现的，所以销毁也跟链表一样，只需将phead与ptail指针置空即可。

完
如发现错误，欢迎打在评论区。
主页还有更多优质内容OvO