欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

循环队列真的没那么难,就那么几个注意点,附Java代码及运行效果

程序员文章站 2022-06-06 22:26:42
...

1. 队列

队列是一种常见的线性数据结构,满足先进先出(First In First Out),简称为FIFO,第一次看到FIFO还以为是单片机的输出输出什么的,见笑了。数据结构不太了解的话可以看看我总结粗略的博客大凌的数据结构

 

2. 循环队列

2.1 为什么需要循环队列

在 大凌的数据结构 中,大凌简述了队列可通过数组和链表实现,且数组和链表各有各的优点。如果我们看中了数组,使用数组实现队列,那么随之而来的就需要我们“买单”。我们都知道在Java中,数组是静态分配的,如果一个数组初始化时大小确定,那么后期是更改不了数组容量的,直至没有引用指向该内存地址,这个数组地址才会被Java虚拟机回收。但我们为了使队列满足先入先出这个规则,那么每一次取出一个元素,只能让队列头指针后移,而不是真正地删除该内存地址,打字太啰嗦了,直接上图,如下图。

循环队列真的没那么难,就那么几个注意点,附Java代码及运行效果

通过上图我们可以了解,使用数组实现队列时,最终会出现明明队列的内存空间地址是空的,但是数据无法加入,也就是所谓的“假满队列”现象。

因此,为了高效地利用内存资源,“诞生”了循环队列。

 

2.2 循环队列的实现

由于循环队列的特殊,rear和front的更新、队列是否为空以及队列是否已满的判断条件变得不一样,接下来就详细地分析一下循环队列的实现。

循环队列的几点说明

① 循环队列使用数组实现;

 在初始化队列容量时,多分配一个,后面有用;

② 队列头指针 front 指向第一个元素的前一个元素,指针顺时针移动

③ 队列尾指针 rear 指向最后一个元素,指针顺时针移动

 

实现流程

1. 一定要看上面的4点说明再来看实现流程啊啊啊!!!假设构造一个容量为5的队列,那么多分配一个

    也就是实际生成一个容量为6的数组,初始化 front = 0, rear = 0此时是队列为空情况,front = rear

    此时实际的数组和循环队列对应图如下。

循环队列真的没那么难,就那么几个注意点,附Java代码及运行效果

2. 添加两个元素4和1,front指向第一个元素的前一个元素,rear指向最后一个元素,此时实际的数组和循环队列对应图如下。

循环队列真的没那么难,就那么几个注意点,附Java代码及运行效果

 

3. 删除一个元素,也就是取出先进入队列的元素 4,front还是指向第一个元素的前一个元素,rear还是指向最后一个元素。

    要说明的是,4其实还是在数组的第二个元素那里,只是访问不到了,则此时实际的数组和循环队列对应图如下。

循环队列真的没那么难,就那么几个注意点,附Java代码及运行效果

4. 添加四个元素8、3、7、2,front指向第一个元素前一个元素,rear指向最后一个元素注意:因为有一个空间是我们预留的,

    此时已是队列满情况,即 (rear + 1) = front;程序中真实判断队满的条件是 (rear + 1) % arr.length == front,后面再讲。

    有没有同学好奇rear怎么从数组的后面指向到前面来的呢?添加8 3 7后,rear指向最后一个元素7,rear = 5;

    添加元素2时,程序让rear继续自增加1,rear = 6,超出数组的最大索引?其实程序中是 rear = (++rear) % arr.length

    那么在添加元素2后,rear = 0;此时实际的数组和循环队列对应图如下。

循环队列真的没那么难,就那么几个注意点,附Java代码及运行效果

5. 最后我们再取出元素 1、8、3、7、2,队空,rear = front;此时实际的数组和循环队列对应图如下。

循环队列真的没那么难,就那么几个注意点,附Java代码及运行效果

 

 

2.3 循环队列的实现代码及运行效果

2.3.1 循环队列实现类的代码

class CircleQueue{
    private int front = 0;
    private int rear = 0;
    private int capcity;
    private int defaultCapcity = 30;

    String[] arr;
    CircleQueue(){
        // 预留了一个位置,所以多分配一个内存空间
        arr = new String[defaultCapcity + 1];
        capcity = defaultCapcity + 1;
    }

    CircleQueue(int s){
        // 预留了一个位置,所以多分配一个内存空间
        arr = new String[s + 1];
        capcity = s + 1;
    }

    void addData(String s){
        // 队满条件
        if(((rear + 1) % capcity) == front){
            System.out.println("Queue is full, can't add data");
            return;
        }
        // rear指向的就是最后一个元素,再添加元素需要先后移然后取模
        rear = (++rear) % capcity;
        arr[rear] = s;
    }

    String getData(){
        // 队空条件
        if(rear == front){
            System.out.println("Queue is empty, can't get data");
            return null;
        }
        // front指向的是第一个元素的前一个,所以取元素要先后移然后取模
        front = (++front) % capcity;
        return arr[front];
    }
}

 

2.3.2 队列容量为3的运行效果图

循环队列真的没那么难,就那么几个注意点,附Java代码及运行效果

循环队列真的没那么难,就那么几个注意点,附Java代码及运行效果

循环队列真的没那么难,就那么几个注意点,附Java代码及运行效果

 

相关标签: Java 循环队列