精华内容
下载资源
问答
  • 如何判断循环队列为队空or满?

    千次阅读 多人点赞 2020-02-16 13:18:35
    什么是循环队列 循环队列就是将队列存储空间的最后一个位置绕到第一个位置,首尾相连形成逻辑上的环状空间,供队列循环使用。 循环队列可以更简单防止假溢出的发生,但队列大小是固定...如何判断循环队列为队空or...

    什么是循环队列

    循环队列就是将队列存储空间的最后一个位置绕到第一个位置,首尾相连形成逻辑上的环状空间,供队列循环使用。

    循环队列可以更简单防止假溢出的发生,但队列大小是固定的。

    假溢出

    作为队列用的存储区还没有满,但队列却发生了溢出,我们把这种现象称为"假溢出"

    解决假溢出有两种方案:

    一、将队列元素向前搬移。

    二、将队列看成首尾相连,即循环队列。

     

    如何判断循环队列为队空or队满?

    循环队列中,由于入队时尾指针向前追赶头指针;

    出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。

    因此,无法通过条件“front==rear”来判别队列是"空"还是"满"。

     

    第一种情况——“牺牲”一个单元

     

    约定循环队列少用一个空间,此时队列为空的判断条件仍然是 ront==rear,

    认为出现上图的情况即为队满,此时rear+1=front。

    在一般情况下,当队列满时,rear+1=front。

    但是,有个特殊情况,就是rear=n-1,而front=0时,这时候,rear+1=n,并不等于front。而此时front=0。

    由于rear,front均为所用空间的指针,循环只是逻辑上的循环,为了规避这一特殊情况,需要余运算。

    真正的队满表达式为:(rear+1)%n==front。

    rear+1最大的情况就是 n ,不会大于 n。特殊情况就是(rear+1)%n == n%n ==front== 0。

    除rear+1=n的 最大情况,剩余情况怎么余 n 都是 tail+1 本身,也就是 front。

    第二种情况——不“牺牲”

    设标记法

    设标记tag

    当有数据出队时,tag=-1;

    当有数据入队时,tag=1;

    利用这个方法,当rear==front时,若tag=-1,说明是由出队导致的,此时为队空

                             当rear==front时,若tag=1,说明是由入队导致的,此时为队满

    计数法

    定义一个变量count,来计算在队列中的数据个数。

    当有数据入队时,++count

    当有数据出队时,--count

    当count==0时为队空,当count==MaxSize时为队满。

    展开全文
  • 循环队列判断满和队空条件

    千次阅读 2019-10-15 15:34:21
    循环队列判断满和队空条件 满:front=(rear+1)%size ; 队空:front = rear&&

    标循环队列判断队满和队空的条件

    队满:front=(rear+1)%size ;
    队空:front = rear&&
    在这里插入图片描述
    图片上的信息来自王红梅教授版数据结构第二版

    展开全文
  • 判断队列为空或者为满

    千次阅读 2020-08-11 19:15:20
    为了方便起见,约定:初始化建空队时,令 front=rear=0, 当队空时:front=rear 当队满时:front=rear 亦成立 因此只凭等式front=rear无法判断队空还是队满。 有两种方法处理上述问题: (1)另设一个标志位以区别...

     

    为了方便起见,约定:初始化建空队时,令
          front=rear=0,
      当队空时:front=rear
      当队满时:front=rear 亦成立
      因此只凭等式front=rear无法判断队空还是队满。  有两种方法处理上述问题:
        (1)另设一个标志位以区别队列是空还是满。
        (2)少用一个元素空间,约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即:
      队空时: front=rear
      队满时: (rear+1)%maxsize=front

      front指向队首元素,rear指向队尾元素的下一个元素。

      

     

     

    1. 当队列不为空时,front指向队列的第一个元素,rear指向队列最后一个元素的下一个位置。
    2. 当队列为空时,front=rear
    3. 队列满时:(rear+1)%maxsiz=front,少用一个存储空间,也就是数组的最后一个存数空间不用

     

    循环队列的相关条件和公式:

    1.队空条件:rear==front

    2.队满条件:(rear+1) %QueueSIze==front,其中QueueSize为循环队列的最大长度

    3.计算队列长度:(rear-front+QueueSize)%QueueSize

    4.入队:(rear+1)%QueueSize

    5.出队:(front+1)%QueueSize

    展开全文
  • 循环队列的队空满的条件

    千次阅读 2013-09-23 10:29:00
    为了方便起见,约定:初始化建空队时,令  front=rear=0,  当队空时:front=rear  当队满时:front=rear 亦成立  因此只凭等式front=rear无法判断队空还是队满。 有两种方法处理上述问题:  (1)另设一...

    为了方便起见,约定:初始化建空队时,令
       front=rear=0,
      当队空时:front=rear
      当队满时:front=rear 亦成立
      因此只凭等式front=rear无法判断队空还是队满。  有两种方法处理上述问题:
        (1)另设一个标志位以区别队列是空还是满。
        (2)少用一个元素空间,约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即:
      队空时: front=rear
      队满时: (rear+1)%maxsize=front

      front指向队首元素,rear指向队尾元素的下一个元素。

      

     


    /
    // 
    // author: kangquan2008@csdn
    //
    /
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    #define QUEUE_SIZE 10
    #define EN_QUEUE 1
    #define DE_QUEUE 2
    #define EXIT     3
    
    typedef int    Item;
    typedef struct QUEUE{
    
    	Item * item;
    	int front;
    	int tear;
    
    }Queue;
    
    int init_queue(Queue * queue)
    {
    	queue->item = malloc(QUEUE_SIZE * sizeof(Item));
    	if(!queue->item)
    	{
    		printf("%s\n","Alloc failed,not memory enough");
    		exit(EXIT_FAILURE);
    	}
    
    	queue->front = queue->tear = 0;
    
    	return 1;
    }
    
    int en_queue(Queue * queue, Item item)
    {
    	if((queue->tear+1) % QUEUE_SIZE == queue->front)
    	{
    		printf("%s\n","The queue is full");
    		return -1;
    	}
    
    	queue->item[queue->tear] = item;
    	queue->tear = (queue->tear + 1) % QUEUE_SIZE;
    
    	return 1;
    }
    
    int de_queue(Queue * queue, Item * item)
    {
    	if(queue->front == queue->tear)
    	{
    		printf("%s\n","The queue is empty");
    		return -1;
    	}
    
    	(*item) = queue->item[queue->front];
    	queue->front = (queue->front + 1) % QUEUE_SIZE;
    
    	return 1;
    }
    
    int destroy_queue(Queue * queue)
    {
    	free(queue->item);
    }
    
    int main()
    {
    	Queue que;
    	init_queue(&que);
    	int elem;
    	bool flag = true;
    	while(flag)
    	{
    		int choice;
    		printf("1 for en_queue,2 for de_queue,3 for exit\r\nplease input:");
    		scanf("%d",&choice);
    
    		switch((choice))
    		{
    			case EN_QUEUE:
    				printf("input a num:");
    				scanf("%d",&elem);
    				en_queue(&que,elem);
    				break;
    			case DE_QUEUE:
    				if(de_queue(&que,&elem) == 1)
    					printf("front item is:%d\n",elem);
    				break;
    			case EXIT:
    				flag = false;
    				break;
    			default:
    				printf("error input\n");
    				break;
    		}
    	}
    
    	destroy_queue(&que);
    	return 0;
    }
    

    文章出处: http://blog.csdn.net/huangkq1989/article/details/5719529

    展开全文
  • 线性表是数据结构中比较重要的一种逻辑结构,插入删除操作是线性表的基本操作,当进行这些操作时,不仅需要考虑插入、删除的位置是否合法性,...数据结构中,队列是只允许在一端进行删除(头)另一端进行插入(队尾
  • 循环队列判断满的两种方法(C#)

    千次阅读 2019-10-20 20:06:46
    问题描述:循环队列为空条件是 rearfront 。如果进元素的速度快于出元素的速度,队尾指针很快就赶上了首指针,此时可以看出循环队列的条件也为 rearfront。怎样区分这两者之间的差别呢? 解决方案: 方法...
  • 顺序循环队列队满队空的两种判别方式

    千次阅读 多人点赞 2020-07-29 19:34:31
    博主很喜欢的一句话花开堪折直须折,莫待无花折枝:博主的理解是头一次为人,就应该做自己想做的事,做自己不后悔的事,做自己以后不会留有遗憾的事,做自己觉得有意义的事,不浪费这大好的青春年华。博主写博客...
  • 循环队列中判断满与队空

    万次阅读 多人点赞 2016-04-02 11:16:38
    在引用循环队列前,我们需要了解队列是如何线性实现的。 简单地讲,便是当队列为时,front = rear = 0,每当插入元素尾...我们可以发现,当循环队列属于上图的d1情况时,是无法判断当前状态是队空还是满。为了
  • 队列为空时:rear= =front 队列满时:(rear+1)%maxSize= =front 不少一个存储位置时:加一个标志flag或者计数的count 入队时flag=true 出时flag=false 满:rear= =front&flag 队空:rear= =front&!...
  • 4, 【2019统考真题】请设计一个队列,要求满足: 初始时队列为空; ②入队时,允许增加队列占用空间; ③出后,出元素所占用的空间可重复使用,即整个队列所占用的空间只增不减;④入队操作和出操作的时间复杂度始终...
  • 问题:链表,栈,队列(循环队列)判定满或者条件?急求 1、为空条件 单链表:头结点指针域next == NULL 静态链表:数组最后一个元素值为0 循环链表:头结点的指针域指向它本身(循环查找时以p->next !=头结点...
  • 顺序队列的三种状态   1. 队空 qu.front == qu.rear ...  注:随着出入队的操作,当出现队空状态时,头队尾指针不一定指向第一个元素。   2. 满 qu.front == 0;qu.rear == max+1   3. ...
  • 循环队列处理满和队空的方式 顺序存储的队列在满时再进出现的溢出往往是假溢出,即还有空间但用不上,为了有效利用队列空间,可将队列元素存放数组首尾相接,形成循环队列。 但是构造循环队列时不得不考虑到...
  • 循环队列:判断队列和满的3种方法

    千次阅读 多人点赞 2020-02-14 19:32:18
    队列为空条件:rear == front 当队列满时条件为:rear+1 == front      上述方式对于上述图是适用的,但如果出现了有下标标识,上述判断条件就不适用了。比如下图有下标了,当队列满时,显然条件就不能判断...
  • C语言之循环队列判断满与

    千次阅读 2017-03-23 08:23:54
    何时队列为空?何时为满? 由于入队时尾指针向前追赶头指针,出时头指针向前追赶尾指针,故队空满时头尾指针均相等。因此,我们无法通过front=rear来判断队列“”还是“满”。 注:先进入的为‘头’,后进入...
  • 入口条件循环(1)

    2018-12-03 19:18:45
    1:我们以菲波那契数列为例:在进行运算时,由于数字要相加,因此运算量较大。 在这里我们引入循环的概念:例如以下是五种for的循环。 #include &amp;lt;algorithm&amp;gt; #include &amp;lt;...
  • 循环队列为充分利用向量空间,克服”假溢出”现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来在...
  • 循环队列满的判断

    万次阅读 2018-03-23 21:06:28
    第一种方法是设置一个标志量flag,当front==rear且flag=0时为,当front==rear且flag=1时队列为满;第二种方法是我们修改条件,保留一个元素空间,也就是说,数组中还有一个空闲单元时,我们就认为这个队列已经满了...
  • //队列的顺序存储(循环队列) #include<stdio.h> #include<stdlib.h> #define Maxsize 10 typedef struct{ int data[Maxsize]; int front,rear; }SqQueue; void InitQueue(SqQueue &Q){//初始化队列 ...
  • 循环循环双端队列

    千次阅读 2020-01-20 23:12:12
    循环队列 是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在首之后以形成一个循环。它也被称为 环形缓冲器。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里...
  • 声明:博文所有gif图均为本人原创…… 队列(queue) ...允许插入的一段叫做队尾,允许删除的一段称为头。 队列的抽象数据类型 ADT 队列(Queue) { Data 同线性表。元素具有相同的类型,相邻元素...
  • 循环队列为空条件:(q->front == q->rear) 为 循环队列为满的情况也是q->front == q->rear, 解决方法:出一元素, 作为满的条件 如图: 循环队列为满的条件:(q->rear+1 == Q->front) 为满...
  • 怎么判断循环队列是否为?或者已经满了?

    万次阅读 多人点赞 2017-03-29 18:39:28
    现有一个循环队列,其头指针为 front,队尾指针为 rear,循环队列的总长度为 N,问怎么判断循环队列满了? 正确答案: D front==rear front==rear+1 front==rear%n front==(rear+1)%n 当...
  • 2、顺序队列,首指针指向首元素,队尾指针指向队尾元素的前一个元素,此时队列为空的判定条件是 Q.front == Q.rear == 0; 2、顺序队列会有假溢出的现象,为此设计了循环队列。 1)为了区分满和队空条件...
  • 循环队列的一些问题总结,入队、出操作

    千次阅读 多人点赞 2019-02-02 12:48:39
    1.在队列的顺序存储方式里,为了避免存储空间的“假溢出”,充分利用存储空间,我们用了一种实现方式,即循环队列。 (1).图中有两个指针(只是两个整型变量,因为在这里有指示作用,所以理解为指针) front、rear,...
  • 队列是队尾添加元素,头删除元素,先进先出...那为什么这个下面的代码可以适用于非循环队列和循环队列呢,原因就在于判断队列为空和满的条件,即当当(rear+1) % MAXSIZE = front时为满这个条件,下面分析一下这个条件
  • 设计一个循环队列,用front和rear分别作为头和队尾指针,另外用一个标志tag表示队列是还是不,约定当tag为0时队空,当tag为1时,这样就可以用front==rear作为满的条件要求,设计队列的结构和相关基本...
  • 循环队列

    2017-07-10 20:25:37
    为了解决顺序队列中的“假溢出”现象,充分...当队列为或满时,front = rear都成立,所以不能用这个条件来判断队列是的还是满的。 为了解决这个问题,在循环队列中有一个约定: 少用一个元素空间,当队尾标识rear

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,678
精华内容 9,071
关键字:

循环队列为空的条件