-
循环队列的两种判断队列空和满的条件
2020-11-19 22:52:02少一个存储位置的 队列为空时:rear= =front 队列满时:(rear+1)%maxSize= =front 不少一个存储位置时:加一个标志flag或者计数的count 入队时flag=true 出队时flag=false 队满:rear= =front&flag 队空:rear...少一个存储位置的
队列为空时:rear= =front
队列满时:(rear+1)%maxSize= =front不少一个存储位置时:加一个标志flag或者计数的count
入队时flag=true
出队时flag=false
队满:rear= =front&flag
队空:rear= =front&!flag
开始时count=0
入队时:count++
出队是:count–
队满:rear ==front &&count=maxsize
队空:rear ==front&&count=0; -
循环队列队满的判断
2018-03-23 21:06:28第二种方法是我们修改条件,保留一个元素空间,也就是说,数组中还有一个空闲单元时,我们就认为这个队列已经满了。接下来我们重点讨论第二种方法,由于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种方法
2020-02-14 19:32:18一.少用一个存储位置 第一种情况: ...比如下图有下标了,当队列满时,显然条件就不能判断了,就要用到另一种判断。 第二种情况: 当队列为空时条件:rear == front 当队列满时条件为:(rear+1)...一.少用一个存储位置
第一种情况:
当队列为空时条件:rear == front当队列满时条件为:rear+1 == front
上述方式对于上述图是适用的,但如果出现了有下标标识,上述判断条件就不适用了。比如下图有下标了,当队列满时,显然条件就不能判断了,就要用到另一种判断。
第二种情况:
当队列为空时条件:rear == front
当队列满时条件为:(rear+1)% maxsize == front
二.设置一个标记位
设置初始标记: boolean flag=false当入队列时,让rear往后移动,让flag=true
当出队列时,让front往后移动,让flag=false当队列为空时: rear == front && flag==false
当队列为满时: rear == front && flag == true
三.计数count——队列中有效元素个数
队列为空时,count == 0当有元素入队时,count++,当count和队列的maxsize相等时,代表队列已满
-
循环队列判断满空的两种方法(C#)
2019-10-20 20:06:46问题描述:循环队列为空条件是 ...方法一:把数组的前端和后端连接起来,形成一个循环的顺序表,即把存储队列元素的表从逻辑上看成一个环。循环队列的队头指针和队尾指针初始化时都置0,队满条件:(rear+1)%MaxSiz...问题描述:循环队列为空条件是 rear=front 。如果进队元素的速度快于出队元素的速度,队尾指针很快就赶上了队首指针,此时可以看出循环队列的队满条件也为 rear=front。怎样区分这两者之间的差别呢?
解决方案:
方法一:把数组的前端和后端连接起来,形成一个循环的顺序表,即把存储队列元素的表从逻辑上看成一个环。循环队列的队头指针和队尾指针初始化时都置0,队满条件:(rear+1)%MaxSize=front,队空条件:rear=front。
方法二:用一个标志tag标识队列可能空(0)或可能满(1),加上front==rear作为队满或队空的条件。Tag初始值置为0,每当入队成功,tag=1,每当出队成功,tag=0。当front=rear&&tag=1时,表示在入队操作后front=rear,此时队满,同理,front=rear&&tag=0时则表示队空。
代码实现:
namespace ConsoleApplication
{
class sqQueueClass
{
const int MaxSize = 100;
public string[] data;
public int front, rear;
public int tag = 0;
public sqQueueClass()
{
data = new string[MaxSize];
front = rear = -1;
}
public bool QueueEmpty()
{
return (front == rear && tag == 0);
}
public bool enQueue(string e)
{
if (front == rear && tag == 1)
return false;
rear = (rear + 1) % MaxSize;
data[rear] = e;
tag = 1;
return true;
}
public bool deQueue(ref string e)
{
if (front == rear && tag == 0)
return false;
front = (front + 1) % MaxSize;
e = data[front];
tag = 0;
return true;
}
}
}
namespace ConsoleApplication
{
class Program
{
static void Main(string[] args)
{
sqQueueClass L1 = new sqQueueClass();
bool pandan = false;
pandan = L1.enQueue(“3”);
Console.WriteLine(pandan);
pandan = L1.enQueue(“5”);
Console.WriteLine(pandan);
pandan = L1.enQueue(“8”);
Console.WriteLine(pandan);
pandan = L1.enQueue(“4”);
Console.WriteLine(pandan);
pandan = L1.enQueue(“0”);
Console.WriteLine(pandan);
string e = “”;
pandan = L1.deQueue(ref e);
Console.WriteLine(pandan);
Console.WriteLine(e);
Console.ReadKey();
}
}
}
运行结果如图示:比较:方法一判断条件较为简单,但浪费了一个存储空间;方法二能够充分利用存储空间,但在进行出队入队操作时,每次都需要对tag进行重新定义且判断条件较为复杂。
总结:循环队列在实现入队出队操作时,应注意算法实现顺序,入队时先判断是不是队满,出队时先判断是不是队空,然后再进行相应的入队出队操作。 -
循环队列以及full/empty条件的判断
2017-04-12 19:22:31为了方便起见,约定:初始化建空队时,令 front=rear=0, 当队空时:front=rear 当队满时:front=rear 亦成立 ... (2)少用一个元素空间,约定以“队列头指针front在队尾指针rear的下一个位 -
循环队列的队空与队满的条件
2014-07-19 00:29:15为了方便起见,约定:初始化建空队时,令 front=rear=0, 当队空时:front=rear 当队满时:front=rear 亦成立 ... (2)少用一个元素空间,约定以“队列头指针front在队尾指针rear的下一个位 -
循环队列判断队空和队满_计软考研双日练 | 如何判循环队列队满队空?
2020-12-18 19:59:37☝☝☝软件工程考研独家平台撰稿| 康康哥编辑| 丽丽姐本文由懂计算机、软件工程的博士师哥原创双日练:NO.20200922循环队列放在一维数组A[0…M-1]中,end1指向队头元素,end2指向队尾元素的后一个位置。假设队列两端... -
循环队列
2017-07-10 20:25:37为了解决顺序队列中的“假溢出”现象,充分利用数组的存储空间,可将顺序队列的头尾相连,构成一个循环队列。循环队列一般都是用数组来实现的。 在循环队列中,front和rear都是可以移动的。 当队列为空或满时,... -
循环队列的数组实现()
2020-09-08 18:10:30理论知识 由于顺序存储的队列会...1.牺牲一个存储单元,入队的时候将队头指针在队尾指针的下一位置最为队列满的条件 这是判断队空的条件仍然是:Q.rear = Q.front 但是判断队满的条件变为:(Q.rear+1)%MAXSIZE = Q.fr -
循环队列的常见操作
2018-04-22 19:25:15与栈相比,队列我个人感觉简单一些,不过对于一般的队列,都是循环队列,这是为了防止内存的浪费,使为队列分配的内存可以循环使用,而且一般动态分配一个长度为n的循环队列的话,真正用来储存数据的只有n-1,因为要... -
循环队列和链队列
2016-06-19 16:12:01队列是一种先进先出的线性表,允许出队的一端叫做队头,允许进队的一端叫做队尾。 1.循环队列是基于数组实现的,front指向队头元素,...当队列满时,保留一个元素。由于是循环队列,所以rear可能比front大,也可能比 -
循环队列FIFO
2020-07-04 11:55:42为充分利用向量空间,克服顺序存储结构的"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来... -
C语言 队列(循环队列)实现
2017-07-09 16:11:33循环队列:头尾相接的顺序存储成为循环队列满队列的判断 办法一:设置一个标志flag,当front == rear 且 flag = 0 为空队列当 front == rear 且 flag = 1 为满队列(烦琐) 办法二: 满队列时,数组中还存在一个... -
Java数组实现循环队列
2020-11-21 21:38:29这样做的原因是为了区分开判断 循环队列满 和 空 的条件,避免两个条件的判断方式重复。 首先我们需要两个指针 head 和 tail 来指向头尾两个元素,head 和 tail 我们约定初始化为0,head指向头元素,t. -
尚硅谷Java数据结构学习记录3-循环队列的实现
2020-02-29 17:40:48需要注意的地方是循环队列的初始条件和判断队列满的条件 初始条件是front = rear = 0 队列为空的条件 front = rear 队列满的条件 (rear+1)%maxSize = front 空出一个空间 队列中元素的个数 (rear + maxSize - ... -
C++ 顺序循环队列和链队列的基本操作
2020-11-05 21:43:54通过该实验,使学生理解链队列的构造特点并灵活应用,掌握链队基本操作的编程实现,认识栈是在一端进行插入,在另一端进行删除集中操作的线性结构,掌握队列的“先入先出”操作特点,知道判断队列空和满的条件,... -
算法与数据结构学习 队列(尚未使用数组手动实现队列和循环队列)
2020-08-22 10:16:54用数组实现的非循环队列,判断队列满的标准是tail == n,队空的判断条件是head == tail 用数组实现队列的时候需要在新元素入队的时候进行数据搬移操作。 (队列的实现暂时未做) 2. 特殊的队列:循环队列 检测... -
大话数据结构 队列10:数组循环队列
2021-01-04 21:25:47满队列的判断比较复杂:如果也是用尾游标等于头游标则出现与空队列相同的判断条件,此时可以额外增加判断标志位,还有第二种判断方法,就是判断尾游标和头游标值差一个元素的时候。 代码 #include "stdio.h" #... -
循环队列(C语言简单实现)
2020-10-16 17:59:11循环队列 定义 把队列中,头尾相接的顺序存储结构成为循环队列。...假设队列的最大尺寸为QueueSize,那么队列满的条件就是:(rear+1)%QueueSize == front; 队列的长度计算公式:(rear-front+QueueSize)%Q -
标志位法实现循环队列
2019-09-06 15:12:50但是在判断循环队列空和满这两种状态任然存在问题,因为对于一个循环队列,不做任何判空和判满的机制。判空和判满的条件都是:q->rear == q->front。带来的问题就是当出现上述条件时不能区分循环队列到底是空... -
循环队列的基本操作C/C++代码实现
2020-06-03 18:27:51注意:循环队列为了方便判断队空和队满,一般少用一个元素空间, 即最后一个元素不用,队列空间大小为m时,有m-1个元素就认为是队满。详情见入队和出队。 求队列长度: 队列长度为:(Q.rear-Q.front+MAXQSIZE)%... -
Java实现一个阻塞队列
2020-10-13 12:24:54阻塞队列环境阻塞队列阻塞队列...Java语言实现一个循环队列 阻塞队列内部构造及初始化 使用ReetrantLock,进行多线程的锁的控制,以及使用Condition进行实现队列中操作等待和唤醒。 static class BlockQueue<T& -
数组循环队列
2018-03-16 17:51:29如果数组仿真队列进行插入一次删除一次的操作,只要2*n次数组就会被用光,当数组仿真队列的元素出队后,队的首部回空出许多位置,而队尾指针指向队列中最后一个元素位置,空出的位置将无法再被利用,导致队列空间的... -
java 手写阻塞队列_Java实现一个阻塞队列
2020-12-21 12:01:11循环队列是如何实现的,以及实现的原理,判断栈满栈空的条件为何这样写,参考Java语言实现一个循环队列阻塞队列内部构造及初始化使用ReetrantLock,进行多线程的锁的控制,以及使用Condition进行实现队列中操作等待... -
栈和队列算法四之循环队列
2014-05-05 09:09:04为了解决假溢出的办法... 当队列为空时,此时front==rear,但是现在队列满的条件也是front==rear,怎么判断队列究竟是空还是满呢? 1.解决办法一是设置一个标志变量flag,当front==rear,且flag=0时为空队列,当fr