1. Python技术站首页
  2. 其他
  3. Java

java数组实现队列及环形队列实现过程解析

• Java
yizhihongxing

Java数组实现队列

简介

队列(Queue)是一种先进先出(FIFO)的数据结构，它支持在队列尾部插入数据，在队列头部删除数据。在实际的开发中，我们经常会使用队列来解决一些问题，比如多线程的任务队列，消息队列等等。在Java中，我们可以使用数组来实现队列。

实现过程

我们使用一个数组来保存队列中的元素，同时记录队列的头部和尾部元素的位置。具体实现方法如下：
1. 创建一个数组 queueArray 和两个变量 head 和 tail，其中 queueArray 用于保存队列的元素，head 和 tail 用于记录队列的头部和尾部元素位置，初始化 head 和 tail 为 0。
2. 在队列尾部插入数据时，将元素插入 queueArray 的 tail 位置，并将 tail 的值加 1。
3. 在队列头部删除数据时，将 head 的值加 1，并直接返回 queueArray[head]（即队列的头部元素）。

示例1：

下面是一个简单的实现代码。我们在 main 函数中创建了一个队列，依次向队列中添加 1、2、3 三个元素，然后删除队列的头部元素，输出删除的元素，再添加 4、5、6 三个元素，并依次删除元素。最终队列为空时结束操作。

public class ArrayQueue {
    private int[] queueArray;
    private int head;
    private int tail;
    private int capacity;

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        queueArray = new int[capacity];
    }

    public boolean enqueue(int item) {
        if (tail == capacity) {
            return false;
        }

        queueArray[tail] = item;
        tail++;
        return true;
    }

    public int dequeue() {
        if (head == tail) {
            return -1;
        }

        int item = queueArray[head];
        head++;
        return item;
    }

    public static void main(String[] args) {
        ArrayQueue queue = new ArrayQueue(6);
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        System.out.println(queue.dequeue());

        queue.enqueue(4);
        queue.enqueue(5);
        queue.enqueue(6);

        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
    }
}

输出结果：

1
2
3
4
5
6

示例2：

我们可以使用Java的泛型，让代码具有更好的灵活性。现在我们重写 ArrayQueue 类，使用泛型来实现队列。

public class ArrayQueue<T> {
    private T[] queueArray;
    private int head;
    private int tail;
    private int capacity;

    @SuppressWarnings("unchecked")
    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        queueArray = (T[]) new Object[capacity];
    }

    public boolean enqueue(T item) {
        if (tail == capacity) {
            return false;
        }

        queueArray[tail] = item;
        tail++;
        return true;
    }

    public T dequeue() {
        if (head == tail) {
            return null;
        }

        T item = queueArray[head];
        head++;
        return item;
    }

    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>(6);
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        System.out.println(queue.dequeue());

        queue.enqueue(4);
        queue.enqueue(5);
        queue.enqueue(6);

        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
    }
}

输出结果：

1
2
3
4
5
6

Java环形队列实现

简介

队列是一种常见的数据结构，使用队列可以控制数据的先进先出(FIFO)。在实际的应用中，队列应用广泛。当然，对于环形队列，它与普通队列不同。普通队列是线性的，所以必须有两个“指针”表示当前的队头、队尾，但环形队列是圆形的，只需要知道一个“指针”就可以了。环形队列在解决一些问题时比普通队列更加高效。本文将介绍如何使用数组实现Java环形队列。

实现过程

在数组中使用环形队列时，我们需要维护一个 head 数组表示当前队列的起点，tail 数组表示当前队列的终点。当 tail 超过了数组最大的下标时，tail 应该重新指向数组开始的位置。与普通队列相比，我们需要特别地处理一些特殊情况。

判断队列是否为空：

当 head == tail 时，队列为空。

判断队列是否已满：

当 (tail + 1) % capacity == head 时，队列已满。

在队列尾部插入数据：

  • 如果队列未满，直接将元素插入 tail 位置。
  • 如果队列已满，返回 false。

在队列头部删除数据：

  • 如果队列为空，返回 null。
  • 如果队列不为空，则先取出 head 位置的元素，再将 head 的值加 1。

示例1：

下面是一个简单的环形队列实现代码，我们在 main 函数中创建了一个容量为 6 的队列，并依次插入 1、2、3、4、5、6 个元素。最后，我们输出队列的所有元素。

public class CircularQueue {
    private int[] queueArray;
    private int head;
    private int tail;
    private int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        queueArray = new int[capacity];
        head = 0;
        tail = 0;
    }

    public boolean enqueue(int item) {
        if ((tail + 1) % capacity == head) {
            return false;
        }

        queueArray[tail] = item;
        tail = (tail + 1) % capacity;
        return true;
    }

    public int dequeue() {
        if (head == tail) {
            return -1;
        }

        int item = queueArray[head];
        head = (head + 1) % capacity;
        return item;
    }

    public static void main(String[] args) {
        CircularQueue queue = new CircularQueue(6);
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.enqueue(4);
        queue.enqueue(5);
        queue.enqueue(6);

        int size = (queue.tail - queue.head + queue.capacity) % queue.capacity;
        for (int i = 0; i < size; i++) {
            System.out.println(queue.dequeue());
        }
    }
}

输出结果：

1
2
3
4
5
6

示例2：

我们同样可以是使用Java的泛型，让代码具有更好的灵活性。现在我们重写 CircularQueue 类，使用泛型来实现队列。

public class CircularQueue<T> {
    private T[] queueArray;
    private int head;
    private int tail;
    private int capacity;

    @SuppressWarnings("unchecked")
    public CircularQueue(int capacity) {
        this.capacity = capacity;
        queueArray = (T[]) new Object[capacity];
        head = 0;
        tail = 0;
    }

    public boolean enqueue(T item) {
        if ((tail + 1) % capacity == head) {
            return false;
        }

        queueArray[tail] = item;
        tail = (tail + 1) % capacity;
        return true;
    }

    public T dequeue() {
        if (head == tail) {
            return null;
        }

        T item = queueArray[head];
        head = (head + 1) % capacity;
        return item;
    }

    public static void main(String[] args) {
        CircularQueue<Integer> queue = new CircularQueue<>(6);
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.enqueue(4);
        queue.enqueue(5);
        queue.enqueue(6);

        int size = (queue.tail - queue.head + queue.capacity) % queue.capacity;
        for (int i = 0; i < size; i++) {
            System.out.println(queue.dequeue());
        }
    }
}

输出结果：

1
2
3
4
5
6

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：java数组实现队列及环形队列实现过程解析 - Python技术站

赞 (0)
0 0 打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年5月26日
下一篇 2023年5月26日

相关文章

  • SpringMVC参数传递之基本数据类型和复杂对象说明

    SpringMVC参数传递之基本数据类型和复杂对象说明 在SpringMVC中，参数传递是非常重要的，它可以帮助我们将数据从页面传递到控制器中进行处理。本文将详细介绍SpringMVC中参数传递的两种方式：基本数据类型和复杂对象，并提供两个示例说明。 基本数据类型参数传递 在SpringMVC中，我们可以使用基本数据类型来传递参数。以下是一个简单的示例，它使…

    Java 2023年5月17日
    00

  • Java Apache POI报错“IndexOutOfBoundsException”的原因与解决办法

    “IndexOutOfBoundsException”是Java的Apache POI类库中的一个异常，通常由以下原因之一引起： 索引错误：如果索引不正确，则可能会出现此异常。例如，可能会尝试访问不存在的行或列。 以下是两个实例： 例1 如果索引不正确，则可以尝试使用正确的索引以解决此问题。例如，在Java中，可以使用以下代码： FileInputStrea…

    Java 2023年5月5日
    00

  • java垃圾回收机制（面试）

    1.1堆空间结构 　　Java 的自动内存管理主要是针对对象内存的回收和对象内存的分配。同时，Java 自动内存管理最核心的功能是 堆 内存中对象的分配与回收。Java 堆是垃圾收集器管理的主要区域，因此也被称作 GC 堆。Eden 区、两个 Survivor 区 S0 和 S1 都属于新生代，中间一层属于老年代，最下面一层属于永久代。  　　 　　 1.2…

    Java 2023年4月27日
    00

  • JAVA日期处理类详解

    JAVA日期处理类详解 在JAVA编程中，日期处理是非常重要的一部分内容。JAVA内置了许多日期处理类，下面就来详细地介绍一下。 java.util.Date类 java.util.Date类是JAVA中最早的关于日期时间处理的类。在JAVA8之前，它被广泛使用。但是由于它的一些不足之处，比如日期时间格式化问题，API设计不具有可读性等等，所以在JAVA8之…

    Java 2023年5月20日
    00

  • SpringBoot使用Caffeine实现缓存的示例代码

    下面给出 SpringBoot 使用 Caffeine 实现缓存的示例代码的完整攻略。 1. 添加 Caffeine 依赖 在 pom.xml 文件中添加 Caffeine 依赖： <!–Caffeine–> <dependency> <groupId>com.github.ben-manes.caffeine<…

    Java 2023年5月19日
    00

  • Java实现纪元秒和本地日期时间互换的方法【经典实例】

    Java实现纪元秒和本地日期时间互换的方法【经典实例】 什么是纪元秒？ 纪元秒是指从“1970年1月1日 00:00:00 UTC”开始计算至某一时刻之间的秒数。 纪元秒与本地日期时间的相互转换 Java提供了从纪元秒到本地日期时间和从本地日期时间到纪元秒的转换方法。这些方法都属于Java API中的java.time包。 从纪元秒到本地日期时间 Java中…

    Java 2023年5月20日
    00

  • Spring Boot实现微信小程序登录

    下面是Spring Boot实现微信小程序登录的完整攻略： 一、前期准备 确认已经拥有一个注册了小程序账号的微信号，并且已经拥有小程序的AppID和AppSecret 通过小程序开发文档，了解小程序登录的过程和参数 二、Spring Boot集成微信登录 添加Spring Boot对于微信登录的依赖： <dependency> <group…

    Java 2023年5月23日
    00

  • 使用SpringDataJpa创建中间表

    创建中间表是数据库设计中比较常见的操作，通常用于多对多关系的表之间，下面将介绍使用SpringDataJpa来创建中间表的完整攻略及示例。 1. 创建实体类和对应的Repository类 首先，需要创建两个实体类来代表多对多关系中的两个表，并在这两个实体类的@Repository注解中使用@RestController注解（或其他泛型注解）来继承Spring…

    Java 2023年5月20日
    00
合作推广
合作推广
分享本页
返回顶部