数据结构-队列

🕗 发布于 2025-01-19 20:05 数据结构

前言

本篇文章介绍队列的基础知识，包括队列的抽象数据类型以及队列的实现。

一、队列及其抽象数据类型

1.1 队列的基本概念

基本定义 限定在表的一端进行插入操作，另一端进行删除操作的线性表
逻辑结构 一种特殊的线性表，一对一关系
存储结构 顺序存储和链式存储，常用顺序存储
运算规则 进行删除操作的一端称为队头，进行插入操作的一端称为队尾，访问结点按照先进先出（FIFO）的原则
队列的插入操作通常称为入队
队列的删除操作通常称为出队
队列的示意图如图1.1所示
在这里插入图片描述

图1.1 队列示意图

1.2 队列的抽象数据类型

ADT Queue
{
数据对象:D={ai|ai ∈ElemSet,i=1,2,3,...n,n >= 0}
数据关系:S={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}
约定an为队尾，a1为队头
基本操作：
initQueue(&Q)
操作结果：构造一个空的队列Q
destroyQueue(&Q)
初始条件：队列Q已存在
操作结果：队列Q被销毁
isEmptyQueue(&Q)
初始条件：队列Q已存在
操作结果：判断队列Q是否为空队列
lengthQueue(&Q)
初始条件：队列Q已存在
操作结果：返回队列Q的长度
enQueue(&Q, e)
初始条件：队列Q已存在
操作结果：插入元素e为队列的队尾元素
deQueue(&Q, &e)
初始条件：队列Q已存在
操作结果：删除队列Q的队头元素，用e返回被删除的元素
getElemQueue(Q, &e)
初始条件：队列Q已存在且为非空队列
操作结果：用e返回队头元素
...
}ADT Queue

二、队列的实现

2.1 顺序表示

2.1.1 结构定义

用顺序存储来表示队列时，要分配一块连续的内存空间来存放队列的元素，并用两个指针变量分别表示队头和队尾。
队列的结构定义如下

//顺序队列的定义

#define SUCCESS 1
#define ERROR 0
#define OVERFLOW -1
#define MAXQSIZE 100   //队列最大元素个数

//队列数据类型定义
typedef char QElemType;

//定义队列类型
struct SeqQueue {
QElemType* base;  //队列指针
int front;        //数据元素下标，假设为队头指针
int rear;  //数据元素下标，假设为队尾指针
};

//定义队列类型指针
typedef struct SeqQueue* PSeqQueue;

利用一块连续的存储单元依次存放自队头到到尾的数据元素
base指针指向这块存储单元的起始地址
front表示队头的下标
rear表示队尾的下标
MAXQSIZE表示队列的最大元素个数
在这里插入图片描述

图2.1 顺序队列示意图

假设MAXQSIZE=4，顺序队列的动态示意图如图2.2
在这里插入图片描述

图2.2 顺序队列的动态示意图

在顺序队列中，同栈一样存在队列溢出问题。
当队列满时，再做入队操作，称为上溢，即对图2.2中的第三个图再做入队操作，会造成上溢；
当队列为空时，再做出队操作，称为下溢，即对图2.2中的第一个和第五个图再做出队操作，会造成下溢

特别地，如果对图2.2中的第五个图进行入队操作，则会造成溢出，而实际上这时队列的前端可能还有可用的空间，因此，这种现象称为假溢出，即front = MAXQSIZE

通常，解决假溢出采用的方法是，把顺序队列从逻辑上看作是一个环形，也称为环形队列，为了在逻辑上形成环形队列，则需要在每次进行入队和出队操作时，对MAXQSIZE进行取余

当环形队列已有MAXQSIZE-1个数据元素时，如果再进行入队操作，则front = rear，与空队列的情况重合，会出现无法判断队列的情况。
为了区分空队列与满队列两种情况的环形队列，一般是牺牲队列的一个结点空间，当队列已有MAXQSIZE-1个数据元素时，则称队列已满的情况。如图2.3所示
空对列：front = rear
满队列: (rear+1)%MAXQSIZE = front

在这里插入图片描述

图2.3 环形队列的情况图

2.1.2 基本操作的实现

顺序队列的初始化

//6.1 队列初始化
void initSeqQueue(PSeqQueue queue)
{
assert(queue);
queue->base = (QElemType*)malloc(sizeof(QElemType) * MAXQSIZE);
if (NULL == queue->base)
{
printf("malloc fail!\n");
exit(OVERFLOW);
}
queue->front = 0;
queue->rear = 0;
}

顺序队列的销毁

//6.2 销毁队列
void destorySeqQueue(PSeqQueue queue)
{
assert(queue);
free(queue->base);
queue->base = NULL;
}

顺序队列的入队
step1 判断队列是否为满队列
step2 入队

//6.5 入队
int enSeqQueue(PSeqQueue queue, QElemType e)
{
assert(queue);
if ((queue->rear + 1) % MAXQSIZE == queue->front) //判断队满
return ERROR;
queue->base[queue->rear] = e;
queue->rear = (queue->rear + 1) % MAXQSIZE;
return SUCCESS;
}

顺序入队的出队
step1 判断队列是否为空队列
step2 出队

//6.6 出队
int deSeqQueue(PSeqQueue queue, QElemType* e)
{
assert(queue);
if (queue->front == queue->rear)//判断队空
return ERROR;
*e = queue->base[queue->front];
queue->front = (queue->front + 1) % MAXQSIZE;
return SUCCESS;
}

获取顺序队列的队头元素
step1 判断队列是否为空队列
step2 获取队头元素

//6.7 获取队头元素
int getQElemSeqQueue(PSeqQueue queue, QElemType* e)
{
assert(queue);
if (queue->front == queue->rear)//判断队空
return ERROR;
*e = queue->base[queue->front];
return SUCCESS;
}

2.2 链式表示

2.2.1 结构定义

队列的链接表示就是用一个单链表来表示队列，队列的每个元素对应链表的一个结点，结点的结构与单链表的结构一样。为了强调队头和队尾都是队列的属性，这里对队列增加一层封装，引入LinkQueue结构的定义，这样的存储的队列简称链接队列。

//链接队列的定义
//不带头结点的链表
#define SUCCESS 1
#define ERROR 0
#define OVERFLOW -1

//队列数据类型定义
typedef char QElemType;

//链接队列结点定义
struct QueueNode;
typedef struct QueueNode* PQueueNode;
struct QueueNode {
QElemType data;
PQueueNode next;
};

//链接队列类型定义
struct LinkQueue {
PQueueNode front;//队头指针
PQueueNode rear;//队尾指针
};
typedef struct LinkQueue LinkQueue;
//指向链接队列类型的指针类型
typedef struct LinkQueue* PLinkQueue;

假设queue是PLinkQueue类型的变量，则图2.4为队列的链接表示
在这里插入图片描述

图2.4 队列的链接表示

2.2.2 基本操作的实现

链接队列的初始化

//7.1 队列初始化
void initLinkQueue(PLinkQueue queue)
{
assert(queue);
queue->front = NULL;
queue->rear  = NULL;
}

链接队列的销毁

//7.2 销毁队列
void destoryLinkQueue(PLinkQueue queue)
{
assert(queue);
PQueueNode p = queue->front;
while (p)
{
PQueueNode q = p->next;
free(p);
p = q;
}
queue->front = NULL;
queue->rear  = NULL;
}

链接队列的入队

//7.4 入队
int enLinkQueue(PLinkQueue queue, QElemType e)
{
assert(queue);
//创建一个队列结点
PQueueNode newNode = (PQueueNode)malloc(sizeof(struct QueueNode));
if (NULL == newNode)
{
printf("malloc fail!n");
return ERROR;
}
newNode->data = e;
newNode->next = NULL;
if (NULL == queue->front)//判断当前队列是否为空
queue->front = newNode;
else
queue->rear->next = newNode;
queue->rear = newNode;
return SUCCESS;
}

链接队列的出队

//7.5 出队
int deLinkQueue(PLinkQueue queue, QElemType* e)
{
assert(queue);
if (NULL == queue->front)//判断空队列
return ERROR;
*e = queue->front->data;
PQueueNode p = queue->front;
queue->front = queue->front->next;
free(p);
if (NULL == queue->front) //如果出队后，队列为空，为了避免野指针，则将队尾置空
queue->rear = NULL;
return SUCCESS;
}

获取链接队列的队头元素

//7.6 获取队头元素
int getQElemLinkQueue(PLinkQueue queue, QElemType* e)
{
assert(queue);
if (NULL == queue->front)  //判断空队列
return ERROR;
*e = queue->front->data;
return SUCCESS;
}

总结

完整代码: https://gitee.com/PYSpring/data-structure/tree/master/queue_code

原文地址：https://blog.csdn.net/pyc68/article/details/145093486

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：在线图片转为excel工具
下一篇：从新手到高手的蜕变：MySQL 约束进阶全攻略

antd + VUE循环form-item的校验循环校验（多层循环）
使用a-form循环校验:v-model动态渲染的，主要是name跟v-model绑定的数据需要是一样的，校验才会生效，:name="['deviceModels',index,'paren
阅读更多2025-01-20
三十二、服务应用操作
ini文件是Initialization File 的缩写，即初始化文件，是Windows的系统配置文件所采用的存储格式。文件扩展名：配置文件名称.ini。比如项目中的配置文件是整个项目共用的。例如，
阅读更多2025-01-20
【MySQL】MySQL用户管理
MySQL中的用户，都存储在系统数据库mysql的user表中。如果用户存在，赋予权限的同时修改密码,如果该用户不存在，就是创建用户。host：表示这个用户可以从哪个主机登陆，如果是localhos
阅读更多2025-01-20
【软件测试】用例篇
【软件测试】用例篇
阅读更多2025-01-20
嵌入式知识点总结(二)-C/C++ 内存
嵌入式知识点总结(二)-C/C++内存
阅读更多2025-01-20
Spring Boot 整合 Knife4j：打造更优雅的 API 文档
在现代 Web 应用开发中，API 文档的重要性不言而喻。清晰、准确、易用的 API 文档不仅可以方便开发者理解和使用 API，还能提高团队协作效率。Knife4j 是一个基于 Swagger 的增强
阅读更多2025-01-20
linux中的docker下载镜像
重新加在文件，重启docker。
阅读更多2025-01-20
x86_64搭建ARM交叉编译工具链
>>交叉编译器中“交叉”的意思就是在一个架构上编译另外一个架构的代码，相当于两种架构“交叉”起来了。交叉编译器有很多种，我们使用Linaro出品的交叉编译器，Linaro一间非营利性质的开
阅读更多2025-01-20
elasticsearch基础
elasticsearch是一款非常强大的开源搜索引擎，具备非常多强大功能，可以帮助我们从海量数据中快速找到需要的内容例如：在github搜索代码：在电商网站搜索商品：在百度搜索答案：在打车软件搜索附
阅读更多2025-01-20
Linux中的页缓存机制
PageCache，又称pcache，中文名称为页高速缓冲存储器，简称页高缓。它是将磁盘上的数据加载到内存中，当系统需要访问这些数据时，可以直接从内存中读取，而不必每次都去读取磁盘。这种方式显著减少了
阅读更多2025-01-20