数据结构 ——— C语言实现链式队列
目录
队列的概念以及示意图
数组队列和链式队列
链式队列的结构
实现链式队列的准备工作
实现链式队列
1. 初始化
2. 打印队列的所有数据
3. 数据入队列（尾插）
4. 数据出队列（头删）
5. 访问队头的数据
6. 访问队尾的数据
7. 队列数据总个数
8. 判断队列是否为空
9. 释放队列的所有节点
10. 以队列逻辑遍历所有数据
Queue.h 的所有代码
Queue.c 的所有代码
队列的概念以及示意图
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
队列具有先进先出的逻辑
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
队列结构示意图：
数组队列和链式队列
数组队列：
把首元素当作队头，尾元素当作队尾
那么出队列就需要删除首元素，在把后面的元素向前挪动，降低了效率
且当空间不够时需要扩容，就存在异地扩容的问题，也会降低效率
链式队列：
把头节点当作队头，尾节点当作队尾
那么出队列只需要将指向头节点的指针指向下一个节点，在释放头节点即可，效率为O(1)
入队列只需要在尾节点尾插即可，所以选择实现链式队列
链式队列的结构
// 数据类型
typedef int QDataType;
// 链式队列每个节点的结构
typedef struct QueueNode
{
struct QueueNode* next; //指向下一个节点的指针
QDataType data; //当前节点的数据
}QNode;
// 链式队列的结构
typedef struct Queue
{
QNode* phead; //指向队头节点的指针
QNode* ptail; //指向队尾节点的指针
int size; //队列的总数据个数
}Queue;实现链式队列的准备工作
创建3个文件
test.c 文件：用来测试增删查改功能是否完善
Queue.h 文件：用来声明动态顺序表的结构以及声明增删查改函数
Queue.c 文件：用来实现动态顺序表的增删查改及功能函数
实现链式队列
1. 初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}2. 打印队列的所有数据
void QueuePrint(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
printf("head<-");
while (cur != NULL)
{
printf("%d<-", cur->data);
cur = cur->next;
}
printf("tail\n\n");
}3. 数据入队列（尾插）
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
// 开辟节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
// 判断是否开辟成功
if (newnode == NULL)
{
assert(pq->ptail == NULL);
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->phead == NULL)
{
// 双重判断，更保险
assert(pq->ptail);
pq->phead = newnode;
pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}分两种情况判断：
当队列没有节点时：直接将指向头尾节点的指针指向新节点
当队列有节点时：pq->ptail 就是指向最后一个节点的指针，那么 pq->ptail->next 就是节点的 next，直接指向新节点，再将 pq->ptail指向新节点
数据成功入队列，最后 size 自增1
测试代码：
4. 数据出队列（头删）
void QueuePop(Queue* pq)
{
assert(pq);
// 队列没有数据时
if (pq->phead == NULL)
{
printf("无数据可出队列\n");
return;
}
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = NULL;
pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}分三种情况判断：
队列没有节点时：直接报错并返回
队列只有一个节点时：释放头节点，并将指向头尾节点的指针都置空
队列有多个节点时：保存下一个节点，再释放头节点，最后将指向头节点的指针指向保存的下一个节点
数据成功出队列，最后 size 自减1
测试代码：
5. 访问队头的数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
// 队列没有数据时
if (pq->phead == NULL)
{
printf("无数据可访问\n");
return;
}
return pq->phead->data;
}6. 访问队尾的数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
// 队列没有数据时
if (pq->ptail == NULL)
{
printf("无数据可访问\n");
return;
}
return pq->ptail->data;
}7. 队列数据总个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}8. 判断队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return (pq->phead == NULL) && (pq->ptail == NULL);
}9. 释放队列的所有节点
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur != NULL)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}10. 以队列逻辑遍历所有数据
Queue q;
QueueInit(&q);
for (int i = 1; i <= 5; i++)
{
QueuePush(&q, i);
}
printf("head<-");
while (!QueueEmpty(&q))
{
// 访问当前队头数据
printf("%d<-", QueueFront(&q));
// 移除当前队头数据
QueuePop(&q);
}
printf("tail\n\n");测试代码：
Queue.h 的所有代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
// 数据类型
typedef int QDataType;
// 链式队列每个节点的结构
typedef struct QueueNode
{
struct QueueNode* next; //指向下一个节点的指针
QDataType data; //当前节点的数据
}QNode;
// 链式队列的结构
typedef struct Queue
{
QNode* phead; //指向队头节点的指针
QNode* ptail; //指向队尾节点的指针
int size; //队列的总数据个数
}Queue;
// 初始化
void QueueInit(Queue* pq);
// 打印
void QueuePrint(Queue* pq);
// 数据入队列（尾插）
void QueuePush(Queue* pq, QDataType x);
// 数据出队列（头删）
void QueuePop(Queue* pq);
// 访问队头的数据
QDataType QueueFront(Queue* pq);
// 访问队尾的数据
QDataType QueueBack(Queue* pq);
// 队列数据总个数
int QueueSize(Queue* pq);
// 是否为空
bool QueueEmpty(Queue* pq);Queue.c 的所有代码
#include"Queue.h"
// 初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
// 打印
void QueuePrint(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
printf("head<-");
while (cur != NULL)
{
printf("%d<-", cur->data);
cur = cur->next;
}
printf("tail\n\n");
}
// 数据入队列（尾插）
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
// 开辟节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
// 判断是否开辟成功
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->phead == NULL)
{
// 双重判断，更保险
assert(pq->ptail == NULL);
pq->phead = newnode;
pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
// 数据出队列（头删）
void QueuePop(Queue* pq)
{
assert(pq);
// 队列没有数据时
if (pq->phead == NULL)
{
printf("无数据可出队列\n");
return;
}
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = NULL;
pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
// 访问队头的数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
// 队列没有数据时
if (pq->phead == NULL)
{
printf("无数据可访问\n");
return -1;
}
return pq->phead->data;
}
// 访问队尾的数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
// 队列没有数据时
if (pq->ptail == NULL)
{
printf("无数据可访问\n");
return -1;
}
return pq->ptail->data;
}
// 队列数据总个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
// 是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return (pq->phead == NULL) && (pq->ptail == NULL);
}