精华内容
下载资源
问答
  • 循环队列元素个

    2021-01-03 22:23:04
    @循环队列元素个数 若f指向第一个元素,r指向最后一个元素的下一个元素。队列长度为n。 情况1:rf的上面 此时元素个数为r-f 情况2:rf下面 此时元素个数为 r-0 + n-f 即r-f+n 元素个数不可能超过n。 故综合两种...

    @循环队列元素个数

    若f指向第一个元素,r指向最后一个元素的下一个元素。队列长度为n。

    情况1:r在f的上面在这里插入图片描述
    此时元素个数为r-f

    情况2:r在f下面

    在这里插入图片描述
    此时元素个数为 r-0 + n-f 即r-f+n

    元素个数不可能超过n。
    故综合两种情况可知要取模。
    即(r-f+n)%n。

    展开全文
  • 队列,循环队列为什么用空一个元素的位置 队列介绍 1)队列是一个有序列表,可以用数组或是链表表示。 2)遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出。 front及rear分别记录队列前后端...

    队列,循环队列为什么用空一个元素的位置

    队列介绍

    1)队列是一个有序列表,可以用数组或是链表表示。

    2)遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出。

    • front及rear分别记录队列前后端的下标,front随着数据的输出而改变,而rear则是随着数据输入而改变。
    image-20200708160054824

    代码实现

    import java.util.Scanner;
    
    public class ArrayQueueDemo {
        public static void main(String[] args) {
            //创建一个队列
            ArrayQueue arrayQueue = new ArrayQueue(3);
            char key = ' ';//接受用户输入
            Scanner scanner = new Scanner(System.in);
            boolean loop = true;
            //输出一个菜单
            while(loop){
                System.out.println("s(show):显示队列");
                System.out.println("e(exit):退出程序");
                System.out.println("a(add):添加数据到队列");
                System.out.println("g(get):从队列取出数据");
                System.out.println("h(head):查看队列头的数据");
                key = scanner.next().charAt(0);
                switch (key){
                    case 's':
                        arrayQueue.showQueue();
                        break;
                    case 'a':
                        System.out.println("请输入一个数字:");
                        int value = scanner.nextInt();
                        arrayQueue.addQueue(value);
                        break;
                    case 'g':
                        try {
                            int res = arrayQueue.getQueue();
                            System.out.println("取出数据:"+res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h':
                        try {
                            int res = arrayQueue.headQueue();
                            System.out.println("队列头数据:"+res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e':
                        scanner.close();
                        loop = false;
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出");
        }
    }
    
    class ArrayQueue{
        private int maxSize;
        private int front;
        private int rear;
        private int[] arr;//模拟队列,该数组用于存放数据
    
        //创建队列的构造器
        public ArrayQueue(int arrMaxSize){
            maxSize = arrMaxSize;
            arr = new int[maxSize];
            front = -1;//指向队列头部(第一个数据的前面)
            rear = -1;//指向队列尾部(最后一个数据)
        }
        //判断队列是否满
        public boolean isFull(){
            return rear == maxSize-1;
        }
        //判断队列是够为空
        public boolean isEmpty(){
            return front==rear;
        }
        //添加数据到队列
        public void addQueue(int n){
            if(isFull()){
                System.out.println("队列已满,不可加入数据");
                return;
            }
            rear++;
            arr[rear] = n;
        }
        //从队列中取出数据
        public int getQueue(){
            if(isEmpty()){
                throw new RuntimeException("队列为空,不可取出数据");
            }
            front++;
            return arr[front];
        }
        //显示队列的中的所有数据
        public void showQueue(){
            if(isEmpty()){
                System.out.println("队列为空");
                return;
            }
            for (int i = 0; i <arr.length ; i++) {
                System.out.print(i+":"+ arr[i]+"\n");
            }
        }
        //显示队列的头数据,不是取出数据
        public  int headQueue(){
            if(isEmpty()){
                System.out.println("队列为空");
                throw new RuntimeException("队列为空");
            }
            return arr[front+1];
        }
    }
    
    

    问题分析并优化:

    • 目前数组使用了一次就不能用了,没有达到复用的效果

    • 我们要使用算法,将目前的数组改成一个环形的队列 取模%

    数组环形队列思路:

    1、front变量的含义做一个调整:front就指向队列的第一个元素,就是是说arr[front]就是队列的第一个元素,front初始值为0;

    2、rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置,rear的初始值为0;

    3、队列满的条件:(rear+1)%maxSize ==front

    4、队列空的条件是:rear == front

    5、此时队列的有效长度是: (rear+maxSize-front)%maxSize

    遇到的问题(循环队列空一个元素的位置)

    在得到队列满的条件:(rear+1)%maxSize ==front时,我充满了疑惑,怎么算都觉得在rear已经表示最后元素的后一位了,这种情况下加一肯定是不对的,后来我查了一些资料。
    别人规定的循环队列

    那么,循环队列为什么用空一个元素的位置呢???

    这个是根据需要来用的
    循环队列中,由于入队时尾指du针向前追赶头指针;zhi出队时头指针向前追赶尾指针,造成dao队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是"空"还是"满"。
    解决这个问题的方法至少有三种:
    ①另设一布尔变量以区别队列的空和满;
    ②少用一个元素的空间。约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满(注意:rear所指的单元始终为空);
    ③使用一个计数器记录队列中元素的总数(即队列长度)。

    代码实现(循环队列)

    import java.util.Scanner;
    
    public class CicleArrayQueueDemo {
        public static void main(String[] args) {
    
            System.out.println("测试数组模拟环形数据");
            CircleArray queue = new CircleArray(4);//空出一个位置,其队列有效数据为3;
            char key = ' ';
            Scanner scanner = new Scanner(System.in);
            boolean loop = true;
            while(loop){
                System.out.println("s(show):显示队列");
                System.out.println("e(exit):退出程序");
                System.out.println("a(add):添加数据到队列");
                System.out.println("g(get):从队列取出数据");
                System.out.println("h(head):查看队列头的数据");
                key = scanner.next().charAt(0);
                switch (key){
                    case 's':
                        queue.showQueue();
                        break;
                    case 'a':
                        System.out.println("请输入一个数字:");
                        int value = scanner.nextInt();
                        queue.addQueue(value);
                        break;
                    case 'g':
                        try {
                            int res = queue.getQueue();
                            System.out.println("取出数据:"+res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h':
                        try {
                            int res = queue.headQueue();
                            System.out.println("队列头数据:"+res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e':
                        scanner.close();
                        loop = false;
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出");
    
        }
    
        static class CircleArray{
            private int maxSize;
            private int front;//front就指向队列的第一个元素,就是是说arr[front]就是队列的第一个元素,front初始值为0;
            private int rear;//rear指向队列的最后一个元素的后一个位置,rear的初始值为0;
            private int[] arr;//模拟队列,该数组用于存放数据
    
            public CircleArray(int arrMaxSize){
                maxSize = arrMaxSize;
                arr = new int[maxSize];
            }
    
            //判断队列是否满
            public boolean isFull(){
                return (rear + 1)%maxSize ==front;
            }
            //判断队列是够为空
            public boolean isEmpty(){
                return front==rear;
            }
            //添加数据到队列
            public void addQueue(int n){
                if(isFull()){
                    System.out.println("队列已满,不可加入数据");
                    return;
                }
                arr[rear] = n;
                rear = (rear+1)%maxSize;
            }
            //从队列中取出数据
            public int getQueue(){
                if(isEmpty()){
                    throw new RuntimeException("队列为空,不可取出数据");
                }
                int value = arr[front];
                front = (front+1) % maxSize;
                return value;
            }
            //求出当前队列的个数
            public int arrCount(){
                return (rear+maxSize-front)%maxSize;
            }
            //显示队列的中的所有数据
            public void showQueue(){
                if(isEmpty()){
                    System.out.println("队列为空");
                    return;
                }
                for (int i = front; i <front+arrCount(); i++) {
                    System.out.print((i%maxSize)+":"+ arr[i%maxSize]+"\n");
                }
            }
            //显示队列的头数据,不是取出数据
            public  int headQueue(){
                if(isEmpty()){
                    System.out.println("队列为空");
                    throw new RuntimeException("队列为空");
                }
                return arr[front];
            }
    
        }
    }
    
    展开全文
  • 循环队列元素个数计算公式

    万次阅读 2019-07-12 10:14:26
    因为循环对列,rear不一定比front大 如果rear<...为了用一个表达式同时表达两者,用(rear-front+maxsize)%maxsize 假设maxsize=10 rear=1 front=9,那么结果是2 rear=9 front=1,那么结果是8 ...

     

    因为循环对列,rear不一定比front大

    如果rear<front结果是rear-front+maxsize 
    如果rear>front结果是rear-front
    为了用一个表达式同时表达两者,用(rear-front+maxsize)%maxsize
    假设maxsize=10
    rear=1 front=9,那么结果是2
    rear=9 front=1,那么结果是8

     

    reference:

    https://ask.csdn.net/questions/256277

    展开全文
  • 逻辑上把顺序存储的队列想象成一个环,就是循环队列循环队列仍是顺序存储,只是元素可以循环存储给定的存储空间。 前篇文章,顺序存储队列基本操作 所描述的队列的存储空间只可以使用次,一些元素出队...

    循环队列定义

    在逻辑上把顺序存储的队列想象成一个环,就是循环队列。
    循环队列仍是顺序存储,只是元素可以循环存储在给定的存储空间。

    前篇文章,顺序存储队列基本操作 所描述的队列的存储空间只可以使用一次,在一些元素出队之后,空出来的空间没有办法再次存储,造成浪费,所以更多选择循环队列。

    两者的内存中的存储一样,只是逻辑上将两者分为了非循环和循环。

    循环队列判空、判满

    判空和判满可以有多种方式,根据自己的设计选择即可。

    第一种方式:
    判空:当首尾指针指向同一位置时,队列为空。
    判满:当尾指针+1 = 首指针,队列已满。
    (这种方式是牺牲一个存储空间来判断队列是否已满)
    注意:判满时 需要对maxsize取余,否则rear可能超出maxsize。

    第二种方式:
    单独设置一个length变量,来存储队列的长度
    判空:length = 0
    判满:length = maxsize

    前篇文章,顺序存储队列基本操作 就是利用length判断长度

    第三种方式
    设置一个tag参数 tag=1 时队满;tag= 0 时对空。
    判空:当首尾指针指向同一位置时,队列为空。
    判满:tag=1 时队满;tag= 0 时对空。

    循环队列长度

    length = (rear + maxsize - front)%maxsize;

    代码实现

    /**
     * 循环队列的基本操作
     */
    #include <cstdio>
    
    #define maxsize 6  //定义队列中元素的最大个数
    /**
     * 定义结构
     */
    typedef struct {
        int data[maxsize];  //存放队列元素
        int front,rear;     //对头指针和队尾指针   数组下标也可以表示指针,可以不加*
    }SqQueue;
    
    /**
     * 初始化队列,构造一个空的队列
     */
    void initQueue(SqQueue &Q){
        Q.front = Q.rear = 0;   //初始化队首队尾指针,构建空的队列
    }
    /**
     * 判断队列是否为空
     */
    bool QueueIsEmpty(SqQueue Q){
        if(Q.front == Q.rear){  //队列为空
            printf("队列为空 \n");
            return true;
        }else{
            return false;
        }
    }
    /**
     * 入队操作
     * @param Q
     * @param value 入队的值
     */
    void enQueue(SqQueue &Q,int value){
        if(Q.front == (Q.rear + 1)%maxsize ){//判断队列是否已满
            printf("队列已满 \n");
            return;
        }
        Q.data[Q.rear] = value; //队尾指针指向新入队的数据
        Q.rear = (Q.rear+1)%maxsize;//rear指针+1 ,此处求余目的是不超出给定的maxsize
    }
    /**
     * 出队操作,返回出队元素
     * @param Q
     */
    int outQueue(SqQueue &Q){
        if(QueueIsEmpty(Q)){ //判断队列是否为空
            printf("队列为空 \n");
            return 0;
        }
        int x = Q.data[Q.front]; //要出队的元素
        Q.front = (Q.front+1)%maxsize;  //首指针后移一位
        return x;
    }
    /**
     * 读队头元素,并返回
     * @return
     */
     int getHead(SqQueue Q){
         return Q.data[Q.front];
     }
    /**
     * 创建完整队列
     * @param Q
     */
    void creatQueue(SqQueue &Q){
        //初始化
        initQueue(Q);
        
         int x;
         scanf("%d",&x);
         while(x != 9999){
             enQueue(Q,x);
             if(Q.front == (Q.rear + 1)%maxsize){
                 break;
             }
             scanf("%d",&x);
         }
    
     }
     /**
      * 打印
      * @return
      */
     void print(SqQueue Q){
         for (int i = Q.front; i < Q.rear; ++i) {
             printf("队列中存储的值 %d \n",Q.data[i]);
         }
         /**
          * 由于是循环存储数据,rear指针可能指向2的位置,
          * front指针指向5的位置(这种情况是尾指针跑到了首指针前面,会出现负数)
          * 负数不能取余,所以+maxsize,保证数据的正确,取余会把加的maxsize再去掉
          */
         int length = (Q.rear+maxsize - Q.front)%maxsize;
         printf("队列length %d \n",length);
      }
    int main(){
        SqQueue Q;
        printf("--------创建完整队列(入队)--------- \n");
        creatQueue(Q);
        printf("--------打印--------- \n");
        print(Q);
        printf("--------获取队头元素--------- \n");
        int head1 = getHead(Q);
        printf("队头元素 - %d \n",head1);
        printf("--------出队--------- \n");
        int out = outQueue(Q);
        printf("出队元素 - %d \n",out);
        printf("--------获取队头元素--------- \n");
        int head2 = getHead(Q);
        printf("队头元素 - %d \n",head2);
    
        return 0;
    }
    

    测试结果

    --------创建完整队列(入队)---------
    12
    13
    14
    15
    16
    17
    18
    9999
    --------打印---------
    队列中存储的值 12
    队列中存储的值 13
    队列中存储的值 14
    队列中存储的值 15
    队列中存储的值 16
    队列中存储的值 17
    队列中存储的值 18
    队列length 7
    --------获取队头元素---------
    队头元素 - 12
    --------出队---------
    出队元素 - 12
    --------获取队头元素---------
    队头元素 - 13
    
    

    顺序存储队列基本操作:https://blog.csdn.net/qq_35963993/article/details/106080380

    展开全文
  • 循环队列

    2020-02-21 14:47:21
    为充分利用向量空间,克服"假溢出"现象的方法是:将... 循环队列就是将队列存储空间的最后一位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列结构中,当存储空间的最后一位置已被使用而再...
  • CircularPriorityQueue:循环优先级队列结构的实现及其基本功能,例如添加和删除元素,显示第一个元素,容量和当前元素
  • 队列——循环队列

    2020-04-19 10:57:29
    循环队列一个大小确定的特殊队列,它的特殊体现循环,之前提到的普通队列,我们是用链表来实现的,这里,由于循环队列一个长度确定的队列,所以我们可以拿顺序表来实现。循环队列的操作与普通队列类似,不过...
  • 循环队列的操作(循环队列

    千次阅读 2013-10-17 18:58:46
    循环队列满时,将循环队列中的所有元素全部出队,并按存入的先后顺序同一行内依次输出,即每行输出m个元素,每个元素后输出一空格。   Input 有多组数据,每组第一行为整数序列的个数n和循环队列的最大容
  • 循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。中文名循环队列外文名Circular Queue领域实现方式有关术语特点大小固定循环队列简介编辑语音循环队列就是将队列存储空间的最后...
  • 队列-循环队列

    2016-06-02 01:14:59
    循环队列1.介绍队列就是一能够实现FIFO (先进先出)的存储结构。 队列分为链式队列和静态队列;...当队列不为空时,head指向队列的第一个元素,tail指向队列最后一个元素的下一位置 当队列为空时
  • 循环队列和链式结构队列

    千次阅读 2017-02-27 13:22:04
    一、循环队列的基础知识 ...(2)当队列不为空时,front指向队列的第一个元素,rear指向队列最后一个元素的下一位置; (3)当队列为空时,front与rear的值相等,但不一定为零; 3.循环队列入队的
  • 循环队列应用

    2018-11-06 23:10:50
    郭艳数据结构作业之循环队列的应用与斐波拉契。题目如下: K_Fib.h文件中K_Fib()函数实现计算并输出K阶斐波那契序列...算法执行结束时,留在循环队列中的元素应是所求K阶斐波那契序列中的最后K项f(n-k+1),…,fn。
  • 泛型循环队列

    2021-06-12 20:01:54
    在循环队列结构中,当存储空间的最后一位置已被使用而再要进入队运算时,只需要存储空间的第一个位置空闲,便可将元素加入到第一个位置,即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生,...
  • 循环队列的介绍

    2020-06-26 22:49:48
    队列 队列就是一能够实现“先进先出”的存储...当队列不为空时,head指向队列第一个元素,tail指向队列最后一个元素的下一位置,也就下一个元素入队时要放在rear的位置上,而tail“顺延” 当tail == head 时,

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 130,216
精华内容 52,086
关键字:

循环队列第一个元素在哪