前言
使用单向无头不循环链表实现队列。
队列：符合先进先出逻辑的特殊数据结构。
不适合用数组来实现，虽然入队便捷但是出队时需要挪动队首后的所有元素，效率略低。
单向不循环链表对于找尾的效率确实低，但是可以在结构体中定义出队首节点和队尾节点，分别管理使得入队和出队的效率都高。所以就需要定义两个结构体，一个管理节点的内容，一个管理整个队列。
建议先跳转到第三部分阅读结构体定义的代码，以便后续便于理解。
关于改变链表头节点的方式：
1、二级指针（传指针解引用改变）
2、返回新头（接受改变值）
3、带哨兵位的头节点（本质上不会改变头节点）
4、结构体包一起（大结构体一级指针改变）
此次选择第四种方式。
可能这时候就会有同学这样问了：为什么在实现单向不循环链表的时候不把结构体包一起呢？这样不就解决了找尾效率低的问题吗？
哎，这位同学就年轻了啊。你这样解决了尾插的问题，但是能解决尾删的问题吗？单向不循环链表中时不能通过一个节点找到上一个节点的。也就是尾删了后还是要找尾···
一、易错接口详解
1.1 出队
出队算法：法一：保存下一个节点为next，再删除。
法二：保存要删除的节点为del，把头结点赋值为新节点，然后free掉del
此次选择法一。
需要注意队列为空时调用此接口会出现非法访问的错误，所以需要提前断言报错。
这里把判断是否为空的功能封装成一个函数，详情请跳转至第二部分查看。
特殊情况：当链表删除掉最后一个节点时，ptail会成为野指针。
所以仅有一个节点时就直接free掉，再将头指针和尾指针都赋值为NULL。
正常情况下，出队时记得保留队头节点的下一节点的地址，以便头节点迭代。
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QueueNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
}
1.2 入队
入队算法：为新的头节点开辟新空间，并插入有效数据。之后的步骤相当于链表的尾插。
但是需要注意特殊情况：队列中没有节点时需要直接把头尾节点都改为新节点。
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->ptail == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
}
二、 简单接口的实现
2.1 队列的初始化
算法：将头指针和尾指针都赋值为NULL
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
}
2.2 队列节点计数
int QueueSize(Queue* pq)
{
assert(pq);
int count = 0;
QueueNode* cur = pq->phead;
while (cur)
{
count++;
cur = cur->next;
}
return count;
}
关于链表计数的接口，如果调用频繁的话就可以在大结构体Queue中加入一个计数成员，入队或出队时修改。如果调用不频繁，就直接在接口中进行计算。
2.3 队列的销毁
算法：利用创建的新指针cur从头走到尾，走到一个节点就删除一个节点，在删除前还需要保留cur指针的下一个节点地址，以便cur指针迭代。最后还不要忘了将头节点的指针phead和为节点的指针ptail指向NULL。
void QueueDestory(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->phead;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
}
2.4 判断队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL && pq->ptail == NULL;
}
2.5 返回队头数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
2.6 返回队尾数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
三、头文件引用、函数与结构体定义
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QueueNode;
typedef struct Queue
{
QueueNode* phead;
QueueNode* ptail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
四、拾枝杂谈——队列接口调用方式
首先创建一个大结构体Queue的对象q，再把对象初始化，再入队，打印的时候必须打印一个队首元素就将队首元素进行出队，直至队列为NULL时即可将队中所有元素打印完成，最终销毁整个队列，避免内存泄漏。
void Test2()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
QueueDestory(&q);
}
|