算法 c语言 数据结构第八弹---队列

队列

1、队列的概念和结构2、队列的实现2.1、头文件包含和结构定义2.2、初始化2.3、销毁2.4、判断是否为空2.5、入队2.6、出队2.7、获取队头数据2.8、获取队尾数据2.9、获取有效数据个数

3、代码汇总总结

1、队列的概念和结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性 表，队列具有先进先出FIFO(First In First Out) 的原则。

入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。 如何实现队列？ 队列是一种一端插入一端删除的数据结构，所以最好的实现方式是头删尾插效率高或者头插尾删效率高。

1.数组实现：尾插和尾删效率较高，不太适合。 2.单链表实现：头删尾插效率较高，链表头删，链表尾插。 前面单链表提到尾插之前需要找到尾结点，为什么此处又说尾插效率高呢？ 因为我们可以在定义结构的时候创建一个记录尾结点的变量，这样我们每次尾插的时候就不需要找尾结点了。 3.双向链表实现：头插头删尾插尾删效率都较高，可以实现队列。 双向链表头插头删尾插尾删效率都较高，为什么此处不直接使用双向链表实现呢？ 因为单链表就能很好的实现一个队列，而双向链表相较与单链表会多开辟一个结点，在空间方面会有更多的消耗，所以一般不推荐使用双向链表实现队列。

2、队列的实现

经过上述的分析，我们推荐使用单链表实现队列，那么接下来就由博主来实现一下队列。 首先创建一个工程。(下图为vs 2022) Queue.h（队列的类型定义、接口函数声明、引用的头文件） Queue.c（队列接口函数的实现） test.c （主函数、测试顺序表各个接口功能）

2.1、头文件包含和结构定义

以下是实现队列可能用到的头文件。

#include

#include

#include

#include

以下是博主创建的队列结构，可以根据自己的喜好创建喔。 建议：创建结构时最好能通俗易懂，最好不用拼音创建。

typedef int QDataType;

typedef struct QueueNode

{

struct QueueNode* next; //存放下一个结点指针

QDataType data; //存放数据

}QueueNode;

typedef struct Queue

{

QueueNode* head;//头结点

QueueNode* tail;//尾结点

}Queue;

2.2、初始化

链表的结构是通过动态开辟的空间，可以先不初始化。但是队列的结构是在栈区开辟的，为了防止越界访问，需要先初始化为NULL。

void QueueInit(Queue* pq)

{

assert(pq);//防止空指针传入

pq->head = pq->tail = NULL;//初始化为空指针，防止野指针问题

}

2.3、销毁

队列是通过动态开辟的内存，需要手动释放，即依次遍历将结点空间释放，并手动置空。 思想：定义一个变量用来找结点，不为空则释放然后找下一个结点，为空则结束。

void QueueDestory(Queue* pq)

{

assert(pq);

QueueNode* cur = pq->head;//养成创建变量习惯，为了后面能找到头结点

while (cur)

{

QueueNode* next = cur->next;//标记下一个结点

free(cur);

cur = next;//更新结点

}

pq->head = pq->tail = NULL;//释放完手动置NULL

}

2.4、判断是否为空

根据队列的初始化函数可知，在创建之前会将头结点置空，所以头结点为空则队列为空。

bool QueueEmpty(Queue* pq)

{

assert(pq);

return pq->head == NULL;//头结点为空则返回真

}

测试

2.5、入队

入队：即在队尾处插入数据。

画图分析如下 代码实现

void QueuePush(Queue* pq, QDataType x)

{

assert(pq);

QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));

if (newnode == NULL)//动态开辟后记得判断喔！

{

printf("malloc fail\n");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;

if (pq->tail == NULL)//没有数据情况

{

pq->head = pq->tail = newnode;//将新结点赋值给头尾结点

}

else//有数据情况

{

pq->tail->next = newnode;//尾结点下一个插入数据

pq->tail = newnode;//将尾结点更新

}

}

测试

2.6、出队

出队：即在队头位置删除数据。 前提：有数据才能出队

代码实现

void QueuePop(Queue* pq)

{

assert(pq);

assert(pq->head);//确保有数据

//一个元素

if (pq->head->next == NULL)

{

free(pq->head);//释放空间

pq->head = pq->tail = NULL;//手动置空

}

//多个元素

else

{

QueueNode* next = pq->head->next;

free(pq->head);//释放空间

pq->head = next;//更新头结点

}

}

测试

队头元素就是头结点中存储的数据

2.7、获取队头数据

队头数据：即头结点数据。

代码实现

QDataType QueueFront(Queue* pq)

{

assert(pq);

assert(pq->head);

return pq->head->data;

}

测试

2.8、获取队尾数据

队尾元素就是队尾结点的数据

代码实现

QDataType QueueBack(Queue* pq)

{

assert(pq);

assert(pq->head);

return pq->tail->data;

}

测试

将队列遍历一遍，计算大小

2.9、获取有效数据个数

有效数据个数：即有效结点个数。 思想：从头结点开始计算，不为空则size++，然后更新到下一个结点，为空则结束。

代码实现

int QueueSize(Queue* pq)

{

assert(pq);

int size = 0;

QueueNode* cur = pq->head;

while (cur)

{

size++;

cur = cur->next;

}

return size;

}

测试

3、代码汇总

以下是Queue.h的代码。

#define _CRT_SECURE_NO_WARNINGS

#include

#include

#include

#include

typedef int QDataType;

typedef struct QueueNode

{

struct QueueNode* next;

QDataType data;

}QueueNode;

typedef struct Queue

{

QueueNode* head;//头结点

QueueNode* tail;//尾结点

}Queue;

//初始化

void QueueInit(Queue* pq);

//销毁

void QueueDestory(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的代码

#define _CRT_SECURE_NO_WARNINGS

#include "Queue.h"

void QueueInit(Queue* pq)

{

assert(pq);

pq->head = NULL;

pq->tail = NULL;

}

void QueueDestory(Queue* pq)

{

assert(pq);

QueueNode* cur = pq->head;

while (cur)

{

QueueNode* next = cur->next;

free(cur);

cur = next;

}

pq->head = pq->tail = NULL;

}

void QueuePush(Queue* pq, QDataType x)

{

assert(pq);

QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));

if (newnode == NULL)

{

printf("QueueNode fail\n");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;

if (pq->tail == NULL)

{

pq->head = pq->tail = newnode;

}

else

{

pq->tail->next = newnode;

pq->tail = newnode;

}

}

void QueuePop(Queue* pq)

{

assert(pq);

assert(pq->head);

if (pq->head->next == NULL)

{

free(pq->head);

pq->head = pq->tail = NULL;

}

else

{

QueueNode* next = pq->head->next;

free(pq->head);

pq->head = next;

}

}

QDataType QueueFront(Queue* pq)

{

assert(pq);

assert(pq->head);

return pq->head->data;

}

QDataType QueueBack(Queue* pq)

{

assert(pq);

assert(pq->head);

return pq->tail->data;

}

bool QueueEmpty(Queue* pq)

{

assert(pq);

return pq->head == NULL;

}

int QueueSize(Queue* pq)

{

assert(pq);

int size = 0;

QueueNode* cur = pq->head;

while (cur)

{

size++;

cur = cur->next;

}

return size;

}

总结

本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！

推荐链接

 您阅读本篇文章共花了：