广告
返回顶部
首页 > 资讯 > 后端开发 > Python >Java动态循环队列是如何实现的
  • 872
分享到

Java动态循环队列是如何实现的

Java动态循环队列java队列 2022-11-12 05:11:27 872人浏览 安东尼

Python 官方文档:入门教程 => 点击学习

摘要

目录一、队列1.1 定义1.2 抽象数据类型1.3 顺序存储二、数组队列2.1 思路分析2.2 代码实现2.3 数组队列实现2.4 分析三、环形队列3.1 思路分析3.2 代码实现3

一、队列

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 代码实现

定义接口方法:



public interface Queue<E> {

    
    boolean isEmpty();

    
    boolean isFull();

    
    int getCapacity();

    
    int getSize();

    
    void add(E e);

    
    E poll();

    
    E getHead();

}

2.3 数组队列实现



public class ArrayQueue<E> implements Queue<E> {

    
    private int maxSize;
    
    private int front;
    
    private int rear;
    
    private E[] data;

    
    @SuppressWarnings("unchecked")
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        data = (E[]) new Object[maxSize];
        front = 0;
        rear = 0;
    }

    
    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    
    @Override
    public boolean isFull() {
        return rear == maxSize;
    }

    
    @Override
    public int getSize() {
        return rear - front;
    }

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

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

    
    @Override
    public E getHead() {
        return data[front];
    }

    
    @Override
    public int getCapacity() {
        return data.length - 1;
    }

    
    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 代码实现



public class LoopQueue<E> implements Queue<E> {

    
    private int maxSize;
    
    private int front;
    
    private int rear;
    
    private E[] data;

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

    
    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    
    @Override
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    
    @Override
    public int getCapacity() {
        return data.length - 1;
    }

    
    @Override
    public int getSize() {
        return (rear + maxSize - front) % maxSize;
    }

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

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

    
    @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 代码实现



public class DynamicLoopQueue<E> implements Queue<E> {

    
    private int maxSize;
    
    private int front;
    
    private int rear;
    
    private E[] data;

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

    
    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    
    @Override
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    
    @Override
    public int getCapacity() {
        return data.length - 1;
    }

    
    @Override
    public int getSize() {
        return (rear + maxSize - front) % maxSize;
    }

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

    
    @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)
        
        if (getSize() == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return temp;
    }

    
    @Override
    public E getHead() {
        return data[front];
    }

    
    @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动态循环队列内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

--结束END--

本文标题: Java动态循环队列是如何实现的

本文链接: https://www.lsjlt.com/news/127792.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • Java动态循环队列是如何实现的
    目录一、队列1.1 定义1.2 抽象数据类型1.3 顺序存储二、数组队列2.1 思路分析2.2 代码实现2.3 数组队列实现2.4 分析三、环形队列3.1 思路分析3.2 代码实现3...
    99+
    2022-11-12
    Java动态循环队列 java队列
  • Java动态循环队列怎么实现
    这篇文章将为大家详细讲解有关Java动态循环队列怎么实现,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。一、队列1.1 定义队列 (Queue) 是一种限定性的有序线性表,它只允许在表的一端插入元素,而在另...
    99+
    2023-06-15
  • Java如何实现循环队列
    小编给大家分享一下Java如何实现循环队列,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!循环队列循环队列 (Circular Queue) 是一种特殊的队列. 循环队列解决了队列出队时需要将所有数据前移一位 (复杂度为 O...
    99+
    2023-06-22
  • java实现循环队列
    循环队列的优点普通队列出队操作开销大:在出队操作时,索引为0后面的所有元素,都需要往前移动一位,元素越多,消耗的时间也越多,时间复杂度为O(N)。循环队列的逻辑:当元素较少时(tail位置在front后面),循环队列与普通队列出队操作一样,...
    99+
    2017-09-10
    java入门 java 循环队列
  • Java 循环队列/环形队列的实现流程
    之前,我们使用链表实现了基础队列,链接放在这里可以去康康哟 Java栈和基础队列的实现详解 之所以没有选择数组来实现,是因为每有一个元素出队,数组中所有剩下的元素都需要向前移动一次,...
    99+
    2022-11-13
    Java 循环队列 Java 环形队列
  • JAVA怎么实现循环队列
    在Java中,可以使用数组和指针来实现循环队列。以下是一个简单的循环队列的实现示例:```javapublic class Circ...
    99+
    2023-09-23
    JAVA
  • java队列实现方法(顺序队列,链式队列,循环队列)
    双向顺序队列ArrayDeque和双向链式队列LinkedList,JDK已经包含,在此略。ArrayDeque包括顺序栈和顺序队列,LinkedList包含链式栈和链式队列。ArrayDeque和LinkedList都是线程不安全的。Pr...
    99+
    2023-05-30
    java 队列 顺序
  • C#实现泛型动态循环数组队列的方法
    任务 循环数组 实现目标:(1)创建一个新的数组数据结构;      (2)该数据结构为泛型;      (3)可以按照元素多少进行扩容缩容;      (4)进行添加删除操作的时间...
    99+
    2022-11-13
    C#泛型动态循环数组队列 C#泛型数组队列
  • C#怎么实现泛型动态循环数组队列
    这篇文章主要介绍“C#怎么实现泛型动态循环数组队列”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“C#怎么实现泛型动态循环数组队列”文章能帮助大家解决问题。任务循环数组实现目标:(1)创建一个新的数组...
    99+
    2023-06-29
  • Java代码实现循环队列的示例代码
    循环队列结构 队列特点 队列为一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受...
    99+
    2022-11-12
    Java实现循环队列 Java循环队列
  • java数组实现循环队列示例介绍
     从顶部进去数据,从底部出来数据,用数组实现队列,但是下面这个队列,只能进行一次存数值,取数值,不够完善。 import java.util.Scanner; pu...
    99+
    2022-11-12
    Java数组实现循环队列 java循环队列
  • C语言如何实现顺序循环队列
    这篇文章将为大家详细讲解有关C语言如何实现顺序循环队列,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。一、队列和循环队列基本概念队列:和栈相反,队列是一种先进先出(FIFO)的线性表。只允许在一端插入,在另...
    99+
    2023-06-29
  • Java中的循环队列怎么利用数组实现
    这篇文章将为大家详细讲解有关Java中的循环队列怎么利用数组实现,文章内容质量较高,因此小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。用Java的数组实现一下循环队列。队列的类//循环队列class CirQueu...
    99+
    2023-05-31
    循环队列 java
  • C语言详解链式队列与循环队列的实现
    目录队列的实现链式队列链式队列的定义链式队列的实现循环队列循环队列的定义循环队列的实现队列的实现 队列是一种先进先出(First in First Out)的线性表,简称FIFO。与...
    99+
    2022-11-13
    C语言 链式队列 C语言 循环队列
  • angularjs循环对象属性如何实现动态列
    小编给大家分享一下angularjs循环对象属性如何实现动态列,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!angularjs循环对象属性实现动态列优点:保存对象...
    99+
    2023-06-25
  • Java数据结构与算法之循环队列的实现
    目录概述循环队列循环队列实现改变队列大小enqueue 方法dequeue 方法main完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章...
    99+
    2022-11-12
    Java循环队列 Java数据结构 循环队列 Java数据结构 队列
  • Java单向队列及环形队列的实现原理是什么
    这篇文章主要介绍“Java单向队列及环形队列的实现原理是什么”,在日常操作中,相信很多人在Java单向队列及环形队列的实现原理是什么问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Java单向队列及环形队列的实...
    99+
    2023-06-25
  • Java 单向队列及环形队列的实现原理
    目录队列的特点图解实现过程:优化解决——环形队列实现思路环形队列各步骤及各方法实现讲解最后:队列的特点 1.可以使用数组和链表两种方式来实现。 2.遵循先入先出(FIFO)的规则,即...
    99+
    2022-11-12
    Java 单向队列 Java 环形队列
  • java数据结构中顺序队列和循环队列的区别是什么
    这篇文章主要介绍“java数据结构中顺序队列和循环队列的区别是什么”,在日常操作中,相信很多人在java数据结构中顺序队列和循环队列的区别是什么问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”java数据结构中...
    99+
    2023-06-20
  • js如何实现列表循环滚动
    本篇内容主要讲解“js如何实现列表循环滚动”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“js如何实现列表循环滚动”吧!先介绍几个属性clientHeight 元素的高度clientTop 元素顶...
    99+
    2023-07-02
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作