今天船长计划用简单的方式向大家介绍数据结构中重要知识点——队列
目录
1.队列的概念及结构
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特征；进行插入操作的一端称为队尾，进行删除操作的一端称为队头；
下面我将向大家展示队列的结构图解：
2.队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优，因为如果使用数组的结构，队列在数组头部出数据，效率会比较低
2.1 头文件的包含
下面我将带大家一步步实现队列的结构，首先我们需要先书写出所需的头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//判空函数头文件，后文有提及2.2构造结构体
这里使用了二次封装的结构体，目的是避免使用二重指针修改数据，使函数更简洁
typedef int QDataType;//种类重命名
typedef struct QueueNode
{
struct QueueNnode* next;
QDataType data;
}QNode;
typedef struct Queue//包含另一结构体指针的结构体(相当于二次封装),可避免使用二次指针
{
QNode* head;
QNode* tail;
int size;
}Queue;2.3定义相应的函数
//初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QDataType x);
//队头出队列
void QueuePop(Queue* pq);
//获取队头元素
QDataType QueueFront(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回特定数据
int QueueEmpty(Queue* pq);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
2.4实现相应的函数
2.4.1 初始化函数
//初始化
void QueueInit(Queue* pq)
{
//查空、头尾指针置空、对应号为0
assert(pq);
pq->head = pq->tail = NULL;//结构体指针，初始化置空
pq->size = 0;
}2.4.2 队尾入队列、队头出队列
队尾入队列思路：查空、创建新节点、检查新节点、封装新节点(x，next->NULL)、检查尾指针head或tail(是否无结点)、链接新节点(tail换位)、size++
//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");//错误返回
exit(-1);//退出为-1
}
else
{
newnode->data = x;
newnode->next = NULL;
}
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}对头出队列思路：验空、验首项、找头、删头释放空间、考虑只有头一项的情况、size--
//队头出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)//==!!!
{
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
}
pq->size--;
}2.4.3获取队头元素、获取队尾元素
QDataType QueueFront(Queue* pq)
{
//验空、验首项、return头元素
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}//获取队尾元素
QDataType QueueBack(Queue* pq)
{
//验空、验首项、return尾元素
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}2.4.4 验空函数
检测队列是否为空
// 检测队列是否为空，如果为空返回非零结果，如果非空返回特定公式
int QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL && pq->tail == NULL;
}2.4.5获取队列中有效元素个数、销毁队列
// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}销毁队列思路：查空、找头、遍历+释放空间、头尾指针置空
//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;//使用与头指针相同的储存类型
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->head = pq->tail = NULL;
}2.5测试检验
船长解下来会给出对应的测试函数，如果各位看官老爷们有兴趣不妨自己动手试试哦
void TestQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
printf("%d ", QueueFront(&q));
QueuePop(&q);
printf("%d ", QueueFront(&q));
QueuePush(&q, 4);
QueuePush(&q, 4);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
}
int main()
{
TestQueue();
return 0;
} 下面是对应的测试结果：
4.结语
看到这里，相信老铁们对如何实现队列已经有了相应的了解。
我是计算机海洋的新进船长Captain_ldx,如果我的文章能对您有帮助的话，麻烦各位观众姥爷们点赞、收藏、关注，你们的每一次举手之劳都将化为船长的前进动力！