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

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)
上一篇 2023年5月26日
下一篇 2023年5月26日

相关文章

  • Java实现向Word文档添加文档属性

    下面我将详细讲解如何使用Java向Word文档添加文档属性。 1. Word文档属性 在Word文档中,文档属性是描述文档特性的元数据,例如作者、标题、主题等等。它们可以加强搜索效果、提取有用信息和跟踪文档版本。文档属性通常包含在文档内部,并不会在文档中显示出来,但可以通过Word菜单中的文件属性信息查看。 2. Java实现方法 Java可以通过POI库(…

    Java 2023年5月19日
    00
  • 史上最全Java8日期时间工具类(分享)

    首先,该文章介绍了作者基于Java 8中的日期时间API开发的一个日期时间工具类,该工具类可以方便地进行常用的日期时间操作。以下是工具类的一些主要特点: 支持多种日期时间格式字符串的解析和格式化。 提供丰富的日期时间计算和转换方法。 更符合人类习惯的日期时间输出格式。 接下来,我们详细讲解一些该工具类的常用方法: 将日期时间转换成指定格式的字符串 使用该工具…

    Java 2023年5月20日
    00
  • 小程序websocket心跳库(websocket-heartbeat-miniprogram)

    小程序websocket心跳库(websocket-heartbeat-miniprogram)是一个专为微信小程序开发的websocket心跳保活库。本库基于wx.socket组件进行二次封装,使得小程序能够稳定地通过websocket进行双向实时通信。本库提供了websocket的连接建立、websocket的发送数据、websocket的心跳保活、we…

    Java 2023年5月23日
    00
  • Spring Boot的几种统一处理方式梳理小结

    对于Spring Boot的几种统一处理方式,我们可以从以下几个方面来进行梳理: 1. 统一异常处理 在Spring Boot中,我们通常会使用@ControllerAdvice注解来统一处理异常,具体的步骤如下: 首先,我们需要新建一个处理器类,并在类上使用@ControllerAdvice注解,表示该类是一个统一的异常处理器。 然后,我们可以在该类中定义…

    Java 2023年5月31日
    00
  • Mybatis-plus与Mybatis依赖冲突问题解决方法

    Mybatis-plus是基于Mybatis的增强框架,它在Mybatis的基础上提供了一些实用、便捷的功能。但是,在开发过程中,我们有可能会遇到Mybatis-plus和Mybatis依赖冲突的问题。本文将针对这一问题给出完整的解决方法,包括具体的示例演示。 完整攻略 1. 了解冲突原因 首先,我们需要了解冲突的原因。Mybatis-plus和Mybati…

    Java 2023年5月20日
    00
  • Jdk中没有jre文件夹怎么办?如何解决?

    当我们下载JDK(Java Development Kit)的安装包时,它包含了JRE(Java Runtime Environment)文件夹,因为JRE的存在意味着可以同时运行Java程序和Java应用程序。然而,有些时候我们会下载不包含JRE文件夹的JDK安装包,这个时候就需要手动添加JRE文件夹才能正常运行Java程序。下面是在Windows系统下的…

    Java 2023年5月26日
    00
  • Java利用TreeUtils工具类实现列表转树

    下面是Java利用TreeUtils工具类实现列表转树的完整攻略。 1.准备工作 在进行列表转树操作前,需要先准备好列表数据。假设列表中每个元素都具有一个唯一标识符id和一个父元素标识符parentId,我们可以封装一个类来表示列表元素: public class TreeNode { private String id; private String pa…

    Java 2023年5月20日
    00
  • 详解在springboot中使用Mybatis Generator的两种方式

    下面我将详细讲解“详解在springboot中使用Mybatis Generator的两种方式”的完整攻略。 一、前置条件 在使用Mybatis Generator之前,我们需要先满足以下几个前置条件: 安装Maven和JDK,在此不再赘述; 在项目中引入依赖mybatis-generator-core和mysql-connector-java,可以在pom…

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