一、队列（Queue）
队列是一种特殊的线性表，它只允许在表的前段（front）进行删除操作，只允许在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。
对于一个队列来说，每个元素总是从队列的rear端进入队列，然后等待该元素之前的所有元素出队之后，当前元素才能出对，遵循先进先出（FIFO）原则。
如果队列中不包含任何元素，该队列就被称为空队列。
Java提供了一个Queue接口，并为该接口提供了众多的实现类：ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、PriorityQueue、ConcurrentLinkedQueue和SynchronousQueue。
其中常用的是：ArrayBlockingQueue、LinkedBlockingQueue和CurrentLinkedQueue，它们都是线程安全的队列。LinkedBlockingQueue队列的吞吐量通常比ArrayBlockingQueue队列高，但在大多数并发应用程序中，LinkedBlockingQueue的性能要低。
除了LinkedBlockingQueue队列之外，JDK还提供了另外一种链队列ConcurrentLinkedQueue，它基于一种先进的、无等待（wait-free）队列算法实现。
二、顺序队列存储结构的实现
package com.ietree.basic.datastructure.queue;
import java.util.Arrays;
/**
* Created by ietree
* 2017/4/29
*/
public class SequenceQueue<T> {
private int DEFAULT_SIZE = 10;
// 保存数组的长度
private int capacity;
// 定义一个数组用于保存顺序队列的元素
private Object[] elementData;
// 保存顺序队列中元素的当前个数
private int front = 0;
private int rear = 0;
// 以默认数组长度创建空顺序队列
public SequenceQueue() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
// 以一个初始化元素来创建顺序队列
public SequenceQueue(T element) {
this();
elementData[0] = element;
rear++;
}
/**
* 以指定长度的数组来创建顺序线性表
*
* @param element 指定顺序队列中第一个元素
* @param initSize 指定顺序队列底层数组的长度
*/
public SequenceQueue(T element, int initSize) {
this.capacity = initSize;
elementData = new Object[capacity];
elementData[0] = element;
rear++;
}
/**
* 获取顺序队列的大小
*
* @return 顺序队列的大小值
*/
public int length() {
return rear - front;
}
/**
* 插入队列
*
* @param element 入队列的元素
*/
public void add(T element) {
if (rear > capacity - 1) {
throw new IndexOutOfBoundsException("队列已满异常");
}
elementData[rear++] = element;
}
/**
* 移除队列
*
* @return 出队列的元素
*/
public T remove() {
if (empty()) {
throw new IndexOutOfBoundsException("空队列异常");
}
// 保留队列的rear端的元素的值
T oldValue = (T) elementData[front];
// 释放队列顶元素
elementData[front++] = null;
return oldValue;
}
// 返回队列顶元素，但不删除队列顶元素
public T element() {
if (empty()) {
throw new IndexOutOfBoundsException("空队列异常");
}
return (T) elementData[front];
}
// 判断顺序队列是否为空
public boolean empty() {
return rear == front;
}
// 清空顺序队列
public void clear() {
// 将底层数组所有元素赋值为null
Arrays.fill(elementData, null);
front = 0;
rear = 0;
}
public String toString() {
if (empty()) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
for (int i = front; i < rear; i++) {
sb.append(elementData[i].toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
}
}
测试类：
package com.ietree.basic.datastructure.queue;
/**
* Created by ietree
* 2017/4/30
*/
public class SequenceQueueTest {
public static void main(String[] args) {