一、概述
队列，又称为伫列（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) + "}"; } }
八、总结：
1、该队列为非线程安全的，在多线程环境中可能会发生数据丢失等问题。
2、队列通过移动指针来确定数组下标的位置，因为是基于数组实现的，所以队列的长度不能够超过数组的长度。
3、该队列是循环队列，这就意味着数组可以重复被使用，避免了重复创建对象带来的性能的开销。
4、添加数据时总是从队列尾部添加，拉取数据时总是从队列头部拉取，拉取完将对象元素删除。