精华内容
下载资源
问答
  • 若希望循环队列中的元素都能得到利用,则需设置一个标志域tag,并以tag的值为0或1来区分头指针front和队尾指针rear相同时队列状态是还是。试编写与此结构相对应的入队和出算法。 front ==rear && ...

    题目:
    若希望循环队列中的元素都能得到利用,则需设置一个标志域tag,并以tag的值为0或1来区分队头指针front和队尾指针rear相同时队列状态是空还是满。试编写与此结构相对应的入队和出队算法。

    front ==rear && tag ==0,队空;
    front ==rear && tag ==1,队满;

    初始化:

    #define MaxSize 50;
    typedef struct{
        ElemType data[MaxSize];
        int front,rear,tag;
    }SqQueue;
    

    入队:

    bool EnQueue(SqQueue &Q,ElemType x){
        if(Q.tag == 1 && Q.front == Q.rear) return false; //队满不允许插入元素;
        
        //初始时,front=rear=-1,增加元素时,rear先加1再赋值;
        Q.rear = (Q.rear +1)%MaxSize; //需要插入元素的位置;
        Q.data[Q.rear] = x;
    	//如果队满;
    	Q.tag =1;
        return true;
    }
    

    出队:

    bool DeQueue(SqQueue &Q,ElemType &x){
        if(Q.tag ==0 && Q.front ==Q.rear) return false; //队空,不再删除元素;
        
        //假设front初始时为-1,则删除元素时,front先加1再删除元素;
        Q.front = (Q.front+1)%MaxSize;
        x = Q.data[Q.front];
        //如果队空;
        Q.tag =0;
        return true;
    }
    
    展开全文
  • 首先我们定义一个具有基本操作方法的Queue类,在这个类中我们设置了一个bool型的变量tag,通过判断tag的值来判断队列是否为、是否为。具体是:rear==front&&!tag为,rear==front&...

    我们首先需要了解的是:循环队列的实现有三种方式

    1. 浪费一个元素的存储空间:front指向队首的实际位置,rear指向实际位置的下一个位置,front==rear时为空,(rear+1) % m == front时为满
    2. 使用标记tag,front指向队首实际位置,rear指向队尾实际位置的下一个位置,入队时tag=1,出队时tag=0,当front == rear && tag == 0时队空,当front == rear && tag == 1时队满
    3. 使用front,rear, length作为判断队空队满的标志,这样就不用浪费一个元素的存储空间了,和tag的作用是一样的,front指向队首实际位置,rear指向队尾实际位置

    这里我只实现一下第二种:

    首先我们定义一个具有基本操作方法的Queue类,在这个类中我们设置了一个bool型的变量tag,通过判断tag的值来判断队列是否为空、是否为满。具体是:rear==front&&!tag为空,rear==front&&tag为满。
    queue.h如下:

    #ifndef QUEUE_H
    #define QUEUE_H
    
    #include<iostream>
    using namespace std;
    
    template<class T>
    class Queue {
    private:
        int maxSize;                           //存放队列数组的大小
        int front;                             //表示队头所在位置的下标
        int rear;                              //表示队尾所在位置的下标
        int *queue;                            //存放类型为T的队列元素的数组
        bool tag;                              //0为空,1为不空
    public:
        Queue(int size);
        ~Queue() {
        delete[] queue;
        }
        void Clear();                          //清空队列
        bool EnQueue(const T item);            //item入队,插入队尾
        bool DeQueue(T & item);                //返回队头元素,并删除该元素
        bool GetFront(T & item);               //返回队头元素但不删除
        void disPlay();                        //输出队列
    };
    
    template<class T>
    Queue<T>::Queue(int size) {
        maxSize = size;
        tag = 0;
        queue = new T[maxSize];
        front = rear = 0;
    }
    
    template<class T>
    void Queue<T>::Clear() {
        front = rear;
        tag = 0;
    }
    
    template<class T>
    bool Queue<T>::EnQueue(const T item) {
        if (rear==front&&tag) {
            cout << "队列已满,溢出!" << endl;
            return false;
        }
        queue[rear] = item;
        rear = (rear + 1) % maxSize;
        tag = 1;
        return true;
    }
    
    template<class T>
    bool Queue<T>::DeQueue(T & item) {
        if (rear==front&&!tag) {
            cout << "队列为空,溢出!" << endl;
            return false;
        }
        item = queue[front];
        front = (front + 1) % maxSize;
        tag = 0;
        return true;
    }
    
    template<class T>
    bool Queue<T>::GetFront(T & item) {
        if (rear==front&&!tag) {
            cout << "队列为空,溢出!" << endl;
            return false;
        }
        item = queue[front];
        return true;
    }
    
    template<class T>
    void Queue<T>::disPlay() {
        if (rear==front&&!tag) {
            cout << "队列为空!" << endl;
            return;
        }
        if (front == rear&&tag!=0) {
            for (int i = 0; i < maxSize; i++) {
                cout << queue[i] << " ";
            }
        }
        for (int i = front;; i = (i + 1) % maxSize) {
            if (i == rear)
                break;
            cout << queue[i] << " ";
        }
        cout << endl;
    }
    #endif // !QUEUE_H
    
    展开全文
  • 循环队列判断队满队空的条件

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

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

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

    展开全文
  • 循环队列中判断队满队空

    万次阅读 多人点赞 2016-04-02 11:16:38
    在引用循环队列前,我们需要了解队列是如何线性实现的。 简单地讲,便是当队列为时,front = rear = 0,每当插入元素尾...我们可以发现,当循环队列属于上图的d1情况时,是无法判断当前状态是队空还是队满。为了

    在引用循环队列前,我们需要了解队列是如何线性实现的。
    这里写图片描述
    简单地讲,便是当队列为空时,front = rear = 0,每当插入元素尾指针+1,删除元素是头指针-1。但是,我们会发现一个问题,如上面的第四个图,0,1,2三个空间并没有使用。因此,为了占用该空间,我们使用了循环队列来实现。
    循环队列原理图:
    这里写图片描述
    我们可以发现,当循环队列属于上图的d1情况时,是无法判断当前状态是队空还是队满。为了达到判断队列状态的目的,可以通过牺牲一个存储空间来实现。
    如上图d2所示,
    队头指针在队尾指针的下一位置时,队满。 Q.front == (Q.rear + 1) % MAXSIZE 因为队头指针可能又重新从0位置开始,而此时队尾指针是MAXSIZE - 1,所以需要求余。
    当队头和队尾指针在同一位置时,队空。 Q.front == Q.rear;

    以下是实现的代码:

    #include <stdio.h>
    #include <malloc.h>
    #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; 
    }
    
    展开全文
  • 判断队列为或者为

    千次阅读 2020-08-11 19:15:20
    因此只凭等式front=rear无法判断队空还是队满。 有两种方法处理上述问题: (1)另设一个标志位以区别队列是还是。 (2)少用一个元素空间,约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“...
  • 为了方便对于循环队列进行队空队满判断,牺牲一个存储单元。记rear、head分别为队尾头指针则: 队满:(rear+1)%maxsize=head 队空:rear=head 插入元素后,rear=(rear+1)%maxsize 删除元素后,head=(head+1...
  • 如何判断循环列为队空or队满

    千次阅读 多人点赞 2020-02-16 13:18:35
    什么是循环队列 循环队列就是将队列存储空间的最后一个位置绕到第一个位置,首尾相连形成逻辑上的环状空间,供队列循环使用。 循环队列可以更简单防止假溢出的发生,但队列大小是固定...如何判断循环列为队空or...
  • 在引用循环队列前,我们需要了解队列是如何线性实现的。 简单地讲,便是当队列为时,front = rear = 0,每当插入元素尾指针+1,...我们可以发现,当循环队列属于上图的d1情况时,是无法判断当前状态是队空还是队满
  • 循环队列设置tag标志域判断满队空 算法思想: tag等于0的情况下,若因删除导致Q.Rear==Q.Front则为队 tag等于1的情况下,若因插入导致Q.Rear==Q.Front则为队满 核心代码: //tag等于0的情况下,若因删除...
  • front表示头指针(指向队列内首元素) rear表示队尾指针(指向队列内尾元素的下一个位置) m表示队列的容量 ...队空:front=rear 队满:front=(rear+1)%m 队列内元素个数:(rear - front + m) % m ...
  • (纠错:上图中出队列应该是:x=sq[front++])简单地讲,便是当队列为时,front = rear = 0,每当插入元素尾指针+1,删除元素是头指针-1。但是,我们会发现一个问题,如上面的第四个图,0,1,2三个空间并没有使用...
  • 循环队列实现(通过设置标志位tag位判断空满队)
  • 线性表是数据结构中比较重要的一种逻辑结构,插入删除操作是线性表的基本操作,当进行这些操作时,不仅需要考虑插入、删除的位置是否合法性,仍然需要考虑‘’与‘’这两种状态,但是,由于栈和队列都是受限制的...
  • * 采用设置标志位的方法区别循环队列的判和判 * 包括入队、出和判队列是否为 * */ private Object[] queueElem; //队列存储空间 private int flag = 0; //标志变量,当入队操作成功
  • 循环队列判断满

    千次阅读 2013-09-22 00:08:32
    因此,我们无法通过front=rear来判断队列“”还是“”。 注:先进入的为‘头’,后进入的为‘尾’。 解决此问题的方法至少有三种: 其一是另设一个布尔变量以匹别队列的; 其二是少用一个元素...
  • 主要介绍了C语言数据结构之判断循环链表的相关资料,希望通过本文能帮助到大家,让大家掌握这部分内容,需要的朋友可以参考下
  • 循环列队队空的判定

    千次阅读 2014-09-21 10:18:13
    循环队列的队空队满的条件 分类: 数据结构与算法2010-07-07 21:31 8976人阅读 评论(3) 收藏 举报 ...为了方便起见,约定:初始化建空队时,令 ... 因此只凭等式front=rear无法判断队空还是
  • 循环列队队空判定

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

    千次阅读 2017-03-23 08:23:54
    因此,我们无法通过front=rear来判断队列“”还是“”。 注:先进入的为‘头’,后进入的为‘尾’。 解决此问题的方法至少有三种: 其一是另设一个布尔变量以匹别队列的; 其二是少用一个元素的空间,约定...
  • 格雷码下的 fifo空满判断

    千次阅读 2019-07-19 20:46:02
     使用gray码解决了一个问题(降低亚稳态),但同时也带来另一个问题,即在格雷码域如何判断空。  对于“空”的判断依然依据二者完全相等(包括MSB);  而对于“”的判断,如下图,由于gray码除了MSB外,...
  • 循环队列:判断队列的3种方法

    千次阅读 多人点赞 2020-02-14 19:32:18
      一.少用一个存储位置   第一种情况: ...比如下图有下标了,当队列时,显然条件就不能判断了,就要用到另一种判断。   第二种情况: 当列为时条件:rear == front 当队列时条件为:(rear+1)...
  • 循环队列的队空队满的条件

    千次阅读 2014-07-19 00:29:15
     因此只凭等式front=rear无法判断队空还是队满。 有两种方法处理上述问题:  (1)另设一个标志位以区别队列是还是。  (2)少用一个元素空间,约定以“队列头指针front在队尾指针rear的下一个位
  • 列为时:rear= =front 队列时:(rear+1)%maxSize= =front 不少一个存储位置时:加一个标志flag或者计数的count 入队时flag=true 出时flag=false 队满:rear= =front&flag 队空:rear= =front&!...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 146,411
精华内容 58,564
关键字:

判断队空队满