精华内容
下载资源
问答
  • 【2011年全国试题3】已知循环队列存储在一维数组A[0…n-1],且队列非空时,front和rear分别指向队头元素和队尾元素。若初始时队列为空,且要求第一个进入队列元素存储在A[0]处,则初始时front和rear值分别是(B...

    【2011年全国试题3】已知循环队列存储在一维数组A[0…n-1],且队列非空时,front和rear分别指向队头元素和队尾元素。若初始时队列为空,且要求第一个进入队列的元素存储在A[0]处,则初始时front和rear的值分别是(B)

    A. 0, 0          B. 0, n-1          C. n-1, 0          D. n-1, n-1

     

    首先理解"队列非空时,front和rear分别指向队头元素和队尾元素"。当队列中有一个元素时,front与rear都需要指向A[0]。我们知道,无论是在存入元素前移动rear还是存入元素后移动rear,最终的状态都是,rear移动了,即执行了(rear+1)%n运算。

    当队列中有一个元素时,front与rear都指向A[0]。这是执行完(rear+1)%n运算后的状态,那么没有执行前就是初始状态。rear=n-1。

    对于front来说,没有出队操作,不需要移动front,存入一个元素时,front没有动,也就是仍然是初始状态,所以front=0。

     

     

     

    答案参考百度知道网友的回答http://zhidao.baidu.com/question/1962019237865543580

    展开全文
  • 近期查看严蔚敏的《数据结构(C语言版)》,里面有这样一句话:从上述分析可见,C语言不能用动态分配的一维数组来实现循环队列。网上也有不少网友询问这句话的意思及对错,先谈一下自己的认识。 动态分配的存储...

    近期查看严蔚敏的《数据结构(C语言版)》,里面有这样一句话:从上述分析可见,在C语言中不能用动态分配的一维数组来实现循环队列。网上也有不少网友询问这句话的意思及对错,先谈一下自己的认识。

    动态分配的存储空间是连续的存储空间,假如分配了n个存储空间(分别问0,1,...,n-1),第n-1个存储空间的地址肯定大于第0个存储空间的地址。当所有的空间都存储满时,继续存储元素就会发生数组越界,出现错误。当出现图3.12中(d)图中的情况时,尾指针不能返回到队列尾部进行继续元素的添加,因此也就不能形成循环多列。因此,只能采用链式存储结构,利用指针将第n-1个存储空间与第0个存储空间产生关联,进而形成循环队列。

    简而言之,动态分配的一维数组是靠本身各存储空间连续产生关联,链表是通过指针将各存储空间产生关联,动态分配的第n-1个存储空间与第0个存储空间之间是没有关联的,是不可能产生循环结构的。

    如有见解,请留言。

    展开全文
  • 与顺序栈类似,在队列的顺序存储结构,用一组地址连续的存储单元依次存放从队头到队尾的元素,如一维数组 Queue[MAXSIZE]。 由于队列中队头和队尾的位置都是动态变化的,因此需要附设两个指针 front 和 rear。 ...

    3.9队列的顺序存储(循环队列)

    1、顺序队列的假溢出现象

    队列的一种顺序存储称为顺序队列

    与顺序栈类似,在队列的顺序存储结构中,用一组地址连续的存储单元依次存放从队头到队尾的元素,如一维数组 Queue[MAXSIZE]。

    由于队列中队头和队尾的位置都是动态变化的,因此需要附设两个指针 front 和 rear。

    • front:指示队头元素在数组中的位置;
    • rear:指示真实队尾元素相邻的下一个位置。

    初始化队列时,令 front = rear =0;

    入队时,直接将新元素送入尾指针 rear 所指的单元, 然后尾指针增 1;

    出队时,直接取出队头指针 front 所指的元素,然后头指针增 1。

    显然,在非空顺序队列中,队头指针始终指向当前的队头元素,而队尾指针始终指向真正队尾元素后面的单元。当 rear==MAXSIZE 时,认为队满。但此时不一定是真的队满,因为随着部分元素的出队,数组前面会出现一些空单元,如下图(d)所示。由于只能在队尾入队,使得上述 空单元无法使用。把这种现象称为假溢出,真正队满的条件是 rear - front=MAXSIZE

    在这里插入图片描述

    2. 循环队列

    为了解决假溢出现象并使得队列空间得到充分利用,一个较巧妙的办法是将顺序队列的数组看成一个环状的空间,即规定最后一个单元的后继为第一个单元,我们形象地称之为循环队列

    假设队列数组为 Queue[MAXSIZE],当 rear+1=MAXSIZE 时,令 rear=0,即可求得最后一个单元 Queue[MAXSIZE-1]的后继:Queue[0]。

    更简便的办法是通过数学中的取模(求余)运算来实现:rear=(rear+1)mod MAXSIZE,显然,当 rear+1=MAXSIZE 时,rear=0, 同样可求得最后一个单元 Queue[MAXSIZE-1]的后继:Queue[0]。

    所以,借助于取模(求余) 运算,可以自动实现队尾指针、队头指针的循环变化。
    进队操作时,队尾指针的变化是:rear= (rear+1)mod MAXSIZE ;
    而出队操作时,队头指针的变化是:front=(front+1)mod MAXSIZE。

    下图给出了循环队列的几种情况:

    循环队列判空判满问题

    与一般的非空顺序队列相同,在非空循环队列中,队头指针始终指向当前的队头元素,而队尾指针始终指向真正队尾元素后面的单元。
    在这里插入图片描述
    队列头元素是 e3,队列尾元素是 e5,当 e6、e7和 e8相继入队后,队列空间均被占满,如上图 (b)所示, 此时队尾指针追上队头指针,所以有:front =rear。

    反之,若 e3、e4 和 e5相继从上图 ©的 队列中删除,则得到空队列,如上图 (a)所示,此时队头指针追上队尾指针,所以也存在关 系式:front = rear。可见,只凭 front = rear 无法判别队列的状态是“空”还是“满”。

    对于这个问题,可有两种处理方法

    • 一种方法是少用一个元素空间。当队尾指针所指向的空单元 的后继单元是队头元素所在的单元时,则停止入队。这样一来,队尾指针永远追不上队头指 针,所以队满时不会有 front =rear。现在队列“满”的条件为(rear+1)mod MAXSIZE=front。 判队空的条件不变,仍为 rear=front。
    • 另一种是增设一个标志量的方法,以区别队列是“空” 还是“满”。主要介绍损失一个存储空间以区分队列空与满的方法。

    循环队列的类型定义

    #define MAXSIZE 50  /*队列的最大长度*/ typedef struct 
    {  
    	QueueElementType  element[MAXSIZE];  /* 队列的元素空间*/  
    	int  front;  /*头指针指示器*/  
    	int  rear ;  /*尾指针指示器*/ 
    }SeqQueue;
    

    循环队列的基本操作

    (1) 初始化操作

    void InitQueue(SeqQueue * Q) 
    {  /* 将*Q 初始化为一个空的循环队列 */ 
    	Q->front=Q->rear=0; 
    } 
    

    (2) 入队操作

    int EnterQueue(SeqQueue *Q, QueueElementType x) 
    {  /*将元素 x 入队*/ 
    	if((Q->rear+1)%MAXSIZE==Q->front)  /*队列已经满了*/ 
      		return(FALSE); 
      	Q->element[Q->rear]=x; 
    	Q->rear=(Q->rear+1)%MAXSIZE;  /* 重新设置队尾指针 */ 
    	return(TRUE);  /*操作成功*/ 
    } 
    

    (3)出队操作

    int DeleteQueue(SeqQueue *Q, QueueElementType * x) 
    { /*删除队列的队头元素,用 x 返回其值*/ 
    	if(Q->front==Q->rear)  /*队列为空*/ 
        	return(FALSE); 
       	*x=Q->element[Q->front]; 
       	Q->front=(Q->front+1)%MAXSIZE;  /*重新设置队头指针*/ 
      	return(TRUE);  /*操作成功*/ 
    } 
    

    这里采用了第一种处理假溢出问题的方法。如果采用第二种方法,则需要设置一个标志量 tag。

    初始化操作即产生一个空的循环队列,此时 Q->front = Q->rear=0,tag=0;当空 的循环队列中有第一个元素入队时,则 tag=1,表示循环队列非空;当 tag=1 且 Q->front=Q->rear 时,表示队满。

    展开全文
  • 循环队列

    2020-02-19 00:29:28
    与顺序栈类似,在队列的顺序存储结构,用一组地址连续的存储单元依次存放从队头到队尾的元素,如一维数组Queue[ MAXSIZE]。此外,由于队列中队头和队尾的位置都是动态变化的,因此需要附设两个指针front和rear,...

    循环队列概念:

    循环队列是队列的一种顺序表示和实现方法。与顺序栈类似,在队列的顺序存储结构中,用一组地址连续的存储单元依次存放从队头到队尾的元素,如一维数组Queue[ MAXSIZE]。此外,由于队列中队头和队尾的位置都是动态变化的,因此需要附设两个指针front和rear,分别指示队头元素和队尾元素在数组中的位置。

    顺序队列的弊端:

    在这里插入图片描述
    显然,在非空顺序队列中,队头指针头元素,而队尾指针始终指向真正队尾元素后面的单元。
    如上图所示 MAXSIZE=6,当rear== MAXSIZE此时不一定是真的队满,因为随着部分元素的出队,数组前面会空出来,由于只能在队尾人队,使得上述空单元无法使用。这种现象称为假溢出真正队满的条件应是rear-front == MAXSIZE。

    解决办法:
    为了解决这种假溢出现象并使队列空间得到充分利用,一个巧妙的方法就是将顺序队列的数组看成是一个环形的空间
    普通环形队列:
    在这里插入图片描述
    继续改进:
    但是由上图可见只凭front== rear无法判断队列的状态是否为空还是满,对于这个问题,方法就是损失一个元素空间,当尾指针所指的空单元的下一个单元时对头元素单元时,队满,停止入队。这样一来,尾指针就永远无法追上队头指针,所以对满就不会是front== rear,而是(rear+1)% MAXSIZE== front。判空的条件不变,仍然是rear==front。

    循环队列:
    在这里插入图片描述
    实现循环队列:
    队满条件:(rear+1)% MAXSIZE == front
    队空条件:rear==front

    #include<stdio.h>
    #define MAXSIZE 20  //队列最大空间
    typedef  int  CQDataType;
    typedef struct CircularQueue
    {
    	CQDataType arr[MAXSIZE];   //队列的元素空间
    	int front;  //对头指针指示器
    	int rear;   //对尾指针指示器
    }CQueue;
    
    
    // 初始化队列
    void QueueInit(CQueue* q)
    {
    	q->front = q->rear = 0; //初始化成一个空的循环队列
    }
    
    // 队尾入队列
    int QueuePush(CQueue* q, CQDataType data)
    {
    	if ((q->rear + 1) % MAXSIZE != q->front)//队列没满时插入
    	{
    		q->arr[q->rear] = data;
    		q->rear = (q->rear + 1) % MAXSIZE;  //重新设置队尾指针
    	}
    	else
    		return -1;//队列满的,无法入队
    }
    
    
    // 队头出队列
    int QueuePop(CQueue* q)
    {
    	if (q->front != q->rear)//队列不为空时可以出对
    	{
    		CQDataType ret=q->arr[q->front];
    		q->front = (q->front + 1) % MAXSIZE;//重新设置队头指针
    	}
    	else
    		return -1;//队列为空,无法出队
    }
    
    展开全文
  • 线性结构就是把所有结点用一根直线穿起来,常用线性结构有:线性表,栈,队列,循环队列一维数组。线性表包括顺序表、链表等,其中,栈和队列只是属于逻辑上概念,实际不存在,仅仅是一种思想,一种理念...
  • 循环队列问题总结

    千次阅读 2016-11-17 16:21:39
    (2011.3)已知循环队列存储在一维数组中A[0…n-1],且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空,且要求第一个进入队列元素存储在A[0]处,则初始时front和rear值分别为:B. A.0,0 B.0...
  • 队列&循环队列的实现

    2019-03-15 20:48:46
    顺序队列:将队列中的元素全部存入一个一维数组中,数组的低下标一端为队头,高下标一端为队列尾部,这样的队列称为顺序队列顺序队列中,队列的存储空间从queue【0】-queue【maxsize-1】。当数据出队列时,队头...
  • 设顺序存储队列一维数组q[n]表示,其中n为队列中元素个数,队列中元素向量中的下标从0到n-1。设队头指针为front,队尾指针是rear,约定front指向队头元素的前一位置,rear指向队尾元素。当front等于-1时队空,...
  • 循环队列的实现

    2011-05-15 00:42:00
    循环队列,如题,就是对队列实现循环存储,队列头尾指针相连,而循环队列在C语言不能通过实现动态分配一维数组实现存储,可定义循环队列如下 typedef struct{  datatype *data;  int ...
  • 循环队列---顺序队列

    2019-01-28 19:18:15
    前两篇中讲述了顺序队列中的队头移动与不移动两种顺序队列,今天讨论顺序队列中的循环队列,这种循环队列是用一维数组实现的。队头移动的情况下,根据元素个数与队列容量之间的数量关系来解决假溢出问题。 从...
  • 队列的顺序存储结构,是将元素存在一个一维数组中,队头所在位置下标是0,当要入队操作时,直接队尾后一个位置插入一个结点即可,时间复杂度为O(1)。而出队列,出队元素下标为0,所以队列中所有元素都要向前...
  • 队列-顺序循环队列

    2020-03-11 20:50:29
    一维数组来存放顺序队列中的数据元素。 队头位置设数组下标为 0 的端,用 front 表示; 队尾位置设数组的另一端,用 rear 表示。 front 和 rear 随着插入和删除而变化。 当队列为空时, front=rear=0。 因为...
  •  根据分析可知,C语言不能用动态分配的一维数组来实现循环队列。如果用户应用程序设有循环队列,则必须为它设定一个最大队列长度;若用户无法预知所用队列最大程度,则宜采用链式存储。 #define ...
  • 己知循环队列存储在一维数组A[O…n-1],且队列非空时front和rear分别指向队头元素和队尾元索。若初始时队列为空,且要求第1个进入队列元素存储在A[0]处,则初始时front和rear值分别为:0,n-1 **我疑问...
  • 队列(queue)是一种限定存取位置的线性变。他允许表的一端插入,另...队列也分为两种,一种是用数组的存储表示,一种是基于链表的存储表示。 基于数组的存储表示的队列被称为顺序队列。其数据成员包括,一维...
  • 数据存储在一一维数组中 特点:先进先出(FIFO)结构 队头(front):删除数据一端 队尾(rear):插入数据一端 顺序队列的缺点:空队时front和rear都指向下标-1处,进队时rear先+1,再放入数据,出队时...
  • 与顺序栈类似,在队列的顺序存储结构,用一组地址连续的存储单元依次存放从队头到队尾的元素,如一维数组 Queue[MAXSIZE]。由于队列中队头和队尾的位置都是动态变化的,因此需要附设两个指针 front 和 rear。front...
  • 我们用一个一维数组存储队列元素值,为了解决“假溢出”现象并使得空间得到充分利用,一个较巧妙的方法是将顺序数组看成一个环状数组(注意:环状空间只是逻辑空间,真实的内存中的还是连续空间,这就解释了为...
  • 队列之顺序存储实现

    2017-10-15 10:01:00
    一个一维数组 记录头元素位置变量front 记录尾元素位置变量rear 开始时front和rear都是-1。 循环队列 使用求余实现循环 线性数组问题: 在一个固定长度数组内,先不断入队直到填满数组,再几次出队。此时...
  • (三)数组

    2020-11-05 22:16:50
    数组定义随机访问低效“插入”和“删除”插入删除数组越界容器更适合使用数组地方:数组下标从0开始小结思考JVM 标记清楚垃圾回收算法二维数组内存寻址死循环问题 定义 数组(Array)是种线性表数据结构。它用...
  • 队列相关习题

    2020-08-07 14:17:47
    1.已知循环队列存储在一维数组A0…n-1],且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空,且要求第一个进入队列元素存储在A[0]处,则初始时front和rear值分别是( )。 A.0,0 B. 0,n-1...
  • 栈、队列有关习题

    2018-11-16 19:40:18
    1.已知循环队列存储在一维数组A[0..n-1],且队列非空时front和rear分别指向队头元素和队尾元素,若初始时队列为空,且要求第1个进入队列元素在A[0]处,则初始时front和rear值分别是 A)0,0 B)0,n-1 C)n-1,0...
  • 已知循环队列存储在一维数组A[0..n-1],且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列空,且要求第一个进入队列元素存储在A[0]处,则初始时front和rear值分别是( )。 A.0,0 B.0,n-...
  • 列表、栈、队列、链表、字典、散列、图和二叉查找树 【列表】 不需长序列查找元素或对其进行排序。 【栈】存储结构是: 【后进先出】或者说【先进后出】 ...可用任何使用一维数组的情况。如需随机访问...
  • 6.1.1 N维数组的定义86 6.1.2 数组的存储方式87 6.1.3 数组元素的寻址88 6.2 稀疏矩阵的压缩存储89 6.2.1 三元组顺序表90 6.2.2 十字链表93 6.3 稀疏矩阵运算的上机体验96 6.4 数组的应用实例100 第7章 树与二叉树...
  • 1.一个栈进栈序列是a...2. 己知循环队列存储在一维数组A[O…n-1],且队列非空时front和rear分别指向队头元素和队尾元索。若初始时队列为空,且要求第1个进入队列元素存储在A[0]处,则初始时front和rear值分...

空空如也

空空如也

1 2 3 4 5 6
收藏数 108
精华内容 43
关键字:

循环队列在一维数组中的存储