经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » Java相关 » Java » 查看文章
教你如何使用Java手写一个基于数组实现的队列
来源：cnblogs　　作者：rainple　　时间：2018/11/20 16:35:10　　对本文有异议

　　一、概述

　　队列，又称为伫列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

　　在Java中队列又可以分为两个大类，一种是阻塞队列和非阻塞队列。

　　1、没有实现阻塞接口：

　　1）实现java.util.Queue的LinkList,

　　2）实现java.util.AbstractQueue接口内置的不阻塞队列： PriorityQueue 和 ConcurrentLinkedQueue

　　2、实现阻塞接口的

　　java.util.concurrent 中加入了 BlockingQueue 接口和五个阻塞队列类。它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用。
　　五个队列所提供的各有不同：
　　* ArrayBlockingQueue ：一个由数组支持的有界队列。
　　* LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。
　　* PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。
　　* DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。
　　* SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。
　　队列是Java中常用的数据结构，比如在线程池中就是用到了队列，比如消息队列等。

　　由队列先入先出的特性，我们知道队列数据的存储结构可以两种，一种是基于数组实现的，另一种则是基于单链实现。前者在创建的时候就已经确定了数组的长度，所以队列的长度是固定的，但是可以循环使用数组，所以这种队列也可以称之为循环队列。后者实现的队列内部通过指针指向形成一个队列，这种队列是单向且长度不固定，所以也称之为非循环队列。下面我将使用两种方式分别实现队列。

 

　　二、基于数组实现循环队列

　　由于在往队列中放数据或拉取数据的时候需要移动数组对应的下标，所以需要记录一下队尾和队头的位置。说一下几个核心的属性吧：

　　1、queue：队列，object类型的数组，用于存储数据，长度固定，当存储的数据数量大于数组当度则抛出异常；

　　2、head：队头指针，int类型，用于记录队列头部的位置信息。

　　3、tail：队尾指针，int类型，用于记录队列尾部的位置信息。

　　4、size：队列长度，队列长度大于等于0或者小于等于数组长度。

  1.  /**
  2.      * 队列管道，当管道中存放的数据大于队列的长度时将不会再offer数据，直至从队列中poll数据后
  3.      */
  4.     private Object[] queue;
  5.     //队列的头部，获取数据时总是从头部获取
  6.     private int head;
  7.     //队列尾部，push数据时总是从尾部添加
  8.     private int tail;
  9.     //队列长度
  10.     private int size;
  11.     //数组中能存放数据的最大容量
  12.     private final static int MAX_CAPACITY = 1<<30;
  13.     //数组长度
  14.     private int capacity;
  15.     //最大下标
  16.     private int maxIndex;

　　

　　三、数据结构

 

　　图中，红色部分即为队列的长度，数组的长度为16。因为这个队列是循环队列，所以队列的头部不一定要在队列尾部前面，只要队列的长度不大于数组的长度就可以了。

 

　　四、构造方法

　　1、MyQueue(int initialCapacity)：创建一个最大长度为 initialCapacity的队列。

　　2、MyQueue():创建一个默认最大长度的队列，默认长度为16；

  1.     public MyQueue(int initialCapacity){
  2.         if (initialCapacity > MAX_CAPACITY)
  3.             throw new OutOfMemoryError("initialCapacity too large");
  4.         if (initialCapacity <= 0)
  5.             throw new IndexOutOfBoundsException("initialCapacity must be more than zero");
  6.         queue = new Object[initialCapacity];
  7.         capacity = initialCapacity;
  8.         maxIndex = initialCapacity - 1;
  9.         head = tail = -1;
  10.         size = 0;
  11.     }
  12.     public MyQueue(){
  13.         queue = new Object[16];
  14.         capacity = 16;
  15.         head = tail = -1;
  16.         size = 0;
  17.         maxIndex = 15;
  18.     }

 

　　五、往队列添加数据

　　添加数据时，首先判断队列的长度是否超出了数组的长度，如果超出了就添加失败（也可以设置成等待，等到有人消费了队列里的数据，然后再添加进去）。都是从队列的尾部添加数据的，添加完数据后tail指针也会相应自增1。具体实现如一下代码：

  1. /**
  2.      * 往队列尾部添加数据
  3.      * @param object 数据
  4.      */
  5.     public void offer(Object object){
  6.         if (size >= capacity){
  7.             System.out.println("queue's size more than or equal to array's capacity");
  8.             return;
  9.         }
  10.         if (++tail > maxIndex){
  11.             tail = 0;
  12.         }
  13.         queue[tail] = object;
  14.         size++;
  15.     }

 

　　六、向队列中拉取数据

　　拉取数据是从队列头部拉取的，拉取完之后将该元素删除，队列的长度减一，head自增1。代码如下：

  1.     /**
  2.      * 从队列头部拉出数据
  3.      * @return 返回队列的第一个数据
  4.      */
  5.     public Object poll(){
  6.         if (size <= 0){
  7.             System.out.println("the queue is null");
  8.             return null;
  9.         }
  10.         if (++head > maxIndex){
  11.             head = 0;
  12.         }
  13.         size--;
  14.         Object old = queue[head];
  15.         queue[head] = null;
  16.         return old;
  17.     }

　　

　　七、其他方法

　　1、查看数据：这个方法跟拉取数据一样都是获取到队列头部的数据，区别是该方法不会将对头数据删除：

  1. /**
  2.      * 查看第一个数据
  3.      * @return
  4.      */
  5.     public Object peek(){
  6.         return queue[head];
  7.     }

　　2、清空队列：

  1. /**
  2.      * 清空队列
  3.      */
  4.     public void clear(){
  5.         for (int i = 0; i < queue.length; i++) {
  6.             queue[i] = null;
  7.         }
  8.         tail = head = -1;
  9.         size = 0;
  10.     }

　　完整的代码如下：

  1. /**
  2.  * 队列
  3.  */
  4. public class MyQueue {
  6.     /**
  7.      * 队列管道，当管道中存放的数据大于队列的长度时将不会再offer数据，直至从队列中poll数据后
  8.      */
  9.     private Object[] queue;
  10.     //队列的头部，获取数据时总是从头部获取
  11.     private int head;
  12.     //队列尾部，push数据时总是从尾部添加
  13.     private int tail;
  14.     //队列长度
  15.     private int size;
  16.     //数组中能存放数据的最大容量
  17.     private final static int MAX_CAPACITY = 1<<30;
  18.     //数组长度
  19.     private int capacity;
  20.     //最大下标
  21.     private int maxIndex;
  23.     public MyQueue(int initialCapacity){
  24.         if (initialCapacity > MAX_CAPACITY)
  25.             throw new OutOfMemoryError("initialCapacity too large");
  26.         if (initialCapacity <= 0)
  27.             throw new IndexOutOfBoundsException("initialCapacity must be more than zero");
  28.         queue = new Object[initialCapacity];
  29.         capacity = initialCapacity;
  30.         maxIndex = initialCapacity - 1;
  31.         head = tail = -1;
  32.         size = 0;
  33.     }
  34.     public MyQueue(){
  35.         queue = new Object[16];
  36.         capacity = 16;
  37.         head = tail = -1;
  38.         size = 0;
  39.         maxIndex = 15;
  40.     }
  42.     /**
  43.      * 往队列尾部添加数据
  44.      * @param object 数据
  45.      */
  46.     public void offer(Object object){
  47.         if (size >= capacity){
  48.             System.out.println("queue's size more than or equal to array's capacity");
  49.             return;
  50.         }
  51.         if (++tail > maxIndex){
  52.             tail = 0;
  53.         }
  54.         queue[tail] = object;
  55.         size++;
  56.     }
  58.     /**
  59.      * 从队列头部拉出数据
  60.      * @return 返回队列的第一个数据
  61.      */
  62.     public Object poll(){
  63.         if (size <= 0){
  64.             System.out.println("the queue is null");
  65.             return null;
  66.         }
  67.         if (++head > maxIndex){
  68.             head = 0;
  69.         }
  70.         size--;
  71.         Object old = queue[head];
  72.         queue[head] = null;
  73.         return old;
  74.     }
  76.     /**
  77.      * 查看第一个数据
  78.      * @return
  79.      */
  80.     public Object peek(){
  81.         return queue[head];
  82.     }
  84.     /**
  85.      * 队列中存储的数据量
  86.      * @return
  87.      */
  88.     public int size(){
  89.         return size;
  90.     }
  92.     /**
  93.      * 队列是否为空
  94.      * @return
  95.      */
  96.     public boolean isEmpty(){
  97.         return size == 0;
  98.     }
  100.     /**
  101.      * 清空队列
  102.      */
  103.     public void clear(){
  104.         for (int i = 0; i < queue.length; i++) {
  105.             queue[i] = null;
  106.         }
  107.         tail = head = -1;
  108.         size = 0;
  109.     }
  111.     @Override
  112.     public String toString() {
  113.         if (size <= 0) return "{}";
  114.         StringBuilder builder = new StringBuilder(size + 8);
  115.         builder.append("{");
  116.         int h = head;
  117.         int count = 0;
  118.         while (count < size){
  119.             if (++h > maxIndex) h = 0;
  120.             builder.append(queue[h]);
  121.             builder.append(", ");
  122.             count++;
  123.         }
  124.         return builder.substring(0,builder.length()-2) + "}";
  125.     }
  126. }

　　

　　八、总结：

　　1、该队列为非线程安全的，在多线程环境中可能会发生数据丢失等问题。

　　2、队列通过移动指针来确定数组下标的位置，因为是基于数组实现的，所以队列的长度不能够超过数组的长度。

　　3、该队列是循环队列，这就意味着数组可以重复被使用，避免了重复创建对象带来的性能的开销。

　　4、添加数据时总是从队列尾部添加，拉取数据时总是从队列头部拉取，拉取完将对象元素删除。

 

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

Java热门文章

  • 【IDEA】Application context not configured for this file
  • [IDEA] chapter_reader - idea看小说插件 idea阅读插件 idea摸鱼插件
  • thrift常见异常及原因分析
  • Java 调用 PaddleDetection 模型
  • JVM 详解，大白话带你认识 JVM
  • spring-boot-2.0.3不一样系列之番外篇 - @Configuration、Condition与@Conditional
  • Java Comparator.comparing比较导致空指针异常的解决
  • Java使用EasyExcel进行单元格合并的问题详解
  • 死磕 java集合之ArrayBlockingQueue源码分析
  • Java基础之集合Set详解

    • Java推荐文章

  • 面试场景题：一次关于线程池使用场景的讨论。
  • 前端黑科技：使用 JavaScript 实现网页扫码功能
  • 聊一聊 Netty 数据搬运工 ByteBuf 体系的设计与实现
  • 简单设计一个JAVA并行处理工具类
  • 【杂谈】JPA乐观锁改悲观锁遇到的一些问题与思考
  • 认识netty的基本组件
  • Jenkins如何使用CrumbIssuer防御CSRF攻击
  • 如何平稳地从nacos迁移到r-nacos？
  • 线程池遇到父子任务，有大坑，要注意！
  • Java JVM——12. 垃圾回收理论概述

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号