原创

队列

温馨提示:
本文最后更新于 2022年06月18日,已超过 8 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

队列介绍

队列是一个有序列表,可以用数组或是链表来实现。
遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出

数组模拟队列的思路

队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。

因为队列的输出、输入是分别从前后端来处理,因此需要两个变量 front及 rear分别记录队列前后端的下标,front 会随着数据输出而改变,而 rear则是随着数据输入而改变,如图所示:

image-20220321144210250

当我们将数据存入队列时称为”addQueue”,addQueue 的处理需要有两个步骤:思路分析
将尾指针往后移:rear+1 , 当front == rear 【空】
若尾指针 rear 小于队列的最大下标 maxSize-1,则将数据存入 rear所指的数组元素中,否则无法存入数据。 rear == maxSize - 1[队列满]

代码实现

package queue;

import java.awt.RenderingHints.Key;
import java.net.Socket;
import java.util.Scanner;

import javax.management.RuntimeErrorException;
import javax.sound.midi.VoiceStatus;

public class ArrayQueue {
    public static void main(String[] args) {
        //创建一个队列
        Quere quere = new Quere(3);
        char key = ' ';
        Scanner scanner = new Scanner(System.in);
        boolean lop = true;
        while(lop) {
            System.out.println("s,显示队列");
            System.out.println("e,退出程序");
            System.out.println("a,添加数据");
            System.out.println("g,取出数据");
            System.out.println("h,查看头部数据");
            key = scanner.next().charAt(0);
            switch (key) {
            case 's': {
                try {
                    quere.showQuere();
                } catch (Exception e) {
                    // TODO: handle exception
                    System.out.println(e.getMessage());
                }
                break;
            }
            case 'e' : {
                scanner.close();
                lop = false;
                System.out.println("程序退出");
                break;
            }
            case 'a' : {
                System.out.println("请输入一个数据");
                int value = scanner.nextInt();
                quere.addQuere(value);
                break;
            }
            case 'g' : {
                try {
                    System.out.println("取出多少个数据");
                    int number = scanner.nextInt();
                    quere.takeOutData(number);
                } catch (Exception e) {
                    // TODO: handle exception
                    System.out.println(e.getMessage());
                }
                break;
            }
            case 'h' : {
                try {
                    quere.seeHead();
                } catch (Exception e) {
                    // TODO: handle exception
                    System.out.println(e.getMessage());
                }
                break;
            }
            default:
                break;
            }
        }
    }
}
//编写一个类实现队列
class Quere{
    //队列中的各项参数
    public int maxSize;
    public int front;
    public int rear;
    int[] arrayQuere =  new int[10];
    //编写构造方法传入初始数据
    public Quere(int maxSize) {
        // TODO Auto-generated constructor stub
        this.maxSize = maxSize;
        //初始的时候队列头指针和尾指针都是指向队列尾部的后一个位置的
        //这样在下面写循环的时候就可以将数值加一之后在进行下面的操作
        front = -1;
        rear = -1;
    }
    //判断队列是否是满的
    public boolean isFull(){
        return rear == maxSize-1;
    }
    //判断队列是否是空的
    public boolean isEmpty() {
        return rear == front;
    }
    //添加数据到队列里面
    public void addQuere(int data) {
        //判断队列是否是满的,如果队列满了将无法添加数据
        if(isFull()) {
            System.out.println("队列是满的,不能继续加入数据");
            return;
        }
        rear++;
        arrayQuere[rear] = data;
    }
    //从队列里面取出数据
    public void takeOutData(int number) {
        //判断是否为空
        if(isEmpty()) {
            throw new RuntimeException("空队列,无法取出数据");
        }
        while(number !=0 && front<rear){
            front++;
            System.out.printf("取出的数据为:arrayQuere[%d]:%d\n",front,arrayQuere[front]);
            number--;
        }
    }
    //查看头部数据
    public void seeHead() {
        if(isEmpty()) {
            throw new RuntimeException("空队列,无头部数据");
        }
        int index = this.front;
        System.out.println("头部数据为:"+arrayQuere[++index]);
    }
    //遍历队列
    public void showQuere() {
        if(isEmpty()) {
            throw new RuntimeException("空队列,无法遍历数据");
        }
        int index = this.front;
        while(index<rear){
            index++;
            System.out.printf("arrayQuere[%d]:%d\n",index,arrayQuere[index]);
        }
    }
}
  • 上面的代码就写成了一个队列,但是这样的队列有一个缺点,只能使用一次,当队列满之后就无法再往里面添加数据了,局限性很大,我们的目标是写一个只要有空位就能继续往里面添加数据的队列

循环队列的实现思路

写成环形结构的话要求:如果rear指针到达队列的最大值,此时front已经被取出,就是此时front的值已经大于0的时候rear就会被重置为0,然后继续往里面添加数据。此时需要考虑的问题:

  1. 什么时候队列为满

  2. 什么时候队列为空

  3. 队列中此时存储了几个数据

  4. 如果队列的中间为空,前后有值将怎么取出、遍历队列中的

  5. 队列的头部值是什么

问题一:我们不妨将front和rear的初始值都规定为0,这样他们都指向了一个值,那么在接下来的代码当中就要先赋值再++,通过观察可以发现,如果front的值为0,rear的值为5,那么加1,%max...就恰好等于front的值,通过这样的简单情况,就能推导出一个公式,当队列满的时候(rear+1)%max = front,这里的满不是真的满,而是少了一个位置,这也是环形队列的关键所在,当然这个空位会因rear的不同而出现在队列的任何位置,我们可以通过其他特殊的数值来判断这个公式对不对,这里我就不写了

问题二:队列为空的时候就是rear = front的时候,这个没什么好说的

问题三:这个问题决定了以后我们能遍历的数据到底有几个,这个推导复杂,说实话我也没有退出来,但是公式是这样的(rear + max - front)%max,不过这只是其中的一种遍历方式,我用了一种更好的方法,不用这个公式也能遍历队列里面的数据,观察发现,只要front的值!=rear的值我们就可以一直遍历,这样是没有错误的,也不会发生死循环和数组越界问题

具体的代码如下:

    //遍历队列
    public void showQuere() {
        if(isEmpty()) {
            throw new RuntimeException("空队列,无法遍历数据");
        }
        int index = this.front;
        while(index !=rear){
            System.out.printf("arrayQuere[%d]:%d\n",index,arrayQuere[index]);
            index = (index+1)%this.maxSize;
        }
    }

问题四:这其实就是三解决的问题,不过有一点,这样遍历的话会将没有赋值的也遍历出来,默认值为0

问题五:队列头就是front

其实还有一个问题:在每一次取出数据和添加数据之后rear=?,front=?这一点通过计算可以得到他们都等于(rear/front+1)%max

这样一来我们就可以使用上面的推论来写出一个循环队列

代码实现

package queue;

import java.awt.Font;
import java.awt.RenderingHints.Key;
import java.net.Socket;
import java.util.Scanner;

import javax.management.RuntimeErrorException;
import javax.sound.midi.VoiceStatus;

public class CircleArrayQuere {
    public static void main(String[] args) {
        //创建一个队列
        Quere02 quere = new Quere02(4);
        char key = ' ';
        Scanner scanner = new Scanner(System.in);
        boolean lop = true;
        //写一个简单的菜单
        while(lop) {
            System.out.println("s,显示队列");
            System.out.println("e,退出程序");
            System.out.println("a,添加数据");
            System.out.println("g,取出数据");
            System.out.println("h,查看头部数据");
            key = scanner.next().charAt(0);
            switch (key) {
            case 's': {
                try {
                    quere.showQuere();
                } catch (Exception e) {
                    // TODO: handle exception
                    System.out.println(e.getMessage());
                }
                break;
            }
            case 'e' : {
                scanner.close();
                lop = false;
                System.out.println("程序退出");
                break;
            }
            case 'a' : {
                System.out.println("请输入一个数据");
                int value = scanner.nextInt();
                quere.addQuere(value);
                break;
            }
            case 'g' : {
                try {
                    System.out.println("取出多少个数据");
                    int number = scanner.nextInt();
                    quere.takeOutData(number);
                } catch (Exception e) {
                    // TODO: handle exception
                    System.out.println(e.getMessage());
                }
                break;
            }
            case 'h' : {
                try {
                    quere.seeHead();
                } catch (Exception e) {
                    // TODO: handle exception
                    System.out.println(e.getMessage());
                }
                break;
            }
            default:
                break;
            }
        }
    }
}
//编写一个类实现队列
class Quere02{
    //队列中的各项参数
    public int maxSize;
    public int front;
    public int rear;
    int[] arrayQuere =null;
    //编写构造方法传入初始数据
    public Quere02(int maxSize) {
        // TODO Auto-generated constructor stub
        this.maxSize = maxSize;
        arrayQuere = new int[maxSize];
        //初始的时候队列头指针和尾指针都是指向队列的第一个数值
        //这样在下面写循环的时候就要先赋值再将数值加一
        front = 0;
        rear = 0;
    }
    //判断队列是否是满的
    public boolean isFull(){
        return (rear+1)%this.maxSize == this.front;//这里的这些操作都和第一种有一定的区别
    }
    //判断队列是否是空的
    public boolean isEmpty() {
        return rear == front;
    }
    //添加数据到队列里面
    public void addQuere(int data) {
        //判断队列是否是满的,如果队列满了将无法添加数据
        if(isFull()) {
            System.out.println("队列是满的,不能继续加入数据");
            return;
        }
        arrayQuere[rear] = data;
        rear = (rear+1)%this.maxSize;
    }
    //从队列里面取出数据
    public void takeOutData(int number) {
        //判断是否为空
        if(isEmpty()) {
            throw new RuntimeException("空队列,无法取出数据");
        }
        while(number !=0 && front !=rear){
            System.out.printf("取出的数据为:arrayQuere[%d]:%d\n",front,arrayQuere[front]);
            front = (front+1)%this.maxSize;
            number--;
        }
    }
    //查看头部数据
    public void seeHead() {
        if(isEmpty()) {
            throw new RuntimeException("空队列,无头部数据");
        }
        int index = this.front;
        System.out.println("头部数据为:"+arrayQuere[index]);
    }
    //遍历队列
    public void showQuere() {
        if(isEmpty()) {
            throw new RuntimeException("空队列,无法遍历数据");
        }
        int index = this.front;
        while(index !=rear){
            System.out.printf("arrayQuere[%d]:%d\n",index,arrayQuere[index]);
            index = (index+1)%this.maxSize;
        }
    }
}

运行可以看到

image-20220321172704683

仅仅只能添加3个数据,这也就是我们所说的空出来了一个位置,这也是循环队列的关键

然后再来看看其他的

image-20220321173101417

image-20220321172933947

我取出了一个数据10,然后我再添加一个数据,可以发现添加成功了,添加到了3这个位置,那么我们可以推断出,原来0这个位置变为了空位置,这也符合我们的预想

我的PPT推论过程

有点乱,只是记录下,你们还是看上面的

image-20220321172529640

正文到此结束