循环队列

我们再用队列得时候不知道发没发现这样一个问题.

这是一个只有三个位置得队列,在进行三次加入(addqueue)操作和三次取出(get)操作之后再进行加入操作时候的样子.明显可以看到,队列已经无法使用了.队列是靠rear和front指针来进行操作的.这两个指针只能向后运动,并不能向前移动,所以他们走过的数组元素就再也不能利用了.

也就是说队列只能用一次.加入,退出,然后就结束了.

当然了,着对于很多问题是不被原谅的.

所以这就要引用一个全新的概念,环形队列.

看一下这个吧,一看就知道这个东西可以循环利用.

比较一下:

来自百度百科

看见了吧,一个是长方形的,一个是圆形的.

但是我们知道计算机中并不存在圆形数组,这种环形队列是构建再逻辑上的.用数学来实现,其本质就是可以让rear走过队尾的时候能回到数组的前方,继续利用被front走过得数组元素.

我们主要看一眼她和普通队列的变化.

首先是构造

class CircleArray{

    private int maxSize;//表示数组的最大容量

    //front变量的含义做一个调整，front指向队列的第一个元素。也就是说arr【front】就是队列第一个元素，

    //初始值为0

    private int front;//队列头

    //rear变量的含义做一个调整，rear指向队列的最后一个元素的后一个位置。因为我希望空出一个空间作为约定。

    //一位有了这个空格就可以比较轻松地知道，空格前面的是rear后面的是front

    //初始值为0

    private int rear;//队列尾

    private int arr[];//该数据用于存放数据，模拟队列

}

并没有什么变化,就像我刚才说到的,环形队列是用逻辑和数学实现的,而不是从物理地址(也就是改变队列的载体--数组来实现的.)

在这里有了一部分变化()

rear由指向队尾最后一个元素变为指向队尾前一个元素.

front由指向队列头部前一个元素,改为指向队列头部.

    这实际上是为了方便区分一个队列得首和尾,并不一定要遵守.

变化发生在构造函数中,要知道实际上你所能提供的数据只有一个队列大小,rear,front这些东西

全是通过构造函数在构造之初就构建得,并不能赋值.

 public CircleArray(int maxSize) {

        this.maxSize = maxSize;

//        this.maxSize = maxSize;

        arr=new int[maxSize];

        front=0;

        rear=0;

    }

然后还是增加模块.首先判定队列是否为满

在这里判定队列为满得情况发生了变化,因为现在是环形列表,所以rear指针是不可以再用maxsize进行操控了.(因为如果再用maxsize唯一的结果就是在rear指针指到maxsize之后就不再移动了,那环形列表就不存在了)

所以判断得标准将会转换,什么时候为满呢.

rear+1-front=maxsize

但是并不完善,因为就像在之前说过的一样,在逻辑上是环形,在现实中却还是一个普通的数组.

结果java中又恰恰不存在指针这个东西,所以rear和front虽然被称为指针,但是实际上确实两个int类型得数据,用作数组的下标.

所以会出现这种情况就是front的标号大于rear的标号,那么如果用

rear+1-front=maxsize的唯一结果恐怕就不再准确了.

所以我们必须换一种安全的办法

(rear+1)%maxsize=front

emmm字有点丑,将就着看.

在这个图中模拟了其中一种情况,我们发现,rear在front之下会出现问题.

所以代码应该这么写

 //因为队满会让整个队列都站上。所以理论上rear+1的得数应该是0也就是front（注意这里的rear是数组的下标，不是地址。所以说rear加上必须存在的1就得到了整个的数量。）

    public boolean isFull() {

        return (rear+1)%maxSize==front;

    }

那么回到增加模块的说法上来.

增加模块也产生了变化,

这里又要老生常谈一下,环形队列并不是指队列的主体数组被首位相接,从物理上连接成是环形,这是由数学完成的.

如何让rear越过maxsize大小之后重新出现在数组开头.

 rear=(rear+1)%maxSize;

![fullsizerender(7)](C:\Users\22643\Documents\Tencent Files\2264381489\FileRecv\MobileFile\fullsizerender(7).jpg)

如图,就是这样办到的.

 public void addQueue(int a){

        //判断队列不为空

        if(isFull()){

            System.out.println("队列满，不能加入数据");

            return;

        }

        //直接将数据加入

        arr[rear]=a;//赋值

        //将rear后移，这里必须考虑取模

        rear=(rear+1)%maxSize;//加入rear到了这个数组的最后一位，此时rear+1在对他跟maxsize取余就直接让rear等于数组开头的值了。

        //加入说arr数组长5，front在3号位置（下标为2），rear的下标为4的时候，rear+1是5对他%maxsize，得出的数是0，这就用逻辑的思想来形成了一个圆环，

        // 而非在地址上进行什么操作。

    }

所以这就做到了.

然后是空值

空值的变化不大,还是那一出

 //判断队列是否为空

    public boolean isEmpty(){

        return rear==front;

    }

取值有一点小小的变化因为涉及到front指针的移动,所以也要考虑越过maxsize的情况

 //获取队列的值

    public int getQueue(){

        if (isEmpty()){

            System.out.println("栈空了！");

//            return -1;这个不行，因为这样的话，只能返回-1

            throw new RuntimeException("队列空。");

        }

      //这里需要分析出front是指向队列的第一个元素

        //1.先把front对应的值保留在一个临时变量

        //2.front后移,考虑取模

        //3.将临时保存的变量返回

        int value=arr[front];

        front=(front+1)%maxSize;//对于front指针也是一样的，要是加的数量超过了maxSize就要靠取模来返回之前曾经走过的位置了

        return value;

    }

这里要解释一下这个front+1.

这个部分的主要原因是因为之前的设置,我们设置了一个不装任何数据的数组元素.所以无论是front还是rear都要加上这个去再去取余.

(你可以理解为累积木,这个就是一个方块,必须加上)

以上是主要产生变化的地方.

下面就是几个必要的功能

显示所有数据的功能

 //显示队列的所有数据

    public void showQueue(){

        if (isEmpty()){

            System.out.println("队列是空的。");

        }

        //思路：从front开始遍历，遍历多少个元素。

        for (int i = front; i <front+size() ; i++) {

            //i是从front开始的，不断地加一有可能让他超过maxSize，所以取模就让她回道头部了。

            System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]); //这个要学习一下。

        }

    }

显示队列有效个数的功能

  //当前队列有效数据的个数

    public int size(){

        return  (rear+maxSize-front)%maxSize;//说白了就是rear-front的绝对值的一种表示形式。

        //rear=1

        //front=0

        //maxSize=3

    }

显示队列头

//显示队列头数据，注意不是取出数据

    public int headQueue(){

        if (isEmpty()){

            System.out.println("队列空的，没有数据");

            throw new RuntimeException("队列是空的");

        }

        return arr[front];//因为队列头front永远指的是队列中的第一个数

    }

最后把完整代码放一下.

package queue;

import java.util.Scanner;

public class CircleArrayQueueDemo {

    public static void main(String[] args) {

        System.out.println("环形队列");

        //环形队列

        CircleArray arrayQueue = new CircleArray(4);//设置3，其队列的最大数字是3

        char key = ' ';//接受用户的输入

        Scanner scanner = new Scanner(System.in);

        boolean loop = true;

        //输出一个菜单

        while (loop) {

            System.out.println("s:显示队列");

            System.out.println("e:退出程序");

            System.out.println("a：添加数据到队列");

            System.out.println("g：从队列取出数据");

            System.out.println("h：查看队列头的数据");

//            System.out.println("s:显示队列");

            key = scanner.next().charAt(0);

            switch (key) {

                case 's':

                    arrayQueue.showQueue();

                    break;

                case 'a':

                    System.out.println("输出一个数");

                    int value = scanner.nextInt();

                    arrayQueue.addQueue(value);

                    arrayQueue.showQueue();

                    break;

                case 'g'://取出数据

                    try {

                        int res = arrayQueue.getQueue();

                        System.out.printf("取出的数据是%d\n,", res);

                    } catch (Exception e) {

                        System.out.println(e.getMessage());

                    }

                    break;

                case 'h'://查看队列头的数据

                    try {

                        System.out.println(arrayQueue.headQueue());

                    } catch (Exception e) {

                        System.out.println(e.getMessage());

                    }

                    break;

                case 'e'://退出

                    scanner.close();

                    loop = false;

                    break;

                default:

                    break;

            }

        }

        System.out.println("程序退出~~~时");

    }

}

class CircleArray{

    private int maxSize;//表示数组的最大容量

    //front变量的含义做一个调整，front指向队列的第一个元素。也就是说arr【front】就是队列第一个元素，

    //初始值为0

    private int front;//队列头

    //rear变量的含义做一个调整，rear指向队列的最后一个元素的后一个位置。因为我希望空出一个空间作为约定。

    //一位有了这个空格就可以比较轻松地知道，空格前面的是rear后面的是front

    //初始值为0

    //不留这个位置（rear不指向队列最后一个元素后一个位置的话）的唯一结果就是rear和front会撞在一起，撞在一起的两个指针会导致front原先有的被覆盖掉。

    private int rear;//队列尾

    private int arr[];//该数据用于存放数据，模拟队列

    public CircleArray(int maxSize) {

        this.maxSize = maxSize;

//        this.maxSize = maxSize;

        arr=new int[maxSize];

        front=0;

        rear=0;

    }

    //判断队列是否满

    //因为队满会让整个队列都站上。所以理论上rear+1的得数应该是0也就是front（注意这里的rear是数组的下标，不是地址。所以说rear加上必须存在的1就得到了整个的数量。）

    public boolean isFull() {

        return (rear+1)%maxSize==front;

    }

    //判断队列是否为空

    public boolean isEmpty(){

        return rear==front;

    }

    //添加数据到队列

    public void addQueue(int a){

        //判断队列不为空

        if(isFull()){

            System.out.println("队列满，不能加入数据");

            return;

        }

        //直接将数据加入

        arr[rear]=a;//赋值

        //将rear后移，这里必须考虑取模

        rear=(rear+1)%maxSize;//加入rear到了这个数组的最后一位，此时rear+1在对他跟maxsize取余就直接让rear等于数组开头的值了。

        //加入说arr数组长5，front在3号位置（下标为2），rear的下标为4的时候，rear+1是5对他%maxsize，得出的数是0，这就用逻辑的思想来形成了一个圆环，

        // 而非在地址上进行什么操作。

    }

    //获取队列的值

    public int getQueue(){

        if (isEmpty()){

            System.out.println("栈空了！");

//            return -1;这个不行，因为这样的话，只能返回-1

            throw new RuntimeException("队列空。");

        }

      //这里需要分析出front是指向队列的第一个元素

        //1.先把front对应的值保留在一个临时变量

        //2.front后移,考虑取模

        //3.将临时保存的变量返回

        int value=arr[front];

        front=(front+1)%maxSize;//对于front指针也是一样的，要是加的数量超过了maxSize就要靠取模来返回之前曾经走过的位置了

        return value;

    }

    //显示队列的所有数据

    public void showQueue(){

        if (isEmpty()){

            System.out.println("队列是空的。");

        }

        //思路：从front开始遍历，遍历多少个元素。

        for (int i = front; i <front+size() ; i++) {

            //i是从front开始的，不断地加一有可能让他超过maxSize，所以取模就让她回道头部了。

            System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]); //这个要学习一下。

        }

    }

    //当前队列有效数据的个数

    public int size(){

        return  (rear+maxSize-front)%maxSize;//说白了就是rear-front的绝对值的一种表示形式。

        //rear=1

        //front=0

        //maxSize=3

    }

    //显示队列头数据，注意不是取出数据

    public int headQueue(){

        if (isEmpty()){

            System.out.println("队列空的，没有数据");

            throw new RuntimeException("队列是空的");

        }

        return arr[front];//因为队列头front永远指的是队列中的第一个数

    }

}

巴特西

java算法--循环队列

循环队列

最新文章

热门文章