队列
队列是一种操作受限制的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列中没有元素时，称为空队列。在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。
队列空的条件：front=rear
队列满的条件： rear = MAXSIZE
顺序队列
建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置．
顺序队列中的溢出现象：
下溢：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
真上溢：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
假上溢：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为”假上溢”现象。
java中Queue
Queue继承于Collection，除了基本的 Collection 操作外，队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。
add()和offer()都是将指定的元素插入队列
add() 在成功时返回 true，如果当前没有可用的空间，则抛出 IllegalStateException。
offer()当使用有容量限制的队列时,无法插入元素，而只是抛出一个异常。
element() 和 peek() 返回但不移除队列的头，如果队列为空，peek()返回 null，element()抛出异常。
remove() 和 poll() 方法可移除和返回队列的头，它们仅在队列为空时其行为有所不同：remove() 方法抛出一个异常，而 poll() 方法则返回 null。
一般使用：
public class TestQueue
{
/**
* @param args
* @author JavaAlpha
* Info 测试队列
*/
public static void main(String[] args)
{
Queue<String> queue = new LinkedList<String>();
queue.offer("1");
queue.offer("2");
queue.offer("3");
System.out.println("queue.size()"+queue.size());
for (String string : queue)
{
System.out.println(string);
}
}
}
结果：
queue.size()3
1
2
3
JDK中包含了 双向顺序队列ArrayDeque、双向链式队列LinkedList和PriorityQueue优先队列。
ArrayDeque包括顺序栈和顺序队列，LinkedList包含链式栈和链式队列。ArrayDeque和LinkedList都是线程不安全的。
Java顺序队列的实现：
package lang;
import java.io.Serializable;
import java.util.Arrays;
public class ArrayQueue<T> implements Serializable{
private static final long serialVersionUID = 7333344126529379197L;
private int DEFAULT_SIZE = 10;
private int capacity;
private Object[] elementData;
private int front = 0;
private int rear = 0;
public ArrayQueue() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
public ArrayQueue(T element) {
this();
elementData[0] = element;
rear++;
}
public ArrayQueue(int initSize) {
elementData = new Object[initSize];
}
/**
* 以指定长度的数组来创建顺序队列
* @param element 指定顺序队列中第一个元素
* @param initSize 指定顺序队列底层数组的长度
*/
public ArrayQueue(T element, int initSize) {
this.capacity = initSize;
elementData = new Object[capacity];
elementData[0] = element;
rear++;
}
/**
* @Title: size
* @Description: 获取顺序队列的大小
* @return
*/
public int size() {
return rear - front;
}
/**
* @Title: offer
* @Description: 入队
* @param element
*/
public void offer(T element) {
ensureCapacity(rear + 1);
elementData[rear++] = element;
}
private void ensureCapacity(int minCapacity) {
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
/**
* @Title: poll
* @Description: 出队
* @return
*/
public T poll() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("空队列异常");
}
T oldValue = (T) elementData[front];
elementData[front++] = null;
return oldValue;
}
/**
* @Title: peek
* @Description: 返回队列顶元素，但不删除队列顶元素
* @return
*/
public T peek() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("空队列异常");
}
return (T) elementData[front];
}
/**
* @Title: isEmpty
* @Description: 判断顺序队列是否为空队列
* @return
*/
public boolean isEmpty() {
return rear == front;
}
/**
* @Title: clear
* @Description: 清空顺序队列
*/
public void clear() {
Arrays.fill(elementData, null);
front = 0;
rear = 0;
}
public String toString() {
if (isEmpty()) {
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();
}
}
}
java链式队列的实现
package lang;
import java.io.Serializable;
public class LinkQueue<T> implements Serializable{
private static final long serialVersionUID = -6726728595616312615L;
private class Node {
private T data;
private Node next;
public Node() {
}
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
private Node front;
private Node rear;
private int size;
/**
* <p>Title: LinkQueue </p>
* <p>Description: 创建空链队列 </p>
*/
public LinkQueue() {
front = null;
rear = null;
}
/**
* <p>Title: LinkQueue </p>
* <p>Description: 以指定数据元素来创建链队列，该链队列只有一个元素</p>
*/
public LinkQueue(T element) {
front = new Node(element, null);
rear = front;
size++;
}
/**
* @Title: size
* @Description: 获取顺序队列的大小
* @return
*/
public int size() {
return size;
}
/**
* @Title: offer
* @Description: 入队
* @param element
*/
public void offer(T element) {
if (front == null) {
front = new Node(element, null);
rear = front;
} else {
Node newNode = new Node(element, null);
rear.next = newNode;
rear = newNode;
}
size++;
}
/**
* @Title: poll
* @Description: 出队
* @return
*/
public T poll() {
Node oldFront = front;
front = front.next;
oldFront.next = null;
size--;
return oldFront.data;
}
/**
* @Title: peek
* @Description: 返回队列顶元素，但不删除队列顶元素
* @return
*/
public T peek() {
return rear.data;
}
/**
* @Title: isEmpty
* @Description: 判断顺序队列是否为空队列
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* @Title: clear
* @Description: 清空顺序队列
*/
public void clear() {
front = null;
rear = null;
size = 0;
}
public String toString() {
if (isEmpty()) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
for (Node current = front; current != null; current = current.next) {
sb.append(current.data.toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
}
public static void main(String[] args) {
LinkQueue<String> queue = new LinkQueue<String>("aaaa");
queue.offer("bbbb");
queue.offer("cccc");
System.out.println(queue);
queue.poll();
System.out.println("删除一个元素后的队列：" + queue);
queue.offer("dddd");
System.out.println("再次添加元素后的队列：" + queue);
queue.poll();
queue.offer("eeee");
System.out.println(queue);
}
}
循环队列
为充分利用向量空间，克服”假溢出”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。这种循环队列可以以单链表的方式来在实际编程应用中来实现。
循环队列的队空与队满的条件
初始化建空队时， front=rear=0
当队空时：front=rear
当队满时：front=rear 亦成立
因此只凭等式front=rear无法判断队空还是队满。 有两种方法处理上述问题：
1、另设一个标志位以区别队列是空还是满。
2、少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即：
队空时： front=rear
队满时： (rear+1)%maxsize=front
front指向队首元素，rear指向队尾元素的下一个元素（始终指向空）。
循环队列的Java实现:
package lang;
import java.io.Serializable;
import java.util.Arrays;
public class LoopQueue<T> implements Serializable{
private static final long serialVersionUID = -3670496550272478781L;
private int DEFAULT_SIZE = 10;
private int capacity;
private Object[] elementData;
private int front = 0;
private int rear = 0;
public LoopQueue() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
public LoopQueue(T element) {
this();
elementData[0] = element;
rear++;
}
public LoopQueue(T element, int initSize) {
this.capacity = initSize;
elementData = new Object[capacity];
elementData[0] = element;
rear++;
}
public int size() {
if (isEmpty()) {
return 0;
}
return rear > front ? rear - front : capacity - (front - rear);
}
public void add(T element) {
if (rear == front && elementData[front] != null) {
throw new IndexOutOfBoundsException("队列已满的异常");
}
elementData[rear++] = element;
rear = rear == capacity ? 0 : rear;
}
public T remove() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("空队列异常");
}
T oldValue = (T) elementData[front];
elementData[front++] = null;
front = front == capacity ? 0 : front;
return oldValue;
}
public T element() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("空队列异常");
}
return (T) elementData[front];
}
public boolean isEmpty() {
return rear == front && elementData[rear] == null;
}
public void clear() {
Arrays.fill(elementData, null);
front = 0;
rear = 0;
}
public String toString() {
if (isEmpty()) {
return "[]";
} else {
if (front < rear) {
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();
}
else {
StringBuilder sb = new StringBuilder("[");
for (int i = front; i < capacity; i++) {
sb.append(elementData[i].toString() + ", ");
}
for (int i = 0; i < rear; i++) {
sb.append(elementData[i].toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
}
}
public static void main(String[] args) {
LoopQueue<String> queue = new LoopQueue<String>("aaaa", 3);
queue.add("bbbb");
queue.add("cccc");
System.out.println(queue);
queue.remove();
System.out.println("删除一个元素后的队列：" + queue);
queue.add("dddd");
System.out.println(queue);
System.out.println("队列满时的长度：" + queue.size());
queue.remove();
queue.add("eeee");
System.out.println(queue);
}
}
阻塞队列（BlockingQueue）
几种主要的阻塞队列
自从Java 1.5之后，在java.util.concurrent包下提供了若干个阻塞队列，主要有以下几个：
ArrayBlockingQueue：基于数组实现的一个阻塞队列，在创建ArrayBlockingQueue对象时必须制定容量大小。并且可以指定公平性与非公平性，默认情况下为非公平的，即不保证等待时间最长的队列最优先能够访问队列。
LinkedBlockingQueue：基于链表实现的一个阻塞队列，在创建LinkedBlockingQueue对象时如果不指定容量大小，则默认大小为Integer.MAX_VALUE。
PriorityBlockingQueue：以上2种队列都是先进先出队列，而PriorityBlockingQueue却不是，它会按照元素的优先级对元素进行排序，按照优先级顺序出队，每次出队的元素都是优先级最高的元素。注意，此阻塞队列为无界阻塞队列，即容量没有上限（通过源码就可以知道，它没有容器满的信号标志），前面2种都是有界队列。
DelayQueue：基于PriorityQueue，一种延时阻塞队列，DelayQueue中的元素只有当其指定的延迟时间到了，才能够从队列中获取到该元素。DelayQueue也是一个无界队列，因此往队列中插入数据的操作（生产者）永远不会被阻塞，而只有获取数据的操作（消费者）才会被阻塞。
阻塞队列方法对比
1. 非阻塞队列中的几个主要方法：
add(E e):将元素e插入到队列末尾，如果插入成功，则返回true；如果插入失败（即队列已满），则会抛出异常；
remove()：移除队首元素，若移除成功，则返回true；如果移除失败（队列为空），则会抛出异常；
offer(E e)：将元素e插入到队列末尾，如果插入成功，则返回true；如果插入失败（即队列已满），则返回false；
poll()：移除并获取队首元素，若成功，则返回队首元素；否则返回null；
peek()：获取队首元素，若成功，则返回队首元素；否则返回null
对于非阻塞队列，一般情况下建议使用offer、poll和peek三个方法，不建议使用add和remove方法。因为使用offer、poll和peek三个方法可以通过返回值判断操作成功与否，而使用add和remove方法却不能达到这样的效果。注意，非阻塞队列中的方法都没有进行同步措施。
2. 阻塞队列中的几个主要方法：
阻塞队列包括了非阻塞队列中的大部分方法，上面列举的5个方法在阻塞队列中都存在，但是要注意这5个方法在阻塞队列中都进行了同步措施。除此之外，阻塞队列提供了另外4个非常有用的方法：
put(E e)
take()
offer(E e,long timeout, TimeUnit unit)
poll(long timeout, TimeUnit unit)
put方法用来向队尾存入元素，如果队列满，则等待；
take方法用来从队首取元素，如果队列为空，则等待；
offer方法用来向队尾存入元素，如果队列满，则等待一定的时间，当时间期限达到时，如果还没有插入成功，则返回false；否则返回true；
poll方法用来从队首取元素，如果队列空，则等待一定的时间，当时间期限达到时，如果取到，则返回null；否则返回取得的元素；
阻塞队列内部是通过Object.wait()、Object.notify()实现的，下面来看
使用阻塞队列实现的生产者-消费者的例子：
public class Test {
private static Integer count = 0;
final BlockingQueue<Integer> bq = new ArrayBlockingQueue<Integer>(5);
public static void main(String[] args) {
Test t = new Test();
new Thread(t.new Producer()).start();
new Thread(t.new Consumer()).start();
new Thread(t.new Consumer()).start();
new Thread(t.new Producer()).start();
}
class Producer implements Runnable {
@Override
public void run() {
for (int i = 0; i < 5; i++) {
try {
Thread.sleep(1000);
} catch (Exception e) {
e.printStackTrace();
}
try {
bq.put(1);
count++;
System.out.println(Thread.currentThread().getName() + "produce:: " + count);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
class Consumer implements Runnable {
@Override
public void run() {
for (int i = 0; i < 5; i++) {
try {
Thread.sleep(1000);
} catch (InterruptedException e1) {
e1.printStackTrace();
}
try {
bq.take();
count--;
System.out.println(Thread.currentThread().getName()+ "consume:: " + count);
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
}
原文地址：http://blog.csdn.net/amazing7/article/details/51362782
