初阶数据结构C语言实现4.2队列
目录
初阶数据结构（C语言实现）——4.2队列
2.队列
2.1队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
2.2队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
- 队列结构
// 链式结构：表示队列
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
- 队列接口
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);- 在VS2022中新建一个工程
Queue20250310.h（队列的类型定义、接口函数声明、引用的头文件）
Queue20250310.c（队列的接口函数的实现）
QueueTest20250310.c（主函数、测试各个接口功能）
2.2.1 初始化队列
// 初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;// 初始化队列的头指针和尾指针为NUL
pq->size = 0; // 初始化队列的大小为0
}2.2.2 销毁队列
// 销毁队列
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;// 将队列的头指针和尾指针置为NUL
pq->size = 0;//将队列的大小置为0
}2.2.3 队尾入队列
// 队尾入队列
void QueuePush(Queue* pq, QDataType data)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("QueueDestroy::malloc fail!");
return;
}
newnode->data = data;// 将数据存入新节点
newnode->next = NULL;// 将新节点的指针域置为NULL
if (pq->head == NULL)// 如果队列为空，则新节点即为队列的头指针和尾指针
{
assert(pq->tail == NULL);
pq->head = pq->tail = newnode;
}
else //如果队列不为空，则将新节点插入到队列的尾部
{
//尾插
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;// 队列的大小加1
}2.2.4 队头出队列
// 队头出队列
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)// 如果队列为空，则将尾指针也置为NULL
pq->tail = NULL;
pq->size--;
}2.2.5获取队列头部元素
// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}2.2.6 获取队列队尾元素
// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}2.2.7获取队列中有效元素个数
// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}2.2.8 检测队列是否为空，如果为空返回非零结果，如果非空返回0
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;// 如果队列的头指针为NULL，则队列为空
}