数据结构之队列

  • 开发
  • 21

片头

嗨,小伙伴们,大家好! 在上一篇中,我们学习了栈,那么在这一章中我们将学习队列的相关知识,准备好了吗 ? Ready Go ! ! !

一、队列

1.1 队列的基本概念

在上一章中，我们学习了数据结构之栈,知道了栈遵循后进先出(LIFO)原则。与栈相对的，队列中的数据元素遵循先进先出(FIFO)原则。那么什么是队列呢？

字面意思来看，就是下图中小狗们排队的场景，每当新的小狗想加入队列时，就会排到最后面；如果最前面的小狗打完饭了，就会出队列。也就是我们说的先进先出（FIFO）。

那么，在我们数据结构当中，队列的定义是什么？

队列： 只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出(FIFO)的特点。进行插入操作（入队）的一端称为队尾，进行删除操作（出队）的一端称为队头。

1.2 队列的实现

我们可以使用数组结构或链表结构来实现队列。如果使用数组来实现队列的话，数组的头插头删需要对每一个元素进行移动操作，效率不如链表。所以二者取其优，我们使用链表的结构实现队列会更简便高效。

关于链表，我们在前面已经学习过了数据结构之单链表和数据结构之双向循环链表，在这里，我们使用单链表就可以解决问题。

二、队列的接口实现 

我们先创建一个头文件“Queue.h”和2个源文件"Queue.c"和"Test.c",具体作用为:

Queue.h 队列的定义,头文件的引用和接口函数的声明
Queue.c 接口函数的实现
Test.c 测试各个函数

明确了使用单链表后,我们需要考虑更多的细节问题。出队的时候，由于队列的先进先出原则，我们要删除队头（即链表头结点） 所以需要一个指针来保存头结点的地址；而入队的时候，我们则需要从队尾（即链表尾结点）插入元素，所以还需要一个指针来保存尾结点的地址。综上所述，我们需要定义2个结构体：①队列中每一个结点的结构体（包含数据域，指针域）②队列结构体（front指针,rear指针,size表示队列的长度）(第2个结构体来保存头尾结点的地址)。

我们先展示“Queue.h”的完整代码,最后再展示"Queue.c"的完整代码。不要忘记在两个源文件中引用“Queue.h”

#pragma once			  //防止头文件被二次引用
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int ElemType;	   //如果要修改存储的数据类型可直接在此修改
typedef struct QListNode   //链式结构: 表示队列结点
{
	ElemType data;		   //每一个结点的数据域
	struct QListNode* next;//每一个结点的指针域
}QNode;

typedef struct Queue	   //队列的结构
{
	QNode* front;			//指向队头
	QNode* rear;			//指向队尾
}Queue;

//队列的增删查改接口实现(因为指针在结构体中,所以不需要传二级指针)

void QueueInit(Queue* q);//初始化队列

void QueuePush(Queue* q, ElemType x);//队尾入队列

void QueuePop(Queue* q);//队头出队列

ElemType QueueFront(Queue* q);//获取队列头部元素

ElemType QueueBack(Queue* q);//获取队列队尾元素

int QueueSize(Queue* q);//获取队列中有效元素个数

int QueueEmpty(Queue* q);//检测队列是否为空,如果为空返回非零结果,如果非空返回0

void QueueDestroy(Queue* q);//销毁队列

接下来我们开始逐个实现各个接口函数

（1）初始化队列
//初始化队列
void QueueInit(Queue* q) {
	assert(q);		 //断言,防止传入空指针
	q->front = NULL; //初始化指向头结点的指针
	q->rear = NULL;  //初始化指向尾结点的指针
	q->size = 0;	 //初始化队列的大小为0
}
（2）队尾入队列
//队尾入队列
void QueuePush(Queue* q, ElemType x) {
	assert(q);//断言,防止传入空指针
	QNode* newNode = (QNode*)malloc(sizeof(QNode));//创建新结点
	if (newNode == NULL) //如果空间开辟失败
	{
		perror("malloc fail!\n");
		exit(1);
	}
	newNode->data = x;	 //新结点的数据域为x
	newNode->next = NULL;//新结点的指针域为NULL

	if (q->front == NULL) //q->front == NULL,说明队列为空
	{
		q->front = q->rear = newNode;//两个指针都指向新结点
	}
	else				  //如果队列不为空
	{
		q->rear->next = newNode;//原来的尾结点指向新结点
		q->rear = newNode;//新结点变成尾结点
	}
	q->size++;//队列的长度加1
}

因为队列和顺序表、链表不一样，它不能像链表遍历打印，需要使用 QueueEmpty函数 和 QueuePop函数, 后面会讲到。

（3）队头出队列
//队头出队列
void QueuePop(Queue* q) {
	assert(q);	//断言,防止传入空指针
	assert(q->front != NULL);//断言,队列为空则报错
	if (q->front->next == NULL) //如果队列中只剩下1个结点
	{
		free(q->front);//释放唯一结点
		q->front = q->rear = NULL;//两个指针置空
	}
	else
	{
		//队列不止1个结点
		QNode* del = q->front;//用del临时变量保存头结点的地址
		q->front = del->next; //头结点更新
		free(del);			  //释放原来的头结点
		del = NULL;			  //置空
	}
	q->size--;			  //更新size
}
（4）获取队列头部元素
//获取队列头部元素
ElemType QueueFront(Queue* q) {
	assert(q);			 //断言,防止传入空指针
	assert(q->front != NULL);//断言,队列为空则报错
	return q->front->data;//返回队头元素
}
（5）获取队列队尾元素
//获取队列队尾元素
ElemType QueueBack(Queue* q) {
	assert(q);			 //断言,防止传入空指针
	assert(q->rear != NULL);//断言,队列为空则报错
	return q->rear->data;//返回队尾元素
}
（6）获取队列中有效元素的个数
//获取队列中有效元素个数
int QueueSize(Queue* q) {
	assert(q);			//断言,防止传入空指针
	return q->size;		//size即为有效元素个数
}
（7） 检测队列是否为空
///检测队列是否为空,如果为空返回非零结果,如果非空返回0
int QueueEmpty(Queue* q) {
	assert(q);			//断言,防止传入空指针
	return q->size == 0;//如果为空返回1,如果非空返回0
}
（8）销毁队列
//销毁队列
void QueueDestroy(Queue* q) {
	assert(q);		    //断言,防止传入空指针
	QNode* p = q->front;//创建一个指针变量用来保存每次的头结点位置
	while (p != NULL)   //当 p == NULL时队列销毁完毕,跳出循环
	{
		QNode* Q = p->next;//更新头结点的地址
		free(p);		   //释放原来的头结点
		p = Q;			   //p指向新的头结点
	}
	q->front = q->rear = NULL;//将2个指针置空
	q->size = 0;//更新size
}

所有接口已经实现，我们在Test.c文件中测试一下:

哈哈哈,运行结果正确 ! 恭喜你,完成了实现队列的代码~ 下面是"Queue.c"文件的完整代码:

#include"Queue.h"
//队列的增删查改接口实现(因为指针在结构体中,所以不需要传二级指针)

//初始化队列
void QueueInit(Queue* q) {
	assert(q);		 //断言,防止传入空指针
	q->front = NULL; //初始化指向头结点的指针
	q->rear = NULL;  //初始化指向尾结点的指针
	q->size = 0;	 //初始化队列的大小为0
}

//队尾入队列
void QueuePush(Queue* q, ElemType x) {
	assert(q);//断言,防止传入空指针
	QNode* newNode = (QNode*)malloc(sizeof(QNode));//创建新结点
	if (newNode == NULL) //如果空间开辟失败
	{
		perror("malloc fail!\n");
		exit(1);
	}
	newNode->data = x;	 //新结点的数据域为x
	newNode->next = NULL;//新结点的指针域为NULL

	if (q->front == NULL) //q->front == NULL,说明队列为空
	{
		q->front = q->rear = newNode;//两个指针都指向新结点
	}
	else				  //如果队列不为空
	{
		q->rear->next = newNode;//原来的尾结点指向新结点
		q->rear = newNode;//新结点变成尾结点
	}
	q->size++;//队列的长度加1
}

//队头出队列
void QueuePop(Queue* q) {
	assert(q);	//断言,防止传入空指针
	assert(q->front != NULL);//断言,队列为空则报错
	if (q->front->next == NULL) //如果队列中只剩下1个结点
	{
		free(q->front);//释放唯一结点
		q->front = q->rear = NULL;//两个指针置空
	}
	else
	{
		//队列不止1个结点
		QNode* del = q->front;//用del临时变量保存头结点的地址
		q->front = del->next; //头结点更新
		free(del);			  //释放原来的头结点
		del = NULL;			  //置空
	}
	q->size--;			  //更新size
}

//获取队列头部元素
ElemType QueueFront(Queue* q) {
	assert(q);			 //断言,防止传入空指针
	assert(q->front != NULL);//断言,队列为空则报错
	return q->front->data;//返回队头元素
}

//获取队列队尾元素
ElemType QueueBack(Queue* q) {
	assert(q);			 //断言,防止传入空指针
	assert(q->rear != NULL);//断言,队列为空则报错
	return q->rear->data;//返回队尾元素
}

//获取队列中有效元素个数
int QueueSize(Queue* q) {
	assert(q);			//断言,防止传入空指针
	return q->size;		//size即为有效元素个数
}

//检测队列是否为空,如果为空返回非零结果,如果非空返回0
int QueueEmpty(Queue* q) {
	assert(q);			//断言,防止传入空指针
	return q->size == 0;//如果为空返回1,如果非空返回0
}

//销毁队列
void QueueDestroy(Queue* q) {
	assert(q);		    //断言,防止传入空指针
	QNode* p = q->front;//创建一个指针变量用来保存每次的头结点位置
	while (p != NULL)   //当 p == NULL时队列销毁完毕,跳出循环
	{
		QNode* Q = p->next;//更新头结点的地址
		free(p);		   //释放原来的头结点
		p = Q;			   //p指向新的头结点
	}
	q->front = q->rear = NULL;//将2个指针置空
	q->size = 0;//更新size
}

习题部分

5.下列关于队列的叙述错误的是（ ）

A.队列可以使用链表实现

B.队列是一种“先入先出”的数据结构

C.数据出队列时一定只影响尾指针

D.数据入队列时一定从尾部插入

正确答案: C

出队操作，一定会影响头指针，如果出队之后，队列为空，会影响尾指针。

6.用无头单链表存储队列，其头指针指向队头结点，尾指针指向队尾结点，则在进行出队操作时()

A.仅修改队头指针

B.队头、队尾指针都要修改

C.队头、队尾指针都可能要修改

D.仅修改队尾指针

正确答案: C

出队操作，一定会修改头指针，如果出队之后，队列为空，需要修改尾指针。

 7.以下不是队列的基本运算的是（ ）

A.从队尾插入一个新元素

B.从队列中删除队尾元素

C.判断一个队列是否为空

D.读取队头元素的值

正确答案: B

队列只能从队头删除元素。

8.下面关于栈和队列的说法中错误的是（ ）

A.队列和栈通常都使用链表实现

B.队列和栈都只能从两端插入、删除数据

C.队列和栈都不支持随机访问和随机插入

D.队列是“先入先出”，栈是“先入后出”

正确答案: AB

A错误：栈是尾部插入和删除，一般使用顺序表实现，队列是头部删除尾部插入，一般使用链表实现

B错误：栈是后进先出，尾部插入和删除；队列是先进先出，尾部插入头部删除

C正确：栈只能访问栈顶元素，不支持随机访问，队列也不支持

D正确：栈和队列的特性

故错误的是A和B

9.下列关于顺序结构实现循环队列的说法，正确的是（ ）

A.循环队列的长度通常都不固定

B.直接用队头和队尾在同一个位置可以判断循环队列是否为满

C.通过设置计数的方式可以判断队列空或者满

D.循环队列是一种非线性数据结构

正确答案: C

队列适合使用链表实现，使用顺序结构(即固定的连续空间)实现时会出现假溢出的问题，因此大佬们设计出了循环队列，循环队列就是为了解决顺序结构实现队列假溢出问题的

A错误：循环队列的长度都是固定的

B错误：队头和队尾在同一个位置时 队列可能是空的，也可能是满的，因此无法判断

C正确：设置计数即添加一个字段来记录队列中有效元素的个数，如果队列中有效元素个数等于空间总大小时队列满，如果队列中有效元素个数为0时队列空

D错误：循环队列也是队列的一种，是一种特殊的线性数据结构

故选择C

 10.现有一循环队列，其队头为front，队尾为rear(rear指向队尾数据的下一个位置)，循环队列长度为N,最多存储N-1个数据。其队内有效长度为（ ）

A.(rear - front + N) % N + 1

B.(rear - front + N) % N

C.(rear - front) % (N + 1)

D.(rear - front + N) % (N - 1)

正确答案: B

有效长度一般是rear-front, 但是循环队列中rear有可能小于front，减完之后可能是负数，所以需要+N，此时结果刚好是队列中有效元素个数，但如果rear大于front，减完之后就是有效元素个数了，再加N后有效长度会超过N，故需要%N。  

片尾

今天我们学习了什么是队列以及如何实现队列等问题,希望看完这篇文章能对友友们有所帮助 !   !   !

求点赞收藏加关注 !   !   !

谢谢大家 !   !   !

阅读全部

相关推荐

  1. 数据结构之队列

    2024-07-11 11:38:05       70 阅读

  3. 数据结构之队列

    2024-07-11 11:38:05       41 阅读

  4. 数据结构之队列

    2024-07-11 11:38:05       36 阅读

  6. 04 数据结构之队列

    2024-07-11 11:38:05       43 阅读

  9. PHP数据结构之队列

    2024-07-11 11:38:05       26 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-11 11:38:05       102 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-11 11:38:05       109 阅读

  9. 在Django里面运行非项目文件

    2024-07-11 11:38:05       91 阅读

  19. Python语言-面向对象

    2024-07-11 11:38:05       98 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-11 11:38:05       98 阅读

热门阅读

  3. 服务端健康检查最常见的方式：TCP 端口探测与 HTTP 接口返回码探测

    2024-07-11 11:38:05       29 阅读

  4. Nginx配置支持WebSocket功能

    2024-07-11 11:38:05       31 阅读

  5. CleanCode、安全编码规范

    2024-07-11 11:38:05       30 阅读

  10. 【React】如何自定义 Hooks

    2024-07-11 11:38:05       23 阅读

  13. 学懂C#编程：常用框架学习（一）———学会并理解WPF的应用

    2024-07-11 11:38:05       27 阅读

  21. python实现http get pos download

    2024-07-11 11:38:05       25 阅读

  22. Spring Boot开发框架

    2024-07-11 11:38:05       28 阅读

  23. Vue3响应系统的作用与实现

    2024-07-11 11:38:05       21 阅读

  25. 数据结构第19节 排序算法（1）

    2024-07-11 11:38:05       25 阅读

  26. 【Scrapy】深入了解 Scrapy 中间件中的 process_spider_output 方法

    2024-07-11 11:38:05       27 阅读

  27. 【Scrapy】 深入了解 Scrapy 下载中间件的 process_exception 方法

    2024-07-11 11:38:05       24 阅读

  30. HOW - 黑暗模式 Dark Mode

    2024-07-11 11:38:05       28 阅读