网站收录不好的原因,做游戏网站有几个要素,建个人网站,有哪些设计网站队列 队列的基本概念基本术语基本操作 队列的顺序实现顺序队列结构体的创建顺序队列的初始化顺序队列入队顺序队列出队顺序队列存在的问题分析循环队列代码汇总 队列的链式实现链式队列的创建链式队列初始化-不带头结点链式队列入队-不带头节点链式队列出队-不带头结点带头结点… 队列 队列的基本概念基本术语基本操作 队列的顺序实现顺序队列结构体的创建顺序队列的初始化顺序队列入队顺序队列出队顺序队列存在的问题分析循环队列代码汇总 队列的链式实现链式队列的创建链式队列初始化-不带头结点链式队列入队-不带头节点链式队列出队-不带头结点带头结点的链式队列各个基本操作源码 队列的基本概念
今天介绍一下线性表的另一个类型队列。队列和栈类似都是在操作规则上有一定要求的线性表
栈是一个只允许在一端进行插入或者删除操作的线性表队列是一个只允许在一端插入另一端删除的线性表。
和栈不同的是栈的插入或删除规定在同一端进行但队列将插入和删除分开在了两端进行。我们可以将其理解成排队打饭先去排队的人先打到饭自然也是先离开因此队列遵循的是先进先出的原则。队列逻辑结构示意图如图
基本术语
队头等效于排队的队头是第一个出去的即删除端队尾等效于排队的队尾是加入队伍的一端即插入端队头元素队伍的第一个元素队尾元素队伍的最后一个元素空队列没有一个元素的队列
基本操作
初始化队列创建一个空队列Q销毁队列销毁队列释放队列Q所占用的空间入队队列Q没有满的情况下加入新的元素到队尾出队队列Q没有空的情况下删除队头元素读队头元素队列Q没有空的情况下获取第一个元素的数据
队列的顺序实现
顺序队列是以类似顺序表的方式实现队列即队列各个元素的存储空间连续且顺序其结构体的创建也与顺序表类似。
顺序队列结构体的创建
创建顺序队列有两个主要的点一个是队列空间的创建另一个是队列的队头与队尾指针的构建。
其相关程序如下
#define MaxSize 10//队列最大长度
typedef struct{ElemType data[MaxSize];//数组存放队列元素int front,rear;//队头指针和队尾指针
}SqQueue;//顺序队列顺序队列的初始化
初始化主要是清除空间的残余数据并将front和rear指针分别指向队头和队尾。具体程序如下
void InitQueue(SqQueue Q){//初始化队内各个元素数据for(int i0;iMaxSize;i)Q.data[i]0;Q.frontQ.rear0;//初始化队头和队尾指针
}顺序队列入队
入队的逻辑是在队尾插入一个新元素然后将指针1即可示意图
我们可以看到这里的rear一般指向空元素内存具体程序如下
bool EnQueue(SqQueue Q,ElemType e){if(队列判满)return false;//队列已满入队失败Q.datd[Q.rear]e;//队列未满元素入队//rear指针加一return true;//入队成功
}在这里有些同学会有一些疑惑
队列判满为什么没有写入队完队尾指针为什么没有具体代码 这里先不急后续我们再讨论这个问题
顺序队列出队
出队的逻辑是将队头元素输出然后指针加一即可顺序队列出列示意图
这里的front指向的都是有元素的空间具体程序如下
bool DeQueue(SqQueue Q,ElemType e){if(队列判空)return false;//队列以空出队失败eQ.datd[Q.front];//队列未空元素出队//front指针加一return true;//出队成功
}在这里我们也出现两个问题
队列判空为什么不写出队完队头指针为什么不写具体代码 接下来我们就来讨论一下上述问题
顺序队列存在的问题分析
在讨论上述顺序队列判空、判满以及指针加一的问题之前我先抛出一个问题
队列的队头和队尾指针是固定不变的嘛 答案显示不是入队队尾指针需要加一同样的出队队头指针也需要加一。不知道你们发现问题没有入队和出队的指针增长方向是一致的对于已经分配好的静态空间来说那经过一番出队入队的操作其内存会形成以下现象
如图所示fornt和rear的增长方向一致那么front之前的内存如何处理呢如果任期发展下去可能会出现front和rear都会在队尾空队列也会成为满队列front之前的空间变成一次性空间了
显然这样的队列肯定不是一个好队列因此我们需要如何解决这个问题其实有人到这时候会想到顺序表或者排队前面的每走一个后面的就向前一步不就可以了嘛。确实也是顺序表就是这样做的。但这无疑会给队列的基本运算带来更大的工作量。 我们需要一个方法使其在队头和队尾指针增长方向一致的情况下也利用到front前面的空间这样做势必要让front回到前面的空间将到这里答案也呼之欲出了那就是循环 接下来我们就用循环队列来讲述以下如何判空和判满以及front和rear指针的变化
循环队列
将队列的头尾相接构成循环队列如此构建哪怕队头和队尾指针都向一个方向增长我们都可以让队列的每一个空间都可以利用到。 循环队列示意图
解决问题的思路是构建循环队列但我们还是要落实的具体的东西来回归我们要解决的两个问题
队列判空和判满front和rear指针增长 我们通过循环队列先去解决队列的判空和判满问题 伪满判断法 观察示意图中红色表示有元素深青色表示无元素当rear的下一个是front时说明满队列。但这个时候其实也有人发现了10并没有元素这也是一个伪满队列。如果我们让10也插入元素那么就会有rear front。但在这里我们将rear front作为判断空栈的条件了为了做出区分满队列和空队列我们牺牲一个结点空间让front rear1作为判断满栈的条件。 判满条件front rear1 判空条件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(front1)%MaxSize;
rear指针增长
rear(rear1)%MaxSize;代码汇总
循环队列伪满队列方法
/*顺序队列结构体创建*/
#define MaxSize 10//队列最大长度
typedef struct{int data[MaxSize];//数组存放队列元素int front,rear;//队头指针和队尾指针
}SqQueue;//顺序队列/*顺序队列初始化*/
void InitQueue(SqQueue Q){//初始化队内各个元素数据for(int i0;iMaxSize;i)Q.data[i]0;Q.frontQ.rear0;//初始化队头和队尾指针
}/*顺序队列入队*/
bool EnQueue(SqQueue Q,int e){if(frontrear)//队列判满return false;//队列已满入队失败Q.datd[Q.rear]e;//队列未满元素入队rear(rear1)%MaxSize;//rear指针加一return true;//入队成功
}/*顺序队列出队*/
bool DeQueue(SqQueue Q,int e){if(frontrear)//队列判空return false;//队列以空出队失败eQ.datd[Q.front];//队列未空元素出队front(front1)%MaxSize;//front指针加一return true;//出队成功
}循环队列队列长度方法
/*顺序队列结构体创建*/
#define MaxSize 10//队列最大长度
typedef struct{int data[MaxSize];//数组存放队列元素int front,rear;//队头指针和队尾指针int length
}SqQueue;//顺序队列/*顺序队列初始化*/
void InitQueue(SqQueue Q){//初始化队内各个元素数据for(int i0;iMaxSize;i)Q.data[i]0;Q.frontQ.rear0;//初始化队头和队尾指针Q.length0//初始化队列长度
}/*顺序队列入队*/
bool EnQueue(SqQueue Q,int e){if(Q.lengthMaxSize)//队列判满return false;//队列已满入队失败Q.datd[Q.rear]e;//队列未满元素入队rear(rear1)%MaxSize;//rear指针加一Q.lengthQ.length1;//队列长度加一return true;//入队成功
}/*顺序队列出队*/
bool DeQueue(SqQueue Q,int e){if(Q.length0)//队列判空return false;//队列以空出队失败eQ.datd[Q.front];//队列未空元素出队front(front1)%MaxSize;//front指针加一Q.lengthQ.length-1;return true;//出队成功
}循环队列操作过程法
/*顺序队列结构体创建*/
#define MaxSize 10//队列最大长度
typedef struct{int data[MaxSize];//数组存放队列元素int front,rear;//队头指针和队尾指针int flag
}SqQueue;//顺序队列/*顺序队列初始化*/
void InitQueue(SqQueue Q){//初始化队内各个元素数据for(int i0;iMaxSize;i)Q.data[i]0;Q.frontQ.rear0;//初始化队头和队尾指针Q.flag0//初始化队列长度
}/*顺序队列入队*/
bool EnQueue(SqQueue Q,int e){if(frontrear Q.flag1 )//队列判满return false;//队列已满入队失败Q.datd[Q.rear]e;//队列未满元素入队rear(rear1)%MaxSize;//rear指针加一Q.flag1;//队列长度加一return true;//入队成功
}/*顺序队列出队*/
bool DeQueue(SqQueue Q,int e){if(frontrear Q.flag0)//队列判空return false;//队列以空出队失败eQ.datd[Q.front];//队列未空元素出队front(front1)%MaxSize;//front指针加一Q.flag0;return true;//出队成功
}队列的链式实现
类似的队列可以仿照顺序表的物理结构存储方式实现顺序队列我们也可以仿照链表的存储方式实现链式队列.同样的链式队列也有带头结点和不带头结点的区分
和链式栈类似因为队列是对两端操作带不带头结点其实差别不大接下来我们先以不带头结点为例子进行讲解
链式队列的创建
队列对于元素本身只需要存储数据和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.frontNULL;Q.rearNULL;
}链式队列入队-不带头节点
链式队列的入队主要就是指针的改变唯一需要注意的是因为没有头结点的存在第一个元素入队时和其他元素入队会有一点不一样
void EnQueue(LinkQueue Q,ElemType e){LinkNode *s(LinkNode*)malloc(sizeof(LinkNode));//创建插入结点空间s-dadae;//结点数据s-nextNULL;//新结点next为空//第一个元素入队需要特殊处理头尾指针均指向第一个结点if(Q.frontNULL){Q.fronts;Q.rears;}else{Q.rear-nexts;//原来的尾结点指向新结点Q.rears;//更新队尾指针指向新结点}
}在这里我们没有判断队满因为链式队列的空间是动态的除非内存空间不足这是几乎不可能出现的。
链式队列出队-不带头结点
链式队列出队主要是修改front指针和释放结点空间需要注意的是最后一个结点出队时的不同
bool DeQueue(LinkQueue Q,ElemType e){if(Q.frontNULL)//判空return false;//空队列出队失败LinkNode *sQ.front;//暂存出队结点es-data;//返回出队元素数据Q.fronts-next;//更新队头指针//最后一个结点出队特殊处理if(Q.rears){Q.frontNULL;Q.rearNULL;}free(s);//释放空间return true;//出队成功
}通过上述的基本操作我们可以看出来没有头结点的链式队列在空间上可以节省一个结点的内存但在出队入队的操作上需要对第一个结点特殊处理如果是有头结点则不需要.
带头结点的链式队列各个基本操作源码
/*队列结点结构体*/
typedef struct LinkNode{ElemType datd;struct LinkNode *next;
}LinkNode;/*队列结构体*/
typedef struct {LinkNode *front,rear;
}LinkQueue;/*有头结点链式队列初始化*/
bool InitQueue(LinkQueue Q){//头 尾指针都指向头结点Q.frontQ.rear(LinkNode*)malloc(sizeof(LinkNode));//创建头结点并初始化头尾指针Q.front-nextNULL;//初始化头结点的next指向空
}/*有头结点链式队列入队*/
void EnQueue(LinkQueue Q,ElemType e){LinkNode *s(LinkNode*)malloc(sizeof(LinkNode));//创建插入结点空间s-dadae;//结点数据s-nextNULL;//新结点next为空Q.rear-nexts;//原来的尾结点指向新结点Q.rears;//更新队尾指针指向新结点
}/*有头结点链式队列出队*/
bool DeQueue(LinkQueue Q,ElemType e){if(Q.frontNULL)//判空return false;//空队列出队失败LinkNode *sQ.front;//暂存出队结点es-data;//返回出队元素数据Q.front-nexts-next;//更新头结点指针//最后一个结点出队特殊处理if(Q.rears)Q.rearQ.front;free(s);//释放空间return true;//出队成功
}
