精华内容
下载资源
问答
  • 循环队列队满判断

    千次阅读 2020-08-27 14:35:14
    为了方便对于循环队列进行满判断,牺牲一个存储单元。记rear、head分别为队尾头指针则: 满:(rear+1)%maxsize=head 空:rear=head 插入元素后,rear=(rear+1)%maxsize 删除元素后,head=(head+1...

    为了方便对于循环队列进行队空队满判断,牺牲一个存储单元。记rear、head分别为队尾队头指针则:

    • 队满:(rear+1)%maxsize=head
    • 队空:rear=head
    • 插入元素后,rear=(rear+1)%maxsize
    • 删除元素后,head=(head+1)%maxsize
    展开全文
  • 循环队列队空与满两个状态的判断算法分析 线性表是数据结构中比较重要的一种逻辑结构,插入删除操作是线性表的基本操作, 当进行这些操作时,不仅需要考虑插入、删除的位置是否合法性, 仍然需要考虑‘满’与...

    循环队列队空与队满两个状态的判断算法分析

    线性表是数据结构中比较重要的一种逻辑结构,插入删除操作是线性表的基本操作,

    当进行这些操作时,不仅需要考虑插入、删除的位置是否合法性,

    仍然需要考虑‘满’与‘空’这两种状态,但是,由于栈和队列都是受限制的线性表,

    它们已经规定了进行插入、删除的位置,所以插入、删除时不需要再考虑位置的合法性,

    只需要考虑‘满’与‘空’。
    1 队列与栈的区别
    数据结构中,队列是只允许在一端进行删除(队头)另一端进行插入(队尾)的线性表;

    栈是只允许在一端进行插入删除(栈顶)的线性表。由于两者都是线性表,

    则遵循线性表的存储结构表示—顺序存储以及链式存储,

    这里主要讨论静态分配的顺序存储结构。如下:
    #define MAXSIZE 100 //初始分配空间
    typedef struct {
    Elemtype data[MAXSIZE];//一维数组
    int Top; //栈顶指针,一直指向栈顶元素,初始值为-1
    }sqStack;
    typedef struct {
    Elemtype data[MAXSIZE];//一维数组
    int front; //队头指针指向队头元素,初始值为0
    int rear; //队尾指针指向队尾元素的下一个位置,初始值为0
    }sqQueue;
    2 顺序队列与栈判断满和空的不同
    线性表顺序存储的静态分配特点是初始化时一次性分配好所需内存空间(MAXSIZE),

    因此在插入删除时需要判断‘空’和‘满’两个状态。由于栈的所有操作只在栈顶进行,

    所以只通过栈顶值Top就可以反映出当前存储空间使用的情况,当Top==-1时栈空,

    Top==MAXSIZE-1时栈满。顺序队列的操作分别在队头队尾两端进行,在出队入队时,

    对头front和队尾rear值都是只增加(向MAXSIZE靠近)而不减小,

    如果仅通过rear==MAXSIZE来判断顺序队列是否满,

    此时可能存在rear已经指向MAXSIZE同时front>0(因为出队使front值增加)

    而不能做入队操作的情况,导致元素出队后的空闲存储空间永远无法重新利用,

    尽管这时循环队列中实际的元素个数远远的小于最大存储空间MAXSIZE,

    这就造成了顺序队列中的“假上溢”现象。

    以上进一步看出栈与顺序队列在进行插入删除时空与满的判断条件不一样。
    顺序队列的“假上溢”现象:
    为克服“假上溢”现象,可以将顺序队列想象为一个首尾相接的环状空间,称为循环队列。

    在循环队列中出队入队时,头尾指针仍要向前移动进行加1操作,

    当头尾指针指向上界MAXSIZE时,

    头尾指针加1操作的结果重新指向下界0(加1后对MAXSIZE做MOD取余数运算)。

    循环队列是解决了“假上溢”现象,但对循环队列进行插入删除时如何判断队空与队满?
    3 循环队列队空与队满的判断
    循环队列入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,

    故存在队空和队满时都有front==rear的情况,

    因此无法通过front==rear来判断队空还是队满,下面就给出五种算法来解决循环队列空和满的问题。

    算法一、增加两个全局变量A,B,分别表示所有元素入队的次数A和元素出队的次数B。
    初始化A=0,B=0;
    出队时,当front==rear&&A==B(即入队元素次数等于出队元素次数)时队空,

    不能出队,然后B++;
    入队时,当front==rear&&(A-B==MAXSIZE)

    (表示入队元素数多于出队元素数,但两者差必须为MAXSIZE)时队满,不能入队,然后A++。
    算法二、增加一个计数变量Count,表示队列中实际存在的数据元素的个数。
    初始化Count=0;
    出队时,当Count==0队空,不能出队,然后Count--;
    入队时,当Count==MAXSIZE队满,不能入队,然后Count++。
    算法三、增加一个布尔变量Tag来区分。
    初始化 Tag=0,并且入队成功时置Tag=1、出队成功时置Tag=0;
    出队是队头在追赶队尾,如果追上了,即rear==front&&tag==0表示队空,

    不能出队,然后重新置Tag=0;
    入队是队尾追赶队头(沿着空位置向队头方向移动),

    如果追上了,即rear==front&&tag==1时表示队满,不能入队,然后重新置Tag=1。
    算法四、约定牺牲存储空间中的一个存储单元来区分。(教材中大多采用这种算法)。
    出队时,当rear==front队空,不能出队;
    入队时,当(rear+1)%MAXSIZE==front队满,不能入队。
    算法五、将静态分配的循环队列改为动态分配的循环队列。
    以上可见,循环队列不能使用动态分配的一维数组实现,但是循环队列也是顺序队列,

    遵循顺序存储结构的分配方式,即可以静态分配存储空间,

    也可以根据队列的长度动态分配存储空间。如下:顺序队列在动态分配顺序存储结构:
    #define QUESIZE 100 //初始分配量
    #define QUEUEINCREMENT 10 //动态分配增量
    typedef struct{
    ElemType *elem; //动态分配存储空间基址
    int front;
    int rear;
    int quesize; //当前分配的存储容量(以sizeof(ElemType)为单位)
    }sqQueue;
    入队时(rear+1)%quesize==front判断是否队满,

    满则动态再分配QUEUEINCREMENT的空间,重新构成新的循环队列,

    新队列头尾指针要分不同情况来修改。因为原队列队满时,

    头尾指针有不同的分布情况,所以先分析出不同分布后再分别根据新增加空间来修改头尾指针。
    出队时rear==front队空,不能出队;
    4 总结
    基于以上五种算法循环队列在实现入队出队操作时就比较容易了,

    不过一定要注意算法实现顺序,入队时先判断是不是队满,

    出队时先判断是不是队空,然后再进行相应的入队出队操作。

    展开全文
  • 顺序循环队列队空的两种判别方式

    千次阅读 多人点赞 2020-07-29 19:34:31
    方法一:少用一个元素空间 我们严蔚敏奶奶的书是使用的这种方法 当我们的顺序循环队列空间大小是m那么有m-1个元素就可以认为是满,也就是: (Q.rear+1)%MAXQSIZE==Q.front 那么空就是首尾指针相等,即: Q.front...

    写在前面:博主是一位普普通通的19届双非软工在读生,平时最大的爱好就是听听歌,逛逛B站。博主很喜欢的一句话花开堪折直须折,莫待无花空折枝:博主的理解是头一次为人,就应该做自己想做的事,做自己不后悔的事,做自己以后不会留有遗憾的事,做自己觉得有意义的事,不浪费这大好的青春年华。博主写博客目的是记录所学到的知识并方便自己复习,在记录知识的同时获得部分浏览量,得到更多人的认可,满足小小的成就感,同时在写博客的途中结交更多志同道合的朋友,让自己在技术的路上并不孤单。

    目录:
    1.方法一:少用一个元素空间
    2.方法二:设置标志位区分队列的空和满

    1.方法一:少用一个元素空间

    我们严蔚敏奶奶的书是使用的这种方法

    当我们的顺序循环队列空间大小是m那么有m-1个元素就可以认为是队满,也就是:
    (Q.rear+1)%MAXQSIZE==Q.front
    那么队空就是首尾指针相等,即:
    Q.front==Q.rear

    2.方法二:设置标志位区分队列的空和满

    我们看一道程序设计题:

    假设以数组Q[m]存放循环队列元素,同时设置一个标志tag以tag== 0和tag==1来区别在队头指针(Q.front)和队尾指针(Q.rear)相等时,队列状态为空,还是满,并试着写出相应插入删除的算法

    直接看代码:

    typedef struct{
    	ElemType *base;
    	int front;
    	int rear;
    	int tag;
    }SqQueue;
    Status InitQueue(SqQueue &Q)
    {
    	Q.base=new ElemType[MAXSIZE];
    	if(!Q.base)
    	exit(1);
    	Q.front=Q.rear=0;
    	Q.tag=0;
    	return OK; 
    }
    Status EnQueue(SqQueue &Q,ElemType e)
    {
    	if((Q.tag==1)&&(Q.rear==Q.front))//队满
    	return ERROR;
    	else
    	Q.base[Q.rear]=e;
    	Q.rear=(Q.rear+1)%MAXSIZE;
    	if(Q.tag==1)
    	Q.tag=1;
    	return OK; 
    }
    Status DeQueue(SqQueue &Q,ElemType e)
    {
    	if((Q.tag==0)&&(Q.rear==Q.front))//队空
    	return ERROR;
    	e=Q.base[Q.front];
    	Q.front=(Q.front+1)%MAXSIZE;
    	if(Q.tag==1)
    	Q.tag=0; 
        return OK; 
    }
    

    我们可以看到队满和空都需要具备两个条件

    队满:(Q.tag==1)&&(Q.rear==Q.front)
    队空:(Q.tag==0)&&(Q.rear==Q.front)

    展开全文
  • 定义变量count记录中元素,显然,count=queue.size时,满 count=0时,空 策略二:立Flag 初始令flag为false,true表示入队,false表示出满,则当前操作为入队;反之,为出 策略三:斩草除根 令front...

    策略一:计数

    定义变量count记录队中元素,显然,count=queue.size时,队满
    count=0时,队空

    策略二:立Flag

    初始令flagfalsetrue表示入队,false表示出队
    若队满,则当前操作为入队;反之,为出队

    策略三:斩草除根

    frontrear所指空间不存数据,则当进行入队操作使得front=rear时,操作无法进行,只有当队空时才会有front=rear

    • 综合来看,前两种策略都需要定义额外的变量,虽然策略三会牺牲一个元素空间,但操作起来比较方便,一般推荐策略三
    展开全文
  • 循环队列队满和空判定

    万次阅读 多人点赞 2018-06-18 21:47:48
    顺序存储结构的循环队列假设循环队列的队尾指针是rear,头是front,其中QueueSize为循环队列的最大长度。(1) 入队时队尾指针前进1:(rear+1)%QueueSize(2) 出头指针前进1:(front+1)%QueueSize例1, 例2(3)...
  • 循环队列队满和空的判定

    千次阅读 2014-09-21 10:18:13
    循环队列的空与满的条件 分类: 数据结构与算法2010-07-07 21:31 8976人阅读 评论(3) 收藏 举报 inputstruct 为了方便起见,约定:初始化建空时,令  front=rear=0,  当空时:front...
  • 顺序队列和循环队列队空判断条件分别是什么,我现在有点混淆了
  • C++实现循环队列(详解头指空) 循环队列.hpp #include <iostream> using namespace std; const int MAXSIZE = 1024; template <class T> class CircleQueue { public: CircleQueue() { front = ...
  • 题目:如果允许在循环队列的两端都可以进行插入和删除操作。要求: ① 写出循环队列的类型定义; ② 写出“从队尾删除”和“从头插入”的算法。 ①定义循环队列: #define MAXSIZE 10; typedef struct{ Elemtype ...
  • 为了方便起见,约定:初始化建空时,令front=rear=0,当空时:front=rear当满时:front=rear 亦成立因此只凭等式front=rear无法判断空还是满。 有两种方法处理上述问题:(1)另设一个标志位以区别队列是空...
  • 实现循环队列,适合数据结构的小白~
  • 循环队列以数组Q【0,...,m-1】存储结构,变量rear表示循环队列中的队尾元素的实际位置,其移动按rear=(rear+1)/MODm,变量length表示当前循环队列中的元素个数,则循环队列的首元素的实际位置是((rear-length+1...
  • 循环队列入

    2021-10-26 15:26:30
    本题要求实现队列的顺序存储表示,包括入队、出和取头操作 函数接口定义: void EnQueue_seq(SeqQueue squeue, DataType x) ; void DeQueue_seq(SeqQueue squeue) ; DataType FrontQueue_seq(SeqQueue squeue...
  • 循环队列: 头指针:指向首元素的前一个位置 队尾指针:指向队尾元素 循环栈: 头指针:指向首元素 队尾指针:指向队尾元素的后一个位置 ...
  • 循环队列判断满和空的条件

    万次阅读 2019-10-15 15:34:21
    循环队列判断满和空的条件 满:front=(rear+1)%size ; 空:front = rear&&
  • 在引用循环队列前,我们需要了解队列是如何线性实现的。 简单地讲,便是当队列为空时,...循环队列原理图: 我们可以发现,当循环队列属于上图的d1情况时,是无法判断当前状态是空还是满。为了达到判断队列状...
  • 循环队列处理满和空的方式 顺序存储的队列在满时再进出现的溢出往往是假溢出,即还有空间但用不上,为了有效利用队列空间,可将队列元素存放数组首尾相接,形成循环队列。 但是构造循环队列时不得不考虑到...
  • front表示头指针(指向队列内首元素) rear表示队尾指针(指向队列内尾元素的下一个位置) m表示队列的容量 空:front=rear 满:front=(rear+1)%m 队列内元素个数:(rear - front + m) % m ...
  • #include <stdio.h> #include <stdlib.h> #define ERROR 0 #define OK 1 typedef struct Queue { int *data; int head, tail, length, count; }Queue; void init(Queue *q, int length) { ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,208
精华内容 2,883
关键字:

循环队列队