【数据结构】【线性表】一文讲完队列(附C语言源码)

server/2024/11/25 16:22:46/

队列

        • 队列的基本概念
          • 基本术语
          • 基本操作
        • 队列的顺序实现
          • 顺序队列结构体的创建
          • 顺序队列的初始化
          • 顺序队列入队
          • 顺序队列出队
          • 顺序队列存在的问题分析
          • 循环队列
          • 代码汇总
        • 队列的链式实现
          • 链式队列的创建
          • 链式队列初始化-不带头结点
          • 链式队列入队-不带头节点
          • 链式队列出队-不带头结点
          • 带头结点的链式队列各个基本操作源码

队列的基本概念

今天介绍一下线性表的另一个类型,队列。队列和栈类似,都是在操作规则上有一定要求的线性表:

  • 栈是一个只允许在一端进行插入或者删除操作的线性表;
  • 队列是一个只允许在一端插入,另一端删除的线性表。

和栈不同的是,栈的插入或删除规定在同一端进行,但队列将插入和删除分开在了两端进行。我们可以将其理解成排队打饭,先去排队的人先打到饭,自然也是先离开,因此队列遵循的是先进先出的原则。队列逻辑结构示意图如图:
![[Pasted image 20241122133855.png]]

基本术语
  • 队头:等效于排队的队头,是第一个出去的即删除端;
  • 队尾:等效于排队的队尾,是加入队伍的一端即插入端;
  • 队头元素:队伍的第一个元素;
  • 队尾元素:队伍的最后一个元素;
  • 空队列:没有一个元素的队列;
基本操作
  • 初始化队列:创建一个空队列Q
  • 销毁队列:销毁队列,释放队列Q所占用的空间
  • 入队:队列Q没有满的情况下,加入新的元素到队尾
  • 出队:队列Q没有空的情况下,删除队头元素
  • 读队头元素:队列Q没有空的情况下,获取第一个元素的数据
队列的顺序实现

顺序队列是以类似顺序表的方式实现队列,即队列各个元素的存储空间连续且顺序,其结构体的创建也与顺序表类似。

顺序队列结构体的创建

创建顺序队列有两个主要的点:一个是队列空间的创建;另一个是队列的队头与队尾指针的构建。
![[顺序队列示意图.png]]

其相关程序如下:

#define MaxSize 10//队列最大长度
typedef struct{ElemType data[MaxSize];//数组存放队列元素int front,rear;//队头指针和队尾指针
}SqQueue;//顺序队列
顺序队列的初始化

初始化主要是清除空间的残余数据,并将front和rear指针分别指向队头和队尾。具体程序如下:

void InitQueue(SqQueue &Q){//初始化队内各个元素数据for(int i=0;i<MaxSize;i++)Q.data[i]=0;Q.front=Q.rear=0;//初始化队头和队尾指针
}
顺序队列入队

入队的逻辑是在队尾插入一个新元素,然后将指针+1即可,示意图:
![[顺序队列入队示意图.png]]

我们可以看到,这里的rear一般指向空元素内存,具体程序如下:

bool EnQueue(SqQueue &Q,ElemType e){if(队列判满)return false;//队列已满,入队失败Q.datd[Q.rear]=e;//队列未满,元素入队//rear指针加一return true;//入队成功
}

在这里有些同学会有一些疑惑:

  • 队列判满为什么没有写
  • 入队完队尾指针为什么没有具体代码
    这里先不急,后续我们再讨论这个问题
顺序队列出队

出队的逻辑是将队头元素输出,然后指针加一即可,顺序队列出列示意图
![[顺序队列出列示意图.png]]

这里的front指向的都是有元素的空间,具体程序如下:

bool DeQueue(SqQueue &Q,ElemType &e){if(队列判空)return false;//队列以空,出队失败e=Q.datd[Q.front];//队列未空,元素出队//front指针加一return true;//出队成功
}

在这里,我们也出现两个问题:

  • 队列判空为什么不写
  • 出队完队头指针为什么不写具体代码
    接下来我们就来讨论一下上述问题
顺序队列存在的问题分析

在讨论上述顺序队列判空、判满以及指针加一的问题之前,我先抛出一个问题:

  • 队列的队头和队尾指针是固定不变的嘛?
    答案显示不是,入队队尾指针需要加一,同样的出队队头指针也需要加一。不知道你们发现问题没有,入队和出队的指针增长方向是一致的,对于已经分配好的静态空间来说,那经过一番出队入队的操作,其内存会形成以下现象:
    ![[顺序队列指针的增长方向.png]]

如图所示fornt和rear的增长方向一致,那么front之前的内存如何处理呢?如果任期发展下去,可能会出现front和rear都会在队尾,空队列也会成为满队列,front之前的空间变成一次性空间了:
![[顺序队列的指针窘境.png]]

显然这样的队列肯定不是一个好队列,因此我们需要如何解决这个问题,其实有人到这时候会想到顺序表或者排队,前面的每走一个,后面的就向前一步不就可以了嘛。确实也是,顺序表就是这样做的。但这无疑会给队列的基本运算带来更大的工作量。
我们需要一个方法,使其在队头和队尾指针增长方向一致的情况下,也利用到front前面的空间,这样做势必要让front回到前面的空间,将到这里,答案也呼之欲出了,那就是循环!
接下来我们就用循环队列来讲述以下如何判空和判满以及front和rear指针的变化

循环队列

将队列的头尾相接,构成循环队列,如此构建,哪怕队头和队尾指针都向一个方向增长,我们都可以让队列的每一个空间都可以利用到。
循环队列示意图:
![[循环队列示意图.png]]

解决问题的思路是构建循环队列,但我们还是要落实的具体的东西来,回归我们要解决的两个问题:

  • 队列判空和判满
  • front和rear指针增长
    我们通过循环队列先去解决队列的判空和判满问题
    伪满判断法
    观察示意图中红色表示有元素,深青色表示无元素,当rear的下一个是front时说明满队列。但这个时候其实也有人发现了,10并没有元素,这也是一个伪满队列。如果我们让10也插入元素,那么就会有rear == front。但在这里我们将rear == front作为判断空栈的条件了,为了做出区分满队列和空队列,我们牺牲一个结点空间让front == rear+1作为判断满栈的条件。
    判满条件:
  • front == rear+1
    判空条件:
  • rear == front
    长度判断法
    那有没有办法不牺牲空间的情况下去做这件事呢?那么首先我们要搞清楚其特点,从指针上看,循环队列的两个指针在队列空和队列满的时候都是一样的。那么我们应该从其他角度上去做改进,第一个想到的就是顺序表的length,当前表长。显然这个就很合适,但这个需要该队列的结构体:
#define MaxSize 10
typedef struct{ElemType data[MaxSize];int front,rear;int length;
}SqQueue;

判满条件:

  • length == MaxSize
    判空条件:
  • length == 0
    过程判断法
    我们在将视野放长一点,看一下满队列和空队列的具体情况,一个队列要满,肯定是需要通过入队这个操作;而一个队列要空则有两种情况,一个是新创建的队列,一个是通过出队使得队列变空。在了解了这一段动态区别之后,即便满队和空队的front指针和rear指针指向同一位置,也可以辨别其状态。类似的我们也需要改变其结构体用于记录其操作过程。
#define MaxSize 10
typedef struct{ElemType data[MaxSize];int front,rear;int flag;
}SqQueue;
  • flag为1时表示操作为入队
  • flag为0时表示操作为出队
  • 队列初始化时需要将flag置为0;
    判满条件:
  • front == rear && flag == 1
    判空条件:
  • front == rear && flag == 0
    上述解决了判空和判满的问题,但我们还有一个问题没解决:front和rear指针的增长问题。以往我们认为无论是出队还是入队操作我们只需要将rear或front加一即可,但一直的+必定在某个时刻指针会超限,即超过MaxSize。我们在引入循环队列之后,指针也需要做出改变,即不能超过MaxSize同时要在增长过程中不断循环。我们可以采用取余的方式实现,每次指针超限通过取余又回到范围:
front指针增长:
front=(front+1)%MaxSize;
rear指针增长:
rear=(rear+1)%MaxSize;
代码汇总

循环队列伪满队列方法:

/*顺序队列结构体创建*/
#define MaxSize 10//队列最大长度
typedef struct{int data[MaxSize];//数组存放队列元素int front,rear;//队头指针和队尾指针
}SqQueue;//顺序队列/*顺序队列初始化*/
void InitQueue(SqQueue &Q){//初始化队内各个元素数据for(int i=0;i<MaxSize;i++)Q.data[i]=0;Q.front=Q.rear=0;//初始化队头和队尾指针
}/*顺序队列入队*/
bool EnQueue(SqQueue &Q,int e){if(front==rear)//队列判满return false;//队列已满,入队失败Q.datd[Q.rear]=e;//队列未满,元素入队rear=(rear+1)%MaxSize;//rear指针加一return true;//入队成功
}/*顺序队列出队*/
bool DeQueue(SqQueue &Q,int &e){if(front==rear)//队列判空return false;//队列以空,出队失败e=Q.datd[Q.front];//队列未空,元素出队front=(front+1)%MaxSize;//front指针加一return true;//出队成功
}

循环队列队列长度方法:

/*顺序队列结构体创建*/
#define MaxSize 10//队列最大长度
typedef struct{int data[MaxSize];//数组存放队列元素int front,rear;//队头指针和队尾指针int length;
}SqQueue;//顺序队列/*顺序队列初始化*/
void InitQueue(SqQueue &Q){//初始化队内各个元素数据for(int i=0;i<MaxSize;i++)Q.data[i]=0;Q.front=Q.rear=0;//初始化队头和队尾指针Q.length=0;//初始化队列长度
}/*顺序队列入队*/
bool EnQueue(SqQueue &Q,int e){if(Q.length==MaxSize)//队列判满return false;//队列已满,入队失败Q.datd[Q.rear]=e;//队列未满,元素入队rear=(rear+1)%MaxSize;//rear指针加一Q.length=Q.length+1;//队列长度加一return true;//入队成功
}/*顺序队列出队*/
bool DeQueue(SqQueue &Q,int &e){if(Q.length==0)//队列判空return false;//队列以空,出队失败e=Q.datd[Q.front];//队列未空,元素出队front=(front+1)%MaxSize;//front指针加一Q.length=Q.length-1;return true;//出队成功
}

循环队列操作过程法:

/*顺序队列结构体创建*/
#define MaxSize 10//队列最大长度
typedef struct{int data[MaxSize];//数组存放队列元素int front,rear;//队头指针和队尾指针int flag;
}SqQueue;//顺序队列/*顺序队列初始化*/
void InitQueue(SqQueue &Q){//初始化队内各个元素数据for(int i=0;i<MaxSize;i++)Q.data[i]=0;Q.front=Q.rear=0;//初始化队头和队尾指针Q.flag=0;//初始化队列长度
}/*顺序队列入队*/
bool EnQueue(SqQueue &Q,int e){if(front==rear && Q.flag==1 )//队列判满return false;//队列已满,入队失败Q.datd[Q.rear]=e;//队列未满,元素入队rear=(rear+1)%MaxSize;//rear指针加一Q.flag=1;//队列长度加一return true;//入队成功
}/*顺序队列出队*/
bool DeQueue(SqQueue &Q,int &e){if(front==rear && Q.flag==0)//队列判空return false;//队列以空,出队失败e=Q.datd[Q.front];//队列未空,元素出队front=(front+1)%MaxSize;//front指针加一Q.flag=0;return true;//出队成功
}
队列的链式实现

类似的,队列可以仿照顺序表的物理结构存储方式实现顺序队列,我们也可以仿照链表的存储方式实现链式队列.同样的,链式队列也有带头结点和不带头结点的区分
![[链式队列.png]]

和链式栈类似,因为队列是对两端操作,带不带头结点其实差别不大,接下来我们先以不带头结点为例子进行讲解

链式队列的创建

队列对于元素本身只需要存储数据和next指针,但对于整个队列,非常重要的是队列的队头和队尾指针,因此在这里我们需要创建两个结构体,一个是元素结点的结构体,记录元素的数据和next指针,另一个是队列的结构体,记录队列的队头指针和队尾指针。

/*队列结点结构体*/
typedef struct LinkNode{ElemType datd;struct LinkNode *next;
}LinkNode;/*队列结构体*/
typedef struct {LinkNode *front,rear;
}LinkQueue;
链式队列初始化-不带头结点

因为没有头结点,同时初始化时的队列不存在元素,因此链式队列的front和rear指针总是指向NULL

bool InitQueue(LinkQueue &Q){Q.front=NULL;Q.rear=NULL;
}
链式队列入队-不带头节点

链式队列的入队主要就是指针的改变,唯一需要注意的是因为没有头结点的存在,第一个元素入队时和其他元素入队会有一点不一样:

void EnQueue(LinkQueue &Q,ElemType e){LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));//创建插入结点空间s->dada=e;//结点数据s->next=NULL;//新结点next为空//第一个元素入队需要特殊处理,头尾指针均指向第一个结点if(Q.front==NULL){Q.front=s;Q.rear=s;}else{Q.rear->next=s;//原来的尾结点指向新结点Q.rear=s;//更新队尾指针指向新结点}
}

在这里我们没有判断队满,因为链式队列的空间是动态的,除非内存空间不足,这是几乎不可能出现的。

链式队列出队-不带头结点

链式队列出队主要是修改front指针和释放结点空间,需要注意的是最后一个结点出队时的不同

bool DeQueue(LinkQueue &Q,ElemType &e){if(Q.front==NULL)//判空return false;//空队列,出队失败LinkNode *s=Q.front;//暂存出队结点e=s->data;//返回出队元素数据Q.front=s->next;//更新队头指针//最后一个结点出队特殊处理if(Q.rear==s){Q.front=NULL;Q.rear=NULL;}free(s);//释放空间return true;//出队成功
}

通过上述的基本操作我们可以看出来,没有头结点的链式队列在空间上可以节省一个结点的内存,但在出队入队的操作上,需要对第一个结点特殊处理,如果是有头结点则不需要.

带头结点的链式队列各个基本操作源码
/*队列结点结构体*/
typedef struct LinkNode{ElemType datd;struct LinkNode *next;
}LinkNode;/*队列结构体*/
typedef struct {LinkNode *front,rear;
}LinkQueue;/*有头结点链式队列初始化*/
bool InitQueue(LinkQueue &Q){//头 尾指针都指向头结点Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));//创建头结点并初始化头尾指针Q.front->next=NULL;//初始化头结点的next指向空
}/*有头结点链式队列入队*/
void EnQueue(LinkQueue &Q,ElemType e){LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));//创建插入结点空间s->dada=e;//结点数据s->next=NULL;//新结点next为空Q.rear->next=s;//原来的尾结点指向新结点Q.rear=s;//更新队尾指针指向新结点
}/*有头结点链式队列出队*/
bool DeQueue(LinkQueue &Q,ElemType &e){if(Q.front==NULL)//判空return false;//空队列,出队失败LinkNode *s=Q.front;//暂存出队结点e=s->data;//返回出队元素数据Q.front->next=s->next;//更新头结点指针//最后一个结点出队特殊处理if(Q.rear==s)Q.rear=Q.front;free(s);//释放空间return true;//出队成功
}

http://www.ppmy.cn/server/144839.html

相关文章

【Pytest+Yaml+Allure】实现接口自动化测试框架

一、框架思想 requestsyamlpytestallure实现接口自动化框架。结合数据驱动和分层思想&#xff0c;将代码与数据分离&#xff0c;易维护&#xff0c;易上手。使用yaml编写编写测试用例&#xff0c;利用requests库发送请求&#xff0c;使用pytest管理用例&#xff0c;allure生成…

在ubuntu中查看csv

在 Ubuntu 中查看 CSV 文件的内容有多种方法。以下是一些常用的方法&#xff1a; 使用命令行工具 cat 命令 如果文件不大&#xff0c;可以使用 cat 命令快速查看文件内容&#xff1a; cat 10_11_query.csvless 命令 对于较大的文件&#xff0c;less 是一个更好的选择&#xf…

高新技术行业中的知识管理:关键性、挑战、策略及工具应用

知识管理的关键性 在瞬息万变的信息时代&#xff0c;知识已成为高新技术行业的核心竞争要素。知识管理&#xff0c;这一旨在高效组织、整合并应用企业内外部知识资源的管理策略&#xff0c;对于推动高新技术企业的持续创新与发展至关重要。它不仅能够激发研发团队的创造力&…

【数据结构】—— 线索二叉树

引入 我们现在提倡节约型杜会&#xff0c; 一切都应该节约为本。对待我们的程序当然也不例外&#xff0c;能不浪费的时间或空间&#xff0c;都应该考虑节省。我们再观察团下图的二叉树&#xff08;链式存储结构)&#xff0c;会发现指针域并不是都充分的利用了&#xff0c;有许…

【创建型设计模式】单例模式

【创建型设计模式】单例模式 这篇博客接下来几篇都将阐述设计模式相关内容。 接下来的顺序大概是&#xff1a;单例模式、工厂方法模式、抽象工厂模式、建造者模式、原型模式。 一、什么是单例模式 单例模式是一种创建型设计模式&#xff0c;它保证一个类仅有一个实例&#…

Kafka日志索引详解以及生产常见问题分析与总结

文章目录 一、Kafka的Log日志梳理1.1、Topic下的消息如何存储1.1.1、log文件追加记录所有消息1.1.2、index和timeindex加速读取log消息日志 1.2、文件清理机制1.2.1、如何判断哪些日志文件过期了1.2.2、过期的日志文件如何处理 1.3、Kafka的文件高效读写机制1.3.1、Kafka的文件…

XML文件(超详细):XML文件概念、作用、写法、如何用程序解析XML、写入XML、dom4j框架、DTD文档、schema文档

目录 1、什么是XML文件&#xff1f;和properties属性文件有什么区别&#xff1f;和txt文本文件有什么区别&#xff1f; 2、XML文件的用途 3、XML的格式 4、如何解析XML文件 5、如何写入XML文件 6、约束XML的书写格式 6.1 DTD文档-约束书写格式&#xff0c;但是不能约束具…

前端安全问题汇总

1、Nginx相关 1.1、升级Nginx版本 及时升级Nginx版本&#xff0c;新版本包含对旧版本的漏洞修复 1.2、版本号隐藏 版本号的显示也被扫描软件识为一种不安全的行为 2、具有不安全、不正确或缺少SameSite属性的Cookie 可以直接在Nginx下设置 location / {add_header Set-C…