目录

一、队列的基本概念

二、队列的两种实现方式

三、链式队列结构设计

四、队列初始化

问题小加 

为什么队列不需要头节点（哨兵节点）？

五、入队操作（QueuePush）

六、出队操作（QueuePop）

八、常见错误总结

九、时间复杂度分析

十、总结

十一，全代码

Queue.h

Queue.c

---

一、队列的基本概念

队列（Queue）是一种先进先出（FIFO）的线性数据结构。

特点：
只能在队尾插入
只能在队头删除

画一个简单结构：

入队 → → → → → → 出队

front                            rear
 ↓                                   ↓
[10] → [20] → [30] → [40]

这里解释三个核心操作：

入队 enqueue
出队 dequeue
取队头 front

---

二、队列的两种实现方式

1 数组实现

需要循环队列（因为头删是，需要向前挪动）
数组容量固定

2 链表实现

动态扩展
不需要移动数据
 

---

三、链式队列结构设计

1，解释节点：

QueueNode

结构图：

[val | next]

代码：

typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType val;
}QueueNode;

再解释队列管理结构：

Queue

phead → 队头
ptail → 队尾
size  → 元素个数

typedef struct Queue
{
	struct QueueNode* phead;
	struct QueueNode* ptail;
	int size;
} Queue;

 结构图：

Queue
 │
 ├── phead
 ├── ptail
 └── size

整体结构：

phead → node → node → node
                                               ↑
                                            ptail

---

四、队列初始化

说明初始化为什么只初始化 Queue。

核心思想：（为什么初始化Queue就行，实则都是真的头节点之后才创建）

初始化只是创建空队列
节点在入队时创建

代码：

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

问题小加 

为什么队列不需要头节点（哨兵节点）？

单链表需要，方便头插，头删 ，这种频繁改变头节点的操作

但是队列只有出队（头删）这一种可能

---

五、入队操作（QueuePush）

说明逻辑：

创建新节点
如果队列为空
    phead = ptail = newnode
否则
    ptail->next = newnode
    ptail = newnode

画一个变化过程：

入队前

phead → [10] → [20]
                             ↑
                           ptail

入队30

phead → [10] → [20] → [30]
                                          ↑
                                        ptail

---

六、出队操作（QueuePop）

重点讲两种情况：

情况1：只有一个节点

free(phead)
phead = ptail = NULL

情况2：多个节点

next = phead->next
free(phead)
phead = next

代码：

//队列的头删
void QueuePop(Queue* pq)
{
	assert(pq);
	//assert(pq->phead);
	assert(pq->size != 0);
	if (pq->size == 1)
	{
		free(pq->phead);
		pq->ptail = pq->phead = NULL;
	}
	Queue* next = (pq->phead)->next;
	free(pq->phead);
	pq->phead = next;

	pq->size--;
}

---

七、销毁队列

这里解释为什么链表不能一次 free。

核心思想：

每个节点都是一次 malloc
必须逐个 free

代码逻辑：

循环释放节点

---

八、常见错误总结

可以写你今天遇到的几个 bug：

1 if 后多写分号

if (pq->size == 1);

会导致判断失效。

---

2 访问空指针

pq->phead 为 NULL
却访问 pq->phead->next

会出现：

读取访问权限冲突

---

3 删除最后一个节点忘记修改 ptail

正确做法：

phead = ptail = NULL

---

九、时间复杂度分析

入队  O(1)
出队  O(1)

原因：

有 ptail 指针
无需遍历

---

十、总结

链式队列利用链表实现 FIFO
通过 phead 和 ptail 实现 O(1) 入队和出队
适合动态数据规模

十一，全代码

Queue.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>

typedef int QDateType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDateType val;
}QueueNode;

typedef struct Queue
{
	struct QueueNode* phead;
	struct QueueNode* ptail;
	int size;
} Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);

// 队列的尾插
void QueuePush(Queue* pq, QDateType x);
//队列的头删
void QueuePop(Queue* pq);

// 队列取头 取尾
QDateType QueueFront(Queue* pq);
QDateType QueueBack(Queue* pq);

//取值
int QueueSize(Queue* pq);

//验空
bool QueueEmpty(Queue* pq);

Queue.c

#include"Queue.h"
//初始化销毁
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

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;
	pq->size = 0;
}

// 队列的尾插
void QueuePush(Queue* pq, QDateType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)//说明是空链表
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
//队列的头删
void QueuePop(Queue* pq)
{
	assert(pq);
	//assert(pq->phead);
	assert(pq->size != 0);
	if (pq->size == 1)
	{
		free(pq->phead);
		pq->ptail = pq->phead = NULL;
	}
	Queue* next = (pq->phead)->next;
	free(pq->phead);
	pq->phead = next;

	pq->size--;
}


// 队列取头 取尾
QDateType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
QDateType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	//assert(pq->size != 0);应该也行反正
	return pq->ptail->val;
}


//取值
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

//验空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}