一、定义
队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表，进行插入操作的一端称为队尾（rear），进行删除的一端为队头（front），插入数据元素的操作叫做入队，删除数据元素的操作叫做出队，它具有先进先出（First In First Out，FIFO）的特性。
二、队列的基本操作分析
前面章节说到，线性表可以通过顺序存储和链式存储来实现，作为操作受限的线性表也一样，所以后面也会通过两种存储结构来分析队列的基本操作实现。
在顺序存储结构中，一般会使用数组来实现，定义一个队列，约定使用 front 来存放队头元素的位置，使用 rear 来存放队尾的位置，当 front=rear=-1 时表示队列为空，入队和出队都是通过移动 rear 和 front 指针来实现，如下图所示，当 a9 入队后不能再做入队操作，而实际上空间并没有占满，此时会出现假溢出现象，为了避免这种情况，我们可以把该连续空间视为“循环顺序队列”。
在循环顺序队列中，当 a9 入队后再做入队操作时，会将数据元素存储在数组前面出队后的空闲空间中，这样数据元素在数组中就会形成一个循环的队列，在这种情况下，当队满或者空队时都会存在 front=rear ，所以要通过 size 来判断队列是空还是满，当 size=array.length 时队满，当 size=0 时队空。使用循环队列时，队头和队尾的位置变换实现如下：
在链式存储结构中，可以直接使用单向链表来实现队列，此时，我们把链表的头部作为队头，把链表的尾部作为队尾，也就是说，在链表尾部插入，链表头部删除，在代码实现中，需要定义两个指针 front 和 rear 分别指向链表的第1个结点和最后1个结点。
1. 入队
在顺序存储中进行入队操作，只需要通过 rear 来定位队尾位置，然后做入队操作，执行完后 rear 移到新的队尾位置。链式存储中，需要将新的结点添加到链表尾部，首先把 a4 赋值给 rear.next，然后新结点 a4 成为新的尾部结点。
2. 出队
顺序存储中进行出队操作，通过 front 定位并获取队头元素，然后做出队操作，执行完后 front 移动到新的队头位置。链式存储中，做出队操作时，获取到头部结点元素 a1 后，然后直接把 front.next 赋值给 front 来实现队头元素的删除。
下面新建一个队列常规操作的接口，然后我们分别使用顺序结构（数组）和链式结构来实现它，读者可以分别对两种存储结构实现的接口的时间复杂度进行分析。
public interface Queue<T> { /** * 入队 */ boolean add(T t); /** * 出队 */ T remove(); /** * 判断队列是否为空 */ boolean isEmpty(); /** * 打印队列所有数据 */ void print(); }
三、队列的基本操作实现
和线性表实现一样，顺序结构使用数组来存储数据，链式结构使用结点来存储数据。
1. 顺序存储实现
public class ArrayQueue<T> implements Queue<T> { private int front = 0; private int rear = 0; private int size = 0; private Object[] elementData; public ArrayQueue(int size) { this.elementData = new Object[size]; } @Override public boolean add(T t) { if (front == rear && size == elementData.length) { throw new ArrayIndexOutOfBoundsException(); } elementData[rear] = t; rear = (rear + 1) % elementData.length; size++; return true; } @SuppressWarnings("unchecked") @Override public T remove() { if (front == rear && size == 0) { throw new NullPointerException(); } Object t = elementData[front]; elementData[front] = null; front = (front + 1) % elementData.length; size--; return (T) t; } @Override public boolean isEmpty() { return size == 0; } @Override public void print() { System.out.println(Arrays.toString(elementData)); } }
2. 链式存储实现
public class LinkedQueue<T> implements Queue<T> { private Node front; private Node rear; private int size = 0; private class Node { private T t; private Node next; public Node() { } public Node(T t, Node next) { this.t = t; this.next = next; } } @Override public boolean add(T t) { Node n = new Node(t, null); if (rear != null) { rear.next = n; } if (front == null) { front = n; } rear = n; size++; return false; } @Override public T remove() { if (front == null) { throw new NullPointerException(); } T t = front.t; front = front.next; size--; return t; } @Override public boolean isEmpty() { return size == 0; } @Override public void print() { Node n = front; while (n != null) { System.out.print(n.t + ","); n = n.next; } System.out.println(); } }
