数据结构初阶队列

一. 队列的基本介绍

1. 基本概念

队列是基本数据结构的一种它符合先进先出的原则

我们来看图

大概就是这样子的一种情况

我们想想看应该用数组还是链表来实现这个结构方便一点呢

我想同学们心里现在肯定已经有了答案了

肯定不是数组

为什么呢？

因为我们如果用数组头作为队头的话每次删数据就要往前移动很多组其他的数据

这里有同学肯定会有这样子的疑问？

不移动可不可行呢？

当然不可以！

队列这种数据结构已经规定死了就是头出尾进

所以说我们使用链表来实现这个数据结构

2. 代码表示

typedef int QDateType;
typedef struct QueueNode
{struct QueueNode* next;QDateType date;
}QNode;
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;

仔细看

我们这里使用QueueNode来表示储存数据的一个个节点

使用Queue来表示两个指针头和尾

可以看图理解快一点

二. 接口函数的实现

1. 队列初始化

//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}

队列初始化实际上就是将队列的两个指针置空

我们来看看效果

这里没有传二级指针进去到底能不能将一级指针置空

成功将两个指针置空了

这是为什么呢？

因为我们的头和尾指针实际上是储存在一个结构体里面的

当我们将结构体的地址传进去的时候结构体指针能够访问到结构体内部的内容（这两个指针）并且可以修改它们

2. 插入数据

这里插入数据我们要考虑两种情况

1.如果head和tail指针指向NULL，就需要将newnode赋给head和tail指针

2.head和tail不指向NULL，就将newnode的地址赋给tail->next，再将tail移到newnode即可

代码如下：

//队进
void QueuePush(Queue* pq, QDateType x)
{assert(pq);//开辟新节点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}//赋值newnode->next = NULL;newnode->date = x;//判断是否为空if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}//个数要++pq->size++;
}

看看效果怎么样

可以运行

3. 删除数据

这里我们要注意的是

由于队列结构的特殊性

我们在打印数据的时候必须要删除数据

所以我们先写删除数据的接口函数

代码表示如下

void QueuePop(Queue* pq)
{assert(pq);assert(pq->head!=NULL);//只有一个节点if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{//保存下一位QNode* next = pq->head->next;free(pq->head);pq->head = next;//迭代}//个数要--pq->size--;
}

看看效果：

可以运行

4. 摧毁队列

直接看代码：

void QueueDestroy(Queue* pq)
{assert(pq);//两个结构体依次销毁 先销毁QNodeQNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}//再置空Queuepq->head = pq->tail = NULL;pq->size = 0;
}

注意：两个结构体要依次销毁，类似（套娃）

我们来看看效果

5. 判断为空

这个也很简单和栈差不多

这里就直接给代码了

//判断为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

6.返回大小

这个也很简单，因为我们在Queue结构体中已经定义过size了，我们直接返回就可以

直接看代码：

//大小
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

7. 返回头数据

这个很简单返回head的值就可以了

注意断言的使用

//对头
QDateType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->date;
}

8.返回尾数据

一样的简单

也要注意断言的使用

//队尾
QDateType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->date;
}

以上便是本文所有内容了，如有错误请各位大佬不吝赐教，感谢留言