纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

Java动态循环队列 Java动态循环队列是怎样实现的

Duktig丶   2021-06-08 我要评论
想了解Java动态循环队列是怎样实现的的相关内容吗Duktig丶在本文为您仔细讲解Java动态循环队列的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Java动态循环队列,java队列下面大家一起来学习吧

一、队列

1.1 定义

队列 (Queue) 是一种限定性的有序线性表它只允许在表的一端插入元素而在另一端删除元素所以队列具有先进先出 (Fist In Fist Out缩写为FIFO)的特性

  • 在队列中允许插入的一端叫做队尾(rear)
  • 允许删除的一端则称为队头(front)
  • 队列是一个有序列表可以用数组或是链表来实现
  • 遵循先进先出的原则即:先存入队列的数据要先取出

1.2 抽象数据类型

数据元素:可以是任意类型的数据但必须属于同一个数据对象

关系:队列中数据元素之间是线性关系

基本操作:

1.初始化操作使用构造方法设置一个空队列

2.isEmpty():判空操作若队列为空则返回TRUE否则返回FALSE

3.isFull():判满操作若队列为满,则返回TRUE否则返回FALSE

4.getSize():获取队列元素个数

5.add(E e):进队操作在队列Q的队尾插入e如果队满抛出异常

6.poll():出队操作使队列Q的队头元素出队并用e返回其值如果队空抛出异常

7.getHead ():取队头元素操作用e取得队头元素的值如果队列为空则返回null

8.clear():队列置空操作将队列Q置为空队列

9.destroy():队列销毁操作释放队列的空间

1.3 顺序存储

队列的一种顺序存储称为顺序队列与顺序栈类似在队列的顺序存储结构中用一组地址连续的存储单元依次存放从队头到队尾的元素如一维数组Queue[maxSize]

二、数组队列

由于队列中队头和队尾的位置都是动态变化的因此需要附设两个指针 front和 rear

  • front:指示队头元素在数组中的位置;
  • rear:指示真实队尾元素相邻的下一个位置

2.1 思路分析

  • 初始化队列时令front = rear = 0
  • 判断队空的条件:front == rear
  • 判断队满的条件:rear == maxSize
  • 入队时若尾指针rear 小于队列的最大下标 maxSize,则将数据存入rear所指的数组元素中,否则无法存入数据然后将尾指针往后移: rear + 1
  • 出队时若队列不为空取出队头指针front所指的元素然后将尾指针往后移: front + 1

2.2 代码实现

定义接口方法:

/**
 * description:自定义队列接口
 *
 * @author RenShiWei
 * Date: 2021/5/29 20:45
 **/
public interface Queue<E> {

    /**
     * @return 是否队空
     */
    boolean isEmpty();

    /**
     * @return 是否队满
     */
    boolean isFull();

    /**
     * @return 队列的可承载元素个数
     */
    int getCapacity();

    /**
     * @return 队列元素个数
     */
    int getSize();

    /**
     * 队尾入队
     *
     * @param e 入队元素
     */
    void add(E e);

    /**
     * 队首出队
     *
     * @return 出队元素
     */
    E poll();

    /**
     * 获取队首元素
     *
     * @return 队首元素
     */
    E getHead();

}

2.3 数组队列实现

/**
 * description:数组队列
 *
 * @author RenShiWei
 * Date: 2021/5/29 20:41
 **/
public class ArrayQueue<E> implements Queue<E> {

    /** 表示可存储元素的最大容量 */
    private int maxSize;
    /** 队列头 */
    private int front;
    /** 队列尾 */
    private int rear;
    /** 该数据用于存放数据模拟队列 */
    private E[] data;

    /**
     * 初始化队列
     *
     * @param arrMaxSize 初始队列最大容量
     */
    @SuppressWarnings("unchecked")
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        data = (E[]) new Object[maxSize];
        front = 0;
        rear = 0;
    }

    /**
     * @return 是否队空
     */
    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * @return 是否队满
     */
    @Override
    public boolean isFull() {
        return rear == maxSize;
    }

    /**
     * @return 队列元素个数
     */
    @Override
    public int getSize() {
        return rear - front;
    }

    /**
     * 队尾入队
     *
     * @param e 入队元素
     */
    @Override
    public void add(E e) {
        if (isFull()) {
            throw new IllegalArgumentException("队列已满不能入队!");
        }
        data[rear++] = e;
    }

    /**
     * 队首出队
     *
     * @return 出队元素
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空不能出队!");
        }
        //出队位置置null
        E temp = data[front];
        data[front++] = null;
        return temp;
    }

    /**
     * 获取队首元素
     * 如果队空返回null
     *
     * @return 队首元素
     */
    @Override
    public E getHead() {
        return data[front];
    }

    /**
     * @return 队列的可承载元素个数
     */
    @Override
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * @return 队列的有效容量(未使用的空间数量)
     */
    public int getEmptyCount() {
        return maxSize - rear;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");
        for (int i = front; i < rear; i++) {
            res.append(data[i]);
            if (i != rear - 1) {
                res.append(", ");
            }
        }
        res.append("] rear");
        return res.toString();
    }

    /**
     * 队列测试
     */
    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>(5);
        Scanner sc = new Scanner(System.in);
        char c;
        boolean loop = true;
        while (loop) {
            System.out.println("s(toString):输出队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("p(poll):从队列取出数据");
            System.out.println("h(getHead):查看队列头的数据");
            System.out.println("n(isEmpty):是否队空");
            System.out.println("f(isFull):是否队满");
            c = sc.next().charAt(0);
            switch (c) {
                case 's':
                    System.out.println("当前队列:" + queue.toString() + "\t元素个数:" + queue.getSize() + "\t有效容量:" + queue.getEmptyCount());
                    break;
                case 'e':
                    sc.close();
                    loop = false;
                    break;
                case 'a':
                    System.out.println("请输入一个整数");
                    queue.add(sc.nextInt());
                    break;
                case 'p':
                    System.out.printf("出队元素:%d\n", queue.poll());
                    break;
                case 'h':
                    System.out.printf("队首元素:%d\n", queue.getHead());
                    break;
                case 'n':
                    System.out.println("队空:" + queue.isEmpty());
                    break;
                case 'f':
                    System.out.println("队满:" + queue.isFull());
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }

}

2.4 分析

假溢出现象

在非空顺序队列中队头指针始终指向当前的队头元素而队尾指针始终指向真正队尾元素当rear == maxSize - 1 时认为队满但此时不一定是真的队满因为随着部分元素的出队数组前面会出现一些空单元如下图所示由于只能在队尾入队使得上述空单元无法使用把这种现象称为假溢出

image-20210529183259424

问题:目前这个数组使用一次就不能用(出队的空间)没有达到复用的效果可使用算法将其改造成环形队列(取模:%)

三、环形队列

为了解决假溢出现象并使得队列空间得到充分利用,一个较巧妙的办法是将顺序队列的数组看成一个环状的空间即规定最后一个单元的后继为第一个单元我们形象地称之为循环队列

3.1 思路分析

  • 初始化队列时令front = rear = 0front指向队列的第一个元素rear指向队列最后一个元素的后一个位置(希望损失一个位置作为约定用来区分队空和队满)
  • 判断队空的条件:front == rear
  • 判断队满的条件:(rear + 1) % maxSize == front
  • 队列中的元素个数:(rear + maxSize - front) % maxSize
  • 入队时将数据存入rear所指的数组元素中指针变化:rear = ( rear+1) % maxSize
  • 出队时将数据存入front所指的数组元素中指针变化:front = ( front+1 ) % maxSize

下图给出了循环队列的几种情况:

image-20210530163134963 

3.2 代码实现

/**
 * description:循环队列
 *
 * @author RenShiWei
 * Date: 2021/5/30 16:38
 **/
public class LoopQueue<E> implements Queue<E> {

    /** 存储元素 数组的长度(有效长度需要-1) */
    private int maxSize;
    /** 队列头 */
    private int front;
    /** 队列尾 */
    private int rear;
    /** 该数据用于存放数据模拟队列 */
    private E[] data;

    /**
     * 初始化环形队列
     *
     * @param arrMaxSize 初始队列容量
     */
    @SuppressWarnings("unchecked")
    public LoopQueue(int arrMaxSize) {
        //循环队列需要有意识浪费一个空间
        maxSize = arrMaxSize + 1;
        data = (E[]) new Object[maxSize];
    }

    /**
     * @return 是否队空
     */
    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * @return 是否队满
     */
    @Override
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    /**
     * @return 队列的可承载元素个数
     */
    @Override
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * @return 队列元素个数
     */
    @Override
    public int getSize() {
        return (rear + maxSize - front) % maxSize;
    }

    /**
     * 队尾入队
     *
     * @param e 入队元素
     */
    @Override
    public void add(E e) {
        if (isFull()) {
            throw new IllegalArgumentException("队列已满不能入队!");
        }
        data[rear] = e;
        //rear指针后移一位
        rear = (rear + 1) % maxSize;
    }

    /**
     * 队首出队
     *
     * @return 出队元素
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空不能出队!");
        }
        E temp = data[front];
        //出队位置置null
        data[front] = null;
        //front指针后移一位
        front = (front + 1) % maxSize;
        return temp;
    }

    /**
     * 获取队首元素
     * 如果队空返回null
     *
     * @return 队首元素
     */
    @Override
    public E getHead() {
        return data[front];
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", getSize(), getCapacity()));
        res.append("front [");
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != rear) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }

    /**
     * 队列测试
     */
    public static void main(String[] args) {
        LoopQueue<Integer> queue = new LoopQueue<>(5);
        Scanner sc = new Scanner(System.in);
        char c;
        boolean loop = true;
        while (loop) {
            System.out.println("s(toString):输出队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("p(poll):从队列取出数据");
            System.out.println("h(getHead):查看队列头的数据");
            System.out.println("n(isEmpty):是否队空");
            System.out.println("f(isFull):是否队满");
            c = sc.next().charAt(0);
            switch (c) {
                case 's':
                    System.out.println("当前队列:" + queue.toString());
                    break;
                case 'e':
                    sc.close();
                    loop = false;
                    break;
                case 'a':
                    System.out.println("请输入一个整数");
                    queue.add(sc.nextInt());
                    break;
                case 'p':
                    System.out.printf("出队元素:%d\n", queue.poll());
                    break;
                case 'h':
                    System.out.printf("队首元素:%d\n", queue.getHead());
                    break;
                case 'n':
                    System.out.println("队空:" + queue.isEmpty());
                    break;
                case 'f':
                    System.out.println("队满:" + queue.isFull());
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }


}

3.3 分析

相比数组队列来说循环队列解决了数组空间不能再次利用的问题但依然存在一些问题:

  • 当队列真的满的时候就不能再进行入队操作了但是从我们常用的ArrayList来分析在存储空间允许的条件下是可以一直添加元素的
  • 当数组元素频繁进行入队或者出队操作时可能造成空间的浪费循环队列其实只利用了有限的存储空间但是在最初实例化循环队列的时候如果空间声明的很大那么会造成一定程度上的空间浪费
  • 假设声明一个容量为20的循环队列但每次入队2个元素后又出队2个元素那么实际只利用了很有限的空间造成了空间浪费但又不能声明的空间太小并不能保证未来每次只入队或者出队2个元素

因此是否可以实现动态的将循环队列进行扩容或者缩容上述两个问题可以利用下面的动态循环队列来实现

当然上述的数组队列也可以改造成动态的但是出队元素的空间依然会浪费所以没必要进行实现

四、动态循环队列

为了解决循环队列队满不能入队以及频繁入队出队引起的空间浪费而引出动态循环队列的概念即在队满时进行扩容在队列元素个数下降到一定情况下进行缩容

4.1 思路分析

  • 除了入队和出队操作其他操作均与循环队列相同
  • 循环队列存储元素的数组容量变更思路:使用扩容一倍/缩容一倍的新数组接收原来循环队列存储的元素接收后将front指针置为0将rear指针值到最后一个元素的位置(即存储有效元素的数量)
  • 什么时候扩容:队满
  • 什么时候缩容:队列元素只有1/4并且缩容后容量不为0
  • 数组容量为0时缩容会出现异常
  • 为什么不在队列元素只有1/2时缩容?当数组元素为一半的时候一次添加一次删除造成的一直扩容和减小的操作

4.2 代码实现

/**
 * description:动态循环
 *
 * @author RenShiWei
 * Date: 2021/5/30 17:06
 **/
public class DynamicLoopQueue<E> implements Queue<E> {

    /** 存储元素 数组的长度(有效长度需要-1) */
    private int maxSize;
    /** 队列头 */
    private int front;
    /** 队列尾 */
    private int rear;
    /** 该数据用于存放数据模拟队列 */
    private E[] data;

    /**
     * 初始化环形队列
     *
     * @param arrMaxSize 初始队列容量
     */
    @SuppressWarnings("unchecked")
    public DynamicLoopQueue(int arrMaxSize) {
        //循环队列需要有意识浪费一个空间
        maxSize = arrMaxSize + 1;
        data = (E[]) new Object[maxSize];
    }

    /**
     * @return 是否队空
     */
    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * @return 是否队满
     */
    @Override
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    /**
     * @return 队列的可承载元素个数
     */
    @Override
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * @return 队列元素个数
     */
    @Override
    public int getSize() {
        return (rear + maxSize - front) % maxSize;
    }

    /**
     * 队尾入队
     *
     * @param e 入队元素
     */
    @Override
    public void add(E e) {
        if (isFull()) {
            //队满不再进行报错而是进行动态扩容
            resize(getCapacity() * 2);
        }
        data[rear] = e;
        //rear指针后移一位
        rear = (rear + 1) % maxSize;
    }

    /**
     * 队首出队
     *
     * @return 出队元素
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空不能出队!");
        }
        E temp = data[front];
        //出队位置置null
        data[front] = null;
        //front指针后移一位
        front = (front + 1) % maxSize;

        //当数组实际元素减小到空间的一半的时候对其进行缩小
        //if(size == data.length / 2)
        /*
            解决当一半的时候一次添加一次删除造成的一直扩容和减小的操作
            增加必须要扩容所以可以让缩容变得更懒时在进行即1/4时
            data.length / 2 != 0防止数组大小最后变成0造成异常
        */
        if (getSize() == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return temp;
    }

    /**
     * 获取队首元素
     * 如果队空返回null
     *
     * @return 队首元素
     */
    @Override
    public E getHead() {
        return data[front];
    }

    /**
     * 扩容方法
     *
     * @param newCapacity 扩容后的队列大小
     */
    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        //有多个元素循环多少次
        for (int i = 0; i < getSize(); i++) {
            //循环队列会发生偏移重新赋值给新数组
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        maxSize = data.length;
        //重置指针
        front = 0;
        rear = getSize();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", getSize(), getCapacity()));
        res.append("front [");
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != rear) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }

    /**
     * 队列测试
     */
    public static void main(String[] args) {
        DynamicLoopQueue<Integer> queue = new DynamicLoopQueue<>(3);
        Scanner sc = new Scanner(System.in);
        char c;
        boolean loop = true;
        while (loop) {
            System.out.println("s(toString):输出队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("p(poll):从队列取出数据");
            System.out.println("h(getHead):查看队列头的数据");
            System.out.println("n(isEmpty):是否队空");
            System.out.println("f(isFull):是否队满");
            c = sc.next().charAt(0);
            switch (c) {
                case 's':
                    System.out.println("当前队列:" + queue.toString());
                    break;
                case 'e':
                    sc.close();
                    loop = false;
                    break;
                case 'a':
                    System.out.println("请输入一个整数");
                    queue.add(sc.nextInt());
                    break;
                case 'p':
                    System.out.printf("出队元素:%d\n", queue.poll());
                    break;
                case 'h':
                    System.out.printf("队首元素:%d\n", queue.getHead());
                    break;
                case 'n':
                    System.out.println("队空:" + queue.isEmpty());
                    break;
                case 'f':
                    System.out.println("队满:" + queue.isFull());
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }

}

相关文章

猜您喜欢

  • Java异常处理 Java异常处理操作 Throwable、Exception、Error

    想了解Java异常处理操作 Throwable、Exception、Error的相关内容吗陈晨辰~在本文为您仔细讲解Java异常处理的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Java异常处理,Throwable,Exception,Error下面大家一起来学习吧..
  • Android框架之Volley源码 解析Android框架之Volley源码

    想了解解析Android框架之Volley源码的相关内容吗handsome黄在本文为您仔细讲解Android框架之Volley源码的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Android,Volley下面大家一起来学习吧..

网友评论

Copyright 2020 www.fresh-weather.com 【世纪下载站】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式