精华内容
下载资源
问答
  • 循环队列队空与队满两个状态的判断算法分析 线性表是数据结构中比较重要的一种逻辑结构,插入删除操作是线性表的基本操作, 当进行这些操作时,不仅需要考虑插入、删除的位置是否合法性, 仍然需要考虑‘满’与...

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

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

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

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

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

    只需要考虑‘满’与‘空’。
    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 总结
    基于以上五种算法循环队列在实现入队出队操作时就比较容易了,

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

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

    展开全文
  • 为了方便对于循环队列进行满判断,牺牲一个存储单元。记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
    展开全文
  • 在引用循环队列前,我们需要了解队列是如何线性实现的。 简单地讲,便是当队列为空时,...循环队列原理图: 我们可以发现,当循环队列属于上图的d1情况时,是无法判断当前状态是空还是满。为了达到判断队列状...

    在引用循环队列前,我们需要了解队列是如何线性实现的。

    112168683_1_20170929114859559

    简单地讲,便是当队列为空时,front = rear = 0,每当插入元素尾指针+1,删除元素是头指针-1。但是,我们会发现一个问题,如上面的第四个图,0,1,2三个空间并没有使用。因此,为了占用该空间,我们使用了循环队列来实现。

    循环队列原理图:

    112168683_2_20170929114859684

    我们可以发现,当循环队列属于上图的d1情况时,是无法判断当前状态是队空还是队满。为了达到判断队列状态的目的,可以通过牺牲一个存储空间来实现。

    如上图d2所示,

    队头指针在队尾指针的下一位置时,队满。 Q.front == (Q.rear + 1) % MAXSIZE 因为队头指针可能又重新从0位置开始,而此时队尾指针是MAXSIZE - 1,所以需要求余。

    当队头和队尾指针在同一位置时,队空。 Q.front == Q.rear;

    以下是实现的代码:

    #include

    #include

    #define MAXSIZE 100 //最大队列长度

    #define OK 1

    #define ERROR 0

    typedef int ElemType;

    typedef int Status;

    typedef struct {

    ElemType *base; //队列空间

    int front; //队头指针

    int rear; //队尾指针,若队尾不为空,则指向队尾元素的下一个位置

    }SqQueue;

    //初始化循环队列

    Status initQueue(SqQueue &Q) {

    Q.base = (ElemType *) malloc(MAXSIZE * sizeof(ElemType)); //申请空间

    Q.front = Q.rear = 0; //队空

    return OK;

    }

    //入队

    Status enQueue(SqQueue &Q, ElemType e) {

    if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR; //队满,无法添加

    Q.base[Q.rear] = e; //插入元素

    Q.rear = (Q.rear + 1) % MAXSIZE; //队尾指针+1

    return OK;

    }

    //出队

    Status deQueue(SqQueue &Q, ElemType &e) {

    if (Q.front == Q.rear) return ERROR; //队空,无法删除

    e = Q.base[Q.front];

    Q.front = (Q.front + 1) % MAXSIZE; //队头指针+1

    return OK;

    }

    //返回队列长度

    Status length(SqQueue &Q) {

    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;

    }1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

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

    千次阅读 多人点赞 2020-07-29 19:34:31
    方法一:少用一个元素空间 我们严蔚敏奶奶的书是使用的这种方法 当我们的顺序循环队列空间大小是m那么有m-1个元素就可以认为是满,也就是: (Q.rear+1)%MAXQSIZE==Q.front 那么空就是首尾指针相等,即: Q.front...
  • 为了方便起见,约定:初始化建空时,令front=rear=0,当空时:front=rear当满时:front=rear 亦成立因此只凭等式front=rear无法判断空还是满。 有两种方法处理上述问题:(1)另设一个标志位以区别队列是空...
  • 题目:如果允许在循环队列的两端都可以进行插入和删除操作。要求: ① 写出循环队列的类型定义; ② 写出“从队尾删除”和“从头插入”的算法。 ①定义循环队列: #define MAXSIZE 10; typedef struct{ Elemtype ...
  • 循环队列队满和队空的判定

    千次阅读 2014-09-21 10:18:13
    循环队列的空与满的条件 分类: 数据结构与算法2010-07-07 21:31 8976人阅读 评论(3) 收藏 举报 inputstruct 为了方便起见,约定:初始化建空时,令  front=rear=0,  当空时:front...
  • ☝☝☝软件工程考研独家平台撰稿| 康康哥编辑| 丽丽姐本文由懂计算机、软件工程的博士师哥原创双日练:NO.20200922循环队列放在一维数组A[0…M-1]中,end1指向头元素,end2指向队尾元素的后一个位置。假设队列两端...
  • 定义变量count记录中元素,显然,count=queue.size时,满 count=0时,空 策略二:立Flag 初始令flag为false,true表示入队,false表示出满,则当前操作为入队;反之,为出 策略三:斩草除根 令front...
  • c++循环列队 初始化 入对 出 销毁 疏忽了长度为5的限制 请自行添加
  • 数据结构--循环列队

    2017-11-30 14:03:52
    * 循环列队类 */ public class MyCycleQueue { //底层使用数组 private long[] arr; //有效数据的大小 private int elements; //头 private int front; //队尾 private int end; /** * 默认构造方法...
  • C++实现循环列队的基本操作 初始化 入队 出 销毁 for(int i=Q.front;i;i++) 请改为for(int i=Q.front;i;i++)
  • 循环列队的循序结构

    千次阅读 2015-01-31 17:05:53
    //1.队列顺序结构的定义 #define MAXQSIZE 100 typedef struct { QElemType base[MAXQSIZE];//静态数组 ...将循序列臆造为一个环状空间。尾指针指向头指针 //2.在对满的情况下,rear指针和front
  • 如何判断循环队列队空? 队空:front=rear 如何盘对循环队列堆满? 队满:front=rear 那么问题就来了,队空和队满的判断条件相同,为了避免队满时产生队空的判断或者相反,我们需要修改队满条件使得队空和堆满...
  • 循环队列

    2015-04-20 18:15:14
    固定长度缓冲区的读写,循环队列通常是最好的选择。如果使用普通的队列来解决固定长度缓冲区的读写问题,当队列存满时删除最早进入队列的元素存在元素移动的问题这样会增加... //循环队列队头 Queue(int N){ ta
  • 循环队列front==rear

    千次阅读 2019-10-27 17:11:58
    循环队列队满和队空的条件都是front==rear,怎么区分这两者之间的差别? 方案一: 分析:该循环数列包含data数组、队头指针front和队中的元素个数count字段。初始时front和count均置为0.队空的条件为count0;队满的...
  • 循环队列简介

    2020-12-12 09:34:53
    由于存储空间有限,当设计循环队列时,需要考虑队满的情况,通常循环队列在队满时都是丢弃新数据,不再写入,但对于比如像实时信号采集系统,就需要覆盖旧数据,所以在设计时首先应该考虑该循环队列队满时是丢弃新...
  • //变化:顺序队列 变成 循环队列(关键:用取余操作实现在数组的范围内 和 循环队列队满条件 ,注意这里会多一个空余数据空间 ) //参考链接:https://www.cnblogs.com/curo0119/p/8608606.html // ...
  • 栈和队列---循环队列

    2020-05-26 23:24:49
    这是需要引入一种新的队列循环队列队首用font 标记,用tail标记队尾中最后一个元素之后的位置。 当队首和队尾重合时候说明队列是空的 front==tail 队列为空,(tail+1)%c==front 队列为满,这样会浪费一个空间 c是...
  • 循环队列概念:解决“假溢出”的...循环队列初始条件:队头指针(front)=队尾指针(rear)=0 循环队列队满条件:(rear+1)%size == front (size是顺序表的最大储存空间) 循环队列空条件:队头指针(rear)=队尾指针(fr...
  • //YHTriangle.cpp//输出杨辉三角形//算法思想:首先在循环队列中存放第三行的 1,2,1和第四行的1.//若循环队列队头元素和队头第二个元素均为1,则从队头删除一个1,在队尾插入两个1.//若不然,将队对头元素和队头第...
  • 队列 不存在物理的循环结构用软件方法实现 求模41mod 50 队列的顺序存储结构及实现 如何实现循环队列 0 1 2 3 4 入队 出队 a3 a4 front rear a6 队列 如何判断循环队列队空 队空的临界状态 队列的顺序存储结构及实现...
  • 如何判断循环队列队空 执行出队操作 队空front=rear 队列的顺序存储结构及实现 0 1 2 3 4 入队 出队 a3 front rear front 3.2 队列 如何判断循环队列队满 队满的临界状态 队列的顺序存储结构及实现 0 1 2 3 4 入队 ...

空空如也

空空如也

1 2 3 4 5
收藏数 88
精华内容 35
关键字:

循环队列队