目录
1.定义
2.队头和队尾
3.示意图
4.实现队列
两种解决方法
1.使用双向带头循环链表
2.为单向链表再定义一个尾指针tail
操作队列的函数
初始化函数QueueInit
插入函数QueuePush
删除函数QueuePop
写法1
注意
写法2
计算队列大小函数QueueSize
销毁函数QueueDestroy
1.定义
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
2.队头和队尾
队头:进行删除(即出队Dequeue)操作的一端
队尾:进行插入(即入队Enqueue)操作的一端
注意到:由于队列的特性,删除只在队头,插入只在队尾(这里和链表不一样:链表支持头删、尾删、头插和尾插)
特点:FIFO(First In First Out)先进先出
3.示意图
这里比较像链表的尾插
4.实现队列
main函数的第一行代码
QNode* head = NULL;如果频繁尾插,会导致找尾麻烦,因此不建议这样写,
两种解决方法
1.使用双向带头循环链表
有关双向带头循环链表的内容参见
94.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删
95.【C语言】数据结构之双向链表的头插,头删,查找,中间插入,中间删除和销毁函数
2.为单向链表再定义一个尾指针tail
Queue.h写入
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;除了有头指针和尾指针之外,还要用变量size来存储队列的大小
再用一个结构体去定义队列中的每一个节点
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;这里和以往的链表的定义不一样,用两个结构体来定义 ,将头指针,尾指针和size打包成结构体是为了方便操作
画图则为:
操作队列的函数
初始化函数QueueInit
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
一开始队列一个元素都没有插入,因此head和tail全部置NULL,队列大小size为0
插入函数QueuePush
每插入一个节点需要做两件事:
1.开辟节点并写入节点(节点指针和节点值)
做法:malloc开辟空间,检查空间是否成功开辟,再用newnode接收新开辟空间的起始地址,
2.修改结构体Queue的成员变量
注意:如果一开始队列中一个节点都没有,不能直接尾插,否则导致pq->tail->next = newnode;和pq->tail = newnode;变为NULL->next = newnode;和NULL = newnode;不合法
如果为NULL,做的操作应该是头指针和尾指针都应该指向newnode,size++而不是去尾插
队列中有节点,直接为插,size++
void QueuePush(Queue* pq, QDataType x)
{
//开辟节点并写入节点(节点指针和节点值)
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->data = x;
newnode->next = NULL;
//---------------------------------------------------
//修改结构体Queue的成员变量
if (pq->head == NULL)
{
assert(pq->tail == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}删除函数QueuePop
队列的性质只支持头删
写法1
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head != NULL);
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
if (pq->head == NULL)
pq->tail = NULL;
pq->size--;
}注意
1.空队列不能头删,因此断言assert(pq->head != NULL);
2.头删要先保存头节点的下一个节点的地址,之后free(头结点的地址)
3.如果头删后没有节点,则投头指针和尾指针都要赋值为NULL
写法2
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head != NULL);
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}
计算队列大小函数QueueSize
由于提前创建好了结构体Queue,则直接返回size即可
void QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}销毁函数QueueDestroy
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}1.由于malloc是以节点为单位开辟空间的,则内存释放时也要以节点为单位释放,因此内存释放要先保存头节点的下一个节点的地址,之后free(头结点的地址)
2.恢复头指针,尾指针和size的初始值
