队列的定义

队列是只允许在表的一端进行插入操作，而在另一端删除操作的线性表。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。如下图所示：

队列的抽象数据类型

同样是线性表，队列也有类似线性表的各种操作，不同的是插入数据只能在队尾进行，删除数据只能在队头进行。

Java中的Queue接口就定义了队列的功能。

public interface Queue<E> extends Collection<E> {
    
    /**
	 * 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
	 */
    boolean add(E e);
    
    /**
	 * 添加一个元素并返回true 如果队列已满，则返回false
	 */
    boolean offer(E e);
    
    /**
	 * 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
	 */
    E remove();
    
    /**
	 * 移除并返问队列头部的元素 如果队列为空，则返回null
	 */
    E poll();
    
    /**
	 * 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
	 */
    E element();
    
    /**
	 * 返回队列头部的元素 如果队列为空，则返回null
	 */
    E peek();
}

可以看到，添加、删除、查询这些个操作都提供了两种形式，其中一种在操作失败时直接抛出异常，而另一种则返回一个特殊的值：

操作	抛出异常	返回特殊值
插入数据	add(e)	offer(e)
删除数据	remove()	poll()
查看队头	element()	peek()

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

下面我们定义一个自己的队列接口：

/**
 * 队列的抽象数据类型
 * @param <E>
 */
public interface Queue<E> {
	
   /**
    * 清空队列
    */
    void clear();
	
    /**
     * 获取元素个数
     */
    int size();
    
    /**
     * 判断是否为空队列
     */
    boolean isEmpty();
    
    /**
     * 查看队头元素
     */
    E peek();
    
    /**
     * 将元素追加到队尾
     */
    E offer(E item);
    
    /**
     * 移除并返回队头元素
     */
    E poll();
}

队列的顺序存储结构实现

1. 队列顺序存储的不足

我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并 把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的 入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1),如图：

与栈不同的是，队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为O(n),如图：

可有时想想，为什么出队列时一定要全部移动呢，如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大増加。也就是说，队头不需要一定在下标为0的位置。

问题还不止于此。假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做假溢出。

2. 循环队列的定义

解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

在循环队列中，除了用一组地址连续的存储单元依次存储从队头到队尾的元素外，还需要附设两个整型变量front和rear分别指示队头和队尾的位置。

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。

在Java中，我们可以将循环队列视作一个类，通过成员变量数组来表示一组地址连续的存储单元，再定义两个成员变量front和rear，将循环队列的基本操作定义成类的方法，循环效果则用“模”运算实现，以此来实现循环队列。这样，初始化循环队列就是将类实例化，销毁就是销毁实例化出来的对象.

3. 循环队列实现

目前还有一个问题，大家想象一下：当front和rear指向同一个位置时,不仅可能是空队列，当队列满时，也是front等于rear，那么如何判断此时的队列究竟是空还是满呢?

解决这种问题的常见做法是这种：

• 使用一标记，用以区分这样的易混淆的情形。

• 牺牲一个元素空间。当front和rear相等时，为空。当rear的下一个位置是front时。为满。

以下我们给出循环队列，采用牺牲一个元素空间的方式来区分队空和队满。我们梳理下以下几个重点：

• front指向队头。rear指向队尾的下一个位置
• 队为空的推断：front==rear；队为满的推断：(rear+1)% QueueSize == front
• 当rear > front时，队列的长度 为rear-front，但当rear < front时，队列长度分为 两段， 一段是QueueSize-front,另一段是0 + rear,加在一起，队列长度为rear-front + QueueSize。因此通用的计算队列长度公式为：(rear—front + QueueSize) % QueueSize

接下来就是按照这个思路用代码实现了：

/**
 * 循环队列实现
 * @author hukai
 *
 */
public class LoopQueue<E> implements Queue<E> {
	
	/**
	 * 默认数组的长度
	 */
	private static final int DEFAULT_SIZE = 10;
	
	/**
	 * 最大容量
	 */
	private int queueSize;
	
	/**
	 * 定义一个数组用于保存循环队列的元素
	 */
	private Object[] elementData;
	
	/**
	 * 队头
	 */
	private int front;
	
	/**
	 * 队尾
	 */
	private int rear;
	
	/**
	 * 默认的构造方法，数组大小为10
	 */
	public LoopQueue() {
		this(DEFAULT_SIZE);
	}
	
	public LoopQueue(int queueSize){
		this.elementData = new Object[queueSize];
		this.queueSize = queueSize;
		this.front = 0;
		this.rear = 0;
	}
	
	/**
	 * 判断队列是否已满
	 */
	private boolean isFull(){
		return (rear + 1) % queueSize == front;
	}
	
	/**
	 * 清空队列
	 */
	@Override
	public void clear() {
		for (int i = 0; i < queueSize; i++) {
			elementData[i] = null;
		}
		this.front = 0;
		this.rear = 0;
	}
	
	/**
	 * 获取队列元素个数
	 */
	@Override
	public int size() {
		return (rear - front + queueSize) % queueSize;
	}
	
	/**
	 * 判断队列是否为空
	 */
	@Override
	public boolean isEmpty() {
		return rear == front;
	}
	
	/**
	 * 查看队头元素
	 */
	@Override
	public E peek() {
		// 如果队列为空，返回null
		if (isEmpty()) return null;
		return elementData(front);
	}
	
	/**
	 * 入队
	 */
	@Override
	public boolean offer(E item) {
		// 不允许null值入队
		if (item == null) throw new NullPointerException("入栈元素不能为空!");
		// 如果队列已满，返回false
		if (isFull()) return false;
		
		elementData[rear] = item;
		rear = (rear + 1) % queueSize;
		
		return true;
	}
	
	/**
	 * 出队
	 */
	@Override
	public E poll() {
		// 如果队列为空，返回null
		if (isEmpty()) return null;
		
		final E item = elementData(front);
		front = (front + 1) % queueSize;
		
		return item;
	}
	
	/**
	 * 返回此列表中指定位置的元素
	 */
	@SuppressWarnings("unchecked")
	E elementData(int index) {
		return (E) elementData[index];
	}

}

队列的链式存储结构

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而巳，我们把它简称为链队列。

我们来梳理下实现链队列的几个注意点：

• 队头front指向链表的头节点，队尾rear指向链表的尾节点。
• 当front和rear均为null时，队列为空
• 当front和rear指向同一个元素，队列中只有一个元素
• 插入操作是将数据元素追加到链表尾节点，删除操作则是移除链表头节点

下面上代码：

/**
 * 链队列实现
 * @author hukai
 *
 * @param <E>
 */
public class LinkedQueue<E> implements Queue<E> {
	
	private Node<E> front;//队头指针
	
	private Node<E> rear;//队尾指针
	
	private int size = 0;
	
	public LinkedQueue() {}
	
	@Override
	public void clear() {
		for (Node<E> x = front; x != null;) {
			Node<E> next = x.next;
			x.item = null;
			x.next = null;
			x = next;
		}
		front = null;
		rear = null;
		size = 0;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public E peek() {
		// 如果队列为空，返回null
		if (isEmpty()) return null;
		return front.item;
	}

	@Override
	public boolean offer(E item) {
		// 不允许null值入队
		if (item == null) throw new NullPointerException("入栈元素不能为空!");
		final Node<E> l = rear;
		final Node<E> newNode = new Node<E>(item, null);
		rear = newNode;
		if (l == null) {
			front = newNode;
		}else{
			l.next = newNode;
		}
		size++;
		return false;
	}

	@Override
	public E poll() {
		final Node<E> f = front;
		// 如果队列为空，返回null
		if (front == null) return null;
		
		final E element = f.item;
		final Node<E> next = f.next;
		f.item = null;
        f.next = null; // help GC
        front = next;
        if (next == null) rear = null;
        size--;
		return element;
	}
	
	/**
	 * Node内部类
	 */
	private static class Node<E> {
		E item;
		Node<E> next;

		Node(E element, Node<E> next) {
			this.item = element;
			this.next = next;
		}
	}

}