-
王道课后习题3.2.1:循环队列设置tag标志域判断队满队空
2019-08-29 09:45:18循环队列设置tag标志域判断队满队空 算法思想: tag等于0的情况下,若因删除导致Q.Rear==Q.Front则为队空 tag等于1的情况下,若因插入导致Q.Rear==Q.Front则为队满 核心代码: //tag等于0的情况下,若因删除...题目描述:
循环队列设置tag标志域判断队满队空
算法思想:
tag等于0的情况下,若因删除导致Q.Rear==Q.Front则为队空
tag等于1的情况下,若因插入导致Q.Rear==Q.Front则为队满
核心代码:
//tag等于0的情况下,若因删除导致Q.Rear==Q.Front则为队空 //tag等于1的情况下,若因插入导致Q.Rear==Q.Front则为队满 bool EnQueue(Queue &Q,int x)//,int tag) { //if((Q.Rear%MaxSize==Q.Front)&&tag==1) //这里不需要再%MaxSize if((Q.Rear==Q.Front)&&tag==1) return false; Q.data[Rear]=x; Q.Rear=(Q.Rear+1)%MaxSize; Q.tag=1;//可能队满 //这里其实挺有意思的,只有当同时满足Q.Rear==Q.Front)&&tag==1的时候才会return false //只要你入队了,你就有可能队满 // if(Q.Rear==Q.Front) // tag=1; return true; } bool DeQueue(Queue &Q,int &x)//,int tag) { if(Q.Rear==Q.Front&&tag==0) return false; x=Q.data[Front]; Front=(Front+1)%MaxSize; Q.tag=0;//可能队空 //只要你出队了,你就有可能队空 return true; }
-
循环队列满队条件
2016-09-03 19:25:37严蔚敏的数据结构书上63页倒数第二段定义了判定队列空间是空还是满的方法:少用一个元素空间,判定队列呈“满”状态的标志是“队列头指针在队列尾指针的下一位置上(指环状的下一位置)” 意思就是说,循环队列留...严蔚敏的数据结构书上63页倒数第二段定义了判定队列空间是空还是满的方法:少用一个元素空间,判定队列呈“满”状态的标志是“队列头指针在队列尾指针的下一位置上(指环状的下一位置)”
意思就是说,循环队列留了一个元素空间,即当maxsize=100的时候,实际能存的数据只有99个,留一个不存的目的就是用来区分队列空还是满。因为空的时候q.rear=q.front,而满的时候就变成了(q.rear+1)%maxsize=q.front。 如果判定条件是q.rear%maxsize=q.front,就是判定头指针和尾指针是否在同一个位置上 如果判定条件是(q.rear+1)%maxsize=q.front,就是判定头指针在尾指针的下一个位置上
其他还有设置标记位的方法
-
用标志域表示队空队满状态的循环队列的综合操作
2015-05-18 17:31:34要求循环队列不损失一个空间全部都得到利用,设置一个标志域tag,以0和1来区分当队头与队尾指针相同时队列状态的空和满,试编写与此结构相对应的入队和出队操作。 -
如何采用设置标志的方法来区分循环队列的满和空
2016-08-10 21:33:12设立一个标志位,比如说是flag 最开始时队列为空,设flag=0 当入队的时候让flag=1 出队的时候flag=0 然后再加上判断队头队尾指针是否重合 重合,且flag=0,则为空 重合且flag=1,则为满设立一个标志位,比如说是flag 最开始时队列为空,设flag=0 当入队的时候让flag=1 出队的时候flag=0 然后再加上判断队头队尾指针是否重合 重合,且flag=0,则为空 重合且flag=1,则为满
-
循环队列队满的判断
2018-03-23 21:06:28第一种方法是设置一个标志量flag,当front==rear且flag=0...接下来我们重点讨论第二种方法,由于rear可能比front大,也可能是比front小,所以尽管他们只相差一个位置时候就是满的情况,但是也可能说是相差整整一圈。所以第一种方法是设置一个标志量flag,当front==rear且flag=0时为空,当front==rear且flag=1时队列为满;
第二种方法是我们修改条件,保留一个元素空间,也就是说,数组中还有一个空闲单元时,我们就认为这个队列已经满了。
接下来我们重点讨论第二种方法,由于rear可能比front大,也可能是比front小,所以尽管他们只相差一个位置时候就是满的情况,但是也可能说是相差整整一圈。所以若队列最大尺寸为QueueSize,那么队列满的条件就是(rear+1)%QueueSize==front(这里取模“%”目的就是为了整合rear与front大小为一个问题)。比如图一所示,QueueSize=5,front=0,rear=4,根据公式(4+1)%5=0,所以此时队列满。
图一通用计算队列长度公式:
(rear-front+QueueSize)%QueueSize/*循环队列求长度代码,返回Q元素个数*/ int QueueLength() { return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; }
/*循环队列求长度代码,返回Q元素个数*/ int QueueLength() { return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; } /*循环队列的入队列操作,若队列未满则插入元素e为Q新的队尾元素*/ Status EnQueue(SqQueue *Q,QElemType e) { if((Q->rear+1)%MAXSIZE==Q->front)/*队列满判断*/ return ERROR; Q-date[Q->rear]=e; /*将元素e赋值给队尾*/ Q-rear=(Q->rear+1)%MAXSIZE; /*rear指针向后移一位置,若到最后则转到数组头部*/ return OK; } /*循环队列的出队列操作,若队列不空,则删除Q中队头元素,用e返回其值*/ Status DeQueue(SqQueue *Q,QElemType e) { if(Q->front==Q->rear) /*队列空判断*/ return ERROR; *e=Q->data[Q->front]; /*将队头元素赋值给e*/ Q->front=(Q->front+1)%MAXSIZE; /*front指针向后移一位置,若到最后则转到数组头部*/ return OK }
-
3.7带标志的循环队列的插入删除操作
2020-08-25 21:17:01题目:假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag,以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入(EnQueue)和删除... -
循环队列的两种判断队列空和满的条件
2020-11-19 22:52:02队列满时:(rear+1)%maxSize= =front 不少一个存储位置时:加一个标志flag或者计数的count 入队时flag=true 出队时flag=false 队满:rear= =front&flag 队空:rear= =front&!flag 开始时count=0 入队时:... -
java循环队列队满_循环队列的队空与队满的条件
2021-03-12 23:17:54为了方便起见,约定:初始化建空队时,令front=rear=0,当队空时:front=rear当队...(2)少用一个元素空间,约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即:队空时: front=rea... -
标志位法实现循环队列
2019-09-06 15:12:50但是在判断循环队列空和满这两种状态任然存在问题,因为对于一个循环队列,不做任何判空和判满的机制。判空和判满的条件都是:q->rear == q->front。带来的问题就是当出现上述条件时不能区分循环队列到底是空... -
通过设置标志位tag判断队空队满的顺序存储的循环队列
2016-11-04 10:52:33首先我们定义一个具有基本操作方法的Queue类,在这个类中我们设置了一个bool型的变量tag,通过判断tag的值来判断队列是否为空、是否为满。具体是:rear==front&&!tag为空,rear==front&... -
栈和队列4--循环队列(标志位)
2019-12-28 16:29:49解决假溢出问题,1,少用一个元素,判断满的条件:(Q.rear+1)% MaxSize==Q.front 2....#define MaxSize 10//循环队列最大长度 using namespace std; typedef int QElemType;//数据类型 typedef st... -
带标志域的循环队列的出队和入队算法
2020-05-10 19:56:28若希望循环队列中的元素都能得到利用,则需设置一个标志域tag,并以tag的值为0或1来区别头指针front和尾指针rear相同时队列状态是“空”还是“满”。 进队时置tag为1,出队时置tag为0(因为只有入队操作可能导致队... -
数据结构:循环队列(一)设置一个标志域后的入队列和出队列的算法
2014-04-26 00:06:09如果希望循环队列中的元素都能得到利用,则需设置一个标志域tag,并以tag的值为0或1来区分,尾指针和头指针值相同时的队列状态是"空"还是"满"。试编写与此结构相应的入队列和出队列的算法。 本题的循环队列... -
循环队列的入队列和出队列
2020-04-14 14:55:10如果希望循环队列中的元素都能得到利用,则需要设置一个标志域 tag,并以 tag 的值为 0 或 1 来区分,尾指针和头指针相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法。 #include <... -
BJFU_数据结构习题_247附加判定标志的循环队列的基本操作
2019-10-26 12:48:06假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag,以tag== 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)... -
判断一个循环队列是满还是空的方法:
2021-04-09 08:48:41所以,如果在tag = 1后,Q.front = Q.rare,则说明是因为插队而引起的,所以是因为队列满了;反之,tag = 0时,Q.front = Q.rare,则说明是因为出队引起的,由此判断是队列空了;方法二:用两个定义区分对列是满的还是... -
判断循环队列是满还是空
2013-10-28 00:06:20判断一个循环队列是满还是空的方法: 方法一:设置一个标志tag,当每一次入队的时候,令tag = 1;当出队的时候,tag = 0;所以,如果在tag = 1后,Q.front = Q.rare,则说明是因为插队而引起的,所以是因为队列满了;... -
循环队列——队列的顺序表示和实现
2020-02-28 17:51:49其二是少用一个元素空间,约定以“队列头指针在队列尾指针的下一位置(指环状的下一位置)上”作为队列呈“满”状态的标志。 从上述分析可见,在C语言中不能用动态分配的一维数组来实现循环队列。如果用户的应用程序中... -
循环队列 设置标志tag判断队列的满和空状态
2020-10-12 21:35:24#include <iostream> #include<bits/stdc++.h> using namespace std; typedef struct{ int *data; int front; int rear; int tag; }qu; void init(qu &q){ q.data=new int[3];...if(q.tag==1& -
java循环队列的实现
2018-11-15 10:33:05package impl; import Interface.IQueue; /** * 循环队列 * &lt;p&... * 情况1.... * 情况2.... 作为队列满的标志 * * @param &lt;T&gt; */ public class Cyc... -
循环队列
2020-07-10 13:21:51循环队列 队列初始为空时:使front=rear,front指向当前队头元素,rear指向队尾元素的下一个位置 这会造成一个问题:当队满的时候front也等于rear,这会导致无法判断是空还是满。 解决方案1 加一个flag标志,flagrear... -
循环队列的队空与队满的条件
2014-07-19 00:29:15为了方便起见,约定:初始化建空队时,令 front=rear=0, 当队空时:front=rear ... (1)另设一个标志位以区别队列是空还是满。 (2)少用一个元素空间,约定以“队列头指针front在队尾指针rear的下一个位 -
循环队列的判断满、空的三种方法以及具体代码实现(数组实现)
2013-09-12 12:29:00由于循环队列的特殊性,当队首指针=队尾指针的时候,既可能表示空也可能表示满,所以需要另加一个判断位。 我现在介绍的循环队列判断满空的三种方法分别是:1.设标志位法 2.预留一位法; 3.预存长度法(顾名思义,...
收藏数
122
精华内容
48