目录
void QueuePush(Queue* pq, QDataType x);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
typedef int QDataType;
typedef struct QueueNode //队列节点1
{
struct QueueNode* next;
QDataType data;
}QNode;
//传参的时候，只需要穿Queue的指针，QNode类型在push内部使用
typedef struct Queue //队列整体
{
QNode* phead; //Queue的phead指向QueueNode的第一个节点
QNode* ptail;
int size;
}Queue;
其次借助Queue.c 与 Queue.h两个文件
一、固定
void QueueInit(Queue* pq);
//队列初始化 //注意英文命名
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq);
//队列销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next; //记录下一个节点
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL; //置空
pq->size = 0;
}
二、push、pop
void QueuePush(Queue* pq, QDataType x);
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//在push内部新建节点指针类型，开辟新的空间
QNode* newnode = (QNode*)malloc(sizeof(QNode)); //push的时候会用到节点结构体类型类型。
if (newnode == NULL)
{
perror("malloc fail\n");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->ptail == NULL) //不带哨兵位，需要判空
{
assert(pq->phead == NULL);
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode; //成为新的尾巴
}
pq->size++; ///插入之后pq->size++
}
void QueuePop(Queue* pq);
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//如果有尾指针单链表的删除要分为一个节点和多个节点
// 1、一个节点
// 2、多个节点
if (pq->phead->next == NULL) //只有一个节点，ptail指向被free的空间，成为野指针
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
// 头删
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--; //增++；删--
}
三、头部元素、尾部元素
QDataType QueueFront(Queue* pq);
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq)); //非真为假
return pq->phead->data;
}
QDataType QueueBack(Queue* pq);
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
四、大小
int QueueSize(Queue* pq);
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}五、判空
bool QueueEmpty(Queue* pq);
bool QueueEmpty(Queue* pq)
{
assert(pq);
//弹出数据的时候，size--；phead、ptail指针挪动，都可以作为判空的任意一个条件
/*return pq->phead == NULL
&& pq->ptail == NULL;*/
return pq->size == 0;
}
注意点
1.QNode代表的是单个节点。Queue代表的是整个队列。传参的时候一般传Queue指针类型，对于push元素的时候，会在函数内部开辟空间时，利用QNode指针类型。
2.节点包括指针next 、 有效数据date 链表包括phead 、 ptail 、 size
3.destroy空间时，需要释放空间 、 指针置空 、 数据置零。释放空间一般先记录下一个节点。
4.对于push而言，需要在内部开辟新的节点（无需buy_new_node函数，只有push会用到开辟），malloc空间时，要将其转化为QNode指针类型。（1.开辟（开辟完成要独立初始化） 2. 判断是否开辟成功 3. 赋值（对于不含哨兵位的单链表插入时，分两种情况①phead为空②phead不为空）4.pq->size++）
当新空间开辟结束之后，pq->phead = newnode;从而让pq->phead引领整个队列
5.对于pop而言首先需要判断有没有节点（任何删除都需要判断有没有有效节点）。当含有尾指针ptail时，删除需要分两种情况（1.只有一个节点 （防止ptail出现野指针问题）2.有多个节点）
pop完成之后size--； （push对应size++；pop对应size--）
6.队列头部元素及尾部元素的返回值要用QDateType类型。节点不可以为空。
assert(pq); 保证必须新建好了队列结构体。
assert(!QueueEmpty(pq));保证队列必须含有有效节点。
7.必须保证所有函数都要assert（pq） 为了保证必须新建好了队列空间！
8.判空（判断是否含有有效节点）：①assert（pq）
②可以选择size == 0判断，可以选择pq->phead == NULL && pq->ptail == NULL。（都对应初始化）
（在初始化完成之后，任何一个pop函数，都会让size--和指针移动）
只有一个元素不会被判空，当唯一的节点被pop之后，此时pq->phead == NULL&& pq->ptail == NULL。
