教你如何使用Java手写一个基于数组实现的队列

2018-11-22 08:42:47来源：博客园阅读 ()

　　一、概述

　　队列，又称为伫列（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或者小于等于数组长度。

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

　　三、数据结构

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

　　四、构造方法

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

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

    public MyQueue(int initialCapacity){
        if (initialCapacity > MAX_CAPACITY)
            throw new OutOfMemoryError("initialCapacity too large");
        if (initialCapacity <= 0)
            throw new IndexOutOfBoundsException("initialCapacity must be more than zero");
        queue = new Object[initialCapacity];
        capacity = initialCapacity;
        maxIndex = initialCapacity - 1;
        head = tail = -1;
        size = 0;
    }
    public MyQueue(){
        queue = new Object[16];
        capacity = 16;
        head = tail = -1;
        size = 0;
        maxIndex = 15;
    }

　　五、往队列添加数据

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

/**
     * 往队列尾部添加数据
     * @param object 数据
     */
    public void offer(Object object){
        if (size >= capacity){
            System.out.println("queue's size more than or equal to array's capacity");
            return;
        }
        if (++tail > maxIndex){
            tail = 0;
        }
        queue[tail] = object;
        size++;
    }

　　六、向队列中拉取数据

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

    /**
     * 从队列头部拉出数据
     * @return 返回队列的第一个数据
     */
    public Object poll(){
        if (size <= 0){
            System.out.println("the queue is null");
            return null;
        }
        if (++head > maxIndex){
            head = 0;
        }
        size--;
        Object old = queue[head];
        queue[head] = null;
        return old;
    }

　　七、其他方法

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

/**
     * 查看第一个数据
     * @return
     */
    public Object peek(){
        return queue[head];
    }

　　2、清空队列：

/**
     * 清空队列
     */
    public void clear(){
        for (int i = 0; i < queue.length; i++) {
            queue[i] = null;
        }
        tail = head = -1;
        size = 0;
    }

　　完整的代码如下：

/**
 * 队列
 */
public class MyQueue {

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

    public MyQueue(int initialCapacity){
        if (initialCapacity > MAX_CAPACITY)
            throw new OutOfMemoryError("initialCapacity too large");
        if (initialCapacity <= 0)
            throw new IndexOutOfBoundsException("initialCapacity must be more than zero");
        queue = new Object[initialCapacity];
        capacity = initialCapacity;
        maxIndex = initialCapacity - 1;
        head = tail = -1;
        size = 0;
    }
    public MyQueue(){
        queue = new Object[16];
        capacity = 16;
        head = tail = -1;
        size = 0;
        maxIndex = 15;
    }

    /**
     * 往队列尾部添加数据
     * @param object 数据
     */
    public void offer(Object object){
        if (size >= capacity){
            System.out.println("queue's size more than or equal to array's capacity");
            return;
        }
        if (++tail > maxIndex){
            tail = 0;
        }
        queue[tail] = object;
        size++;
    }

    /**
     * 从队列头部拉出数据
     * @return 返回队列的第一个数据
     */
    public Object poll(){
        if (size <= 0){
            System.out.println("the queue is null");
            return null;
        }
        if (++head > maxIndex){
            head = 0;
        }
        size--;
        Object old = queue[head];
        queue[head] = null;
        return old;
    }

    /**
     * 查看第一个数据
     * @return
     */
    public Object peek(){
        return queue[head];
    }

    /**
     * 队列中存储的数据量
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 队列是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 清空队列
     */
    public void clear(){
        for (int i = 0; i < queue.length; i++) {
            queue[i] = null;
        }
        tail = head = -1;
        size = 0;
    }

    @Override
    public String toString() {
        if (size <= 0) return "{}";
        StringBuilder builder = new StringBuilder(size + 8);
        builder.append("{");
        int h = head;
        int count = 0;
        while (count < size){
            if (++h > maxIndex) h = 0;
            builder.append(queue[h]);
            builder.append(", ");
            count++;
        }
        return builder.substring(0,builder.length()-2) + "}";
    }
}