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

2024-10-01 02:00:38

一、队列

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 时，认为队满。但此时不一定是真的队满，因为随着部分元素的出队，数组前面会出现一些空单元，如下图所示。由于只能在队尾入队，使得上述空单元无法使用。把这种现象称为假溢出。

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

三、环形队列

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

3.1 思路分析

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

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

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

10分钟搞定Java并发队列

前言如果按照用途与特性进行粗略的划分,JUC 包中包含的工具大体可以分为 6 类: 执行者与线程池并发队列同步工具并发集合锁原子变量在并发系列中,主要讲解了执行者与线程池,同步工具,锁 , 在分析源码时,或多或少的提及到了「队列」,队列在 JUC 中也是多种多样存在,所以本文就以「远看」视角,帮助大家快速了解与区分这些看似「杂乱」的队列并发队列 Java 并发队列按照实现方式来进行划分可以分为 2 种: 阻塞队列非阻塞队列如果你已经看完并发系列锁的实现,你已经能够知道他们实
SpringBoot集成JmsTemplate(队列模式和主题模式)及xml和JavaConfig配置详解

1.导入jar包:  <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-activemq</artifactId> </dependency> <dependency> <groupId>org.apache.activemq</g
详解java中的阻塞队列

阻塞队列简介阻塞队列(BlockingQueue)首先是一个支持先进先出的队列,与普通的队列完全相同: 其次是一个支持阻塞操作的队列,即: 当队列满时,会阻塞执行插入操作的线程,直到队列不满. 当队列为空时,会阻塞执行获取操作的线程,直到队列不为空. 阻塞队列用在多线程的场景下,因此阻塞队列使用了锁机制来保证同步,这里使用的可重入锁: 而对于阻塞与唤醒机制则有与锁绑定的Condition实现应用场景:生产者消费者模式 java中的阻塞队列 java中的阻塞队列根据容量可以分为有界队列和无界队
java中用数组实现环形队列的示例代码

本篇文章主要讲述了使用数组实现环形队列的思路以及具体代码一.队列是什么我们先来看下百科的解释: 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,队列是一种操作受限制的线性表.进行插入操作的端称为队尾,进行删除操作的端称为队头. 总结起来两点: 1.一种线性表 2.添加操作只能在表尾,删除操作在表头(先进先出) 二.实现队列的思路 1.初始化一个空队列初始化一个大小固定的数组,并将头指针,尾指针都指向下表为0的位置,但其
详解Java中的延时队列 DelayQueue

当用户超时未支付时,给用户发提醒消息.另一种场景是,超时未付款,订单自动取消.通常,订单创建的时候可以向延迟队列种插入一条消息,到时间自动执行.其实,也可以用临时表,把这些未支付的订单放到一个临时表中,或者Redis,然后定时任务去扫描.这里我们用延时队列来做.RocketMQ有延时队列,RibbitMQ也可以实现,Java自带的也有延时队列,接下来就回顾一下各种队列. Queue 队列是一种集合.除了基本的集合操作以外,队列还提供了额外的插入.提取和检查操作.队列的每个方法都以两种形式存在:一
Java 延迟队列的常用的实现方式

延迟队列的使用场景还比较多,例如: 1.超时未收到支付回调,主动查询支付状态: 2.规定时间内,订单未支付,自动取消: ... 总之,但凡需要在未来的某个确定的时间点执行检查的场景中都可以用延迟队列. 常见的手段主要有:定时任务扫描.RocketMQ延迟队列.Java自动的延迟队列.监听Redis Key过期等等 1. DelayQueue 首先,定义一个延迟任务 package com.cjs.example; import lombok.Data; import java.util.con
JAVA 实现延迟队列的方法

延迟队列的需求各位应该在日常开发的场景中经常碰到.比如: 用户登录之后5分钟给用户做分类推送: 用户多少天未登录给用户做召回推送: 定期检查用户当前退款账单是否被商家处理等等场景. 一般这种场景和定时任务还是有很大的区别,定时任务是你知道任务多久该跑一次或者什么时候只跑一次,这个时间是确定的.延迟队列是当某个事件发生的时候需要延迟多久触发配套事件,引子事件发生的时间不是固定的. 业界目前也有很多实现方案,单机版的方案就不说了,现在也没有哪个公司还是单机版的服务,今天我们一一探讨各种方案的大致实现
Java动态循环队列是如何实现的

一.队列 1.1 定义队列 (Queue) 是一种限定性的有序线性表,它只允许在表的一端插入元素,而在另一端删除元素,所以队列具有先进先出 (Fist In Fist Out,缩写为FIFO)的特性. 在队列中,允许插入的一端叫做队尾(rear): 允许删除的一端则称为队头(front). 队列是一个有序列表,可以用数组或是链表来实现. 遵循先进先出的原则.即:先存入队列的数据,要先取出. 1.2 抽象数据类型数据元素:可以是任意类型的数据,但必须属于同一个数据对象. 关系:队列中数据元素之
java数据结构循环队列的空满判断及长度计算

目录一.假溢出二.循环队列判断是空是满三.循环队列的长度计算四.代码实现在上一章中,使用了数组模拟了队列.但是留下的问题是,把数据取完后,再往里加数据就不行了. 一.假溢出这是因为数组的末尾已经被占用了,入队会继续在数组后面增加,于是产生数组越界.但是实际上,数组里是有空闲位置的,这种也可以叫“假溢出”. 为了解决“假溢出”的问题,于是乎有了循环队列. 既然数组后面满了,头部有空,那继续加进来的元素从头开始放即可. 接着上图,这时候有a6入队,于是rear的下标指向a6的下一个元素位
基于Java数组实现循环队列的两种方法小结

用java实现循环队列的方法: 1.添加一个属性size用来记录眼下的元素个数. 目的是当head=rear的时候.通过size=0还是size=数组长度.来区分队列为空,或者队列已满. 2.数组中仅仅存储数组大小-1个元素,保证rear转一圈之后不会和head相等.也就是队列满的时候.rear+1=head,中间刚好空一个元素. 当rear=head的时候.一定是队列空了. 队列(Queue)两端同意操作的类型不一样: 能够进行删除的一端称为队头,这样的操作也叫出队dequeue: 能够进行插
Java代码实现循环队列的示例代码

循环队列结构队列特点队列为一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表.进行插入操作的端称为队尾,进行删除操作的端称为队头.队列中没有元素时,称为空队列. 队列的数据元素又称为队列元素.在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队.因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO-first i
Java数据结构与算法之循环队列的实现

目录概述循环队列循环队列实现改变队列大小 enqueue 方法 dequeue 方法 main 完整代码概述从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 循环队列循环队列 (Circular Queue) 是一种特殊的队列. 循环队列解决了队列出队时需要将所有数据前移一位 (复杂度为 O(n)) 的问题. 循环队列的底层依然是数组, 不过增加了指向头和尾的指针. 循环队列实现判断队列是否为空: 当头指针 Q.front == 尾指针 Q.rear,
java数组实现循环队列示例介绍

从顶部进去数据,从底部出来数据,用数组实现队列,但是下面这个队列,只能进行一次存数值,取数值,不够完善. import java.util.Scanner; public class ArrayQueueDemo { public static void main(String[]args){ //定义队列大小maxsize ArrayQueue arrayQueue=new ArrayQueue(3); Scanner scanner=new Scanner(System.in); char
Java用数组实现循环队列的示例

复习了下数据结构,用Java的数组实现一下循环队列. 队列的类 //循环队列 class CirQueue{ private int QueueSize; private int front; private int rear; private int[] queueList ; public CirQueue(int QueueSize){ this.QueueSize = QueueSize; queueList = new int[QueueSize]; front = 0; rear =
java数据结构与算法之双向循环队列的数组实现方法

本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p
Java数据结构之循环队列简单定义与用法示例

本文实例讲述了Java数据结构之循环队列简单定义与用法.分享给大家供大家参考,具体如下: 一.概述: 1.原理: 与普通队列的区别在于循环队列添加数据时,如果其有效数据end == maxSize - 1(最大空间)的话,end指针又移动到-1的位置删除数据时,如果head== maxSize时 head指针移动到0的位置 2.示例图: 二.实现代码: package com.java.queue; /** * @描述对列 * @项目名称 Java_DataStruct * @包名 com.
java队列实现方法(顺序队列,链式队列,循环队列)

双向顺序队列ArrayDeque和双向链式队列LinkedList,JDK已经包含,在此略.ArrayDeque包括顺序栈和顺序队列,LinkedList包含链式栈和链式队列.ArrayDeque和LinkedList都是线程不安全的.PriorityQueue优先队列也在JDK. 1.顺序队列的实现 package lang; import java.io.Serializable; import java.util.Arrays; /** * @ClassName: ArrayQueue *