链式队列的结构

typedef int QDataType;typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;
}Queue;

由于使用链表实现队列，所以我们需要一个队列结点QueueNode，保存值域和指向下一节点的指针；
由于队列的功能为对头出队，队尾入队，所以设计两个指针，分别指向对头队尾；Queue就是队列的结构，里面有对头队尾指针；

---

链式队列的头文件

完成基本功能： 初始化； 判空； 摧毁； 入队； 出队； 获取对头； 获取队尾； 队列元素个数；

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
bool QueueIsEmpty(Queue* pq);
QDataType QueueBack(Queue* pq);
QDataType QueueFront(Queue* pq);
int QueueSize(Queue* pq);

---

链式队列的实现代码

这是没有头结点的链式队列：所以当我们在入队时候，要判断入队的元素是否为第一个，单独处理第一个数据；然后其他数据尾插即可；

出队时候，如果对头指针指向空，表示出完队列所有元素，要注意给队尾置空；

#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}
//释放队列的所有结点
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* cur = pq->head;while (cur){QueueNode* next = cur->next;free(cur);cur = next;}
}
//入队，队尾入队
void QueuePush(Queue* pq,QDataType x)
{assert(pq);QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));newNode->data = x;newNode->next = NULL;//插入的数据为第一个结点if (pq->head == NULL){pq->head = pq->tail = newNode;}else //不是第一个结点{pq->tail->next = newNode;pq->tail = newNode;}
}
//出队，对头出队
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head); //队列为空不可以删//队列不为空，删QueueNode* next = pq->head->next;free(pq->head);pq->head = next;//单独出来还剩最后一个结点//tail 和 head 都执行最后一个结点，//此时要置空tail//防止野指针if (pq->head == NULL){pq->tail = NULL;}}
//判断队列是否为空
bool QueueIsEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}
//获取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head);return pq->tail->data;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head != NULL); //空队列return pq->head->data;
}
int QueueSize(Queue* pq)
{assert(pq);QueueNode* cur = pq->head;int count = 0;while (cur){cur = cur->next;count++;}return count;}