01 Java基本数据结构之栈实现
02 Java基本数据结构之队列实现
03 Java基本数据结构之优先级队列
04 Java基本数据结构之链表
如有错误，还请指出
仍然先简单介绍一下队列的基本结构，然后是整体的代码实现，最后对每个部分需要注意的点作了详细说明。
队列，类似于栈，只是队列中第一个插入的数据项最先被移除（先进先出，FIFO），而在栈中，最后插入的数据项最先移除（LIFO）。
举个例子，可以用于模拟真实世界的环境，例如模拟人们在银行里排队等待，飞机等待起飞，或者网络上数据包等待传送。
本次队列实现仍是使用数组实现的，在后面的部分，如理解了链表后，可以使用链表实现。数组实现是一种很简单同时很好理解的方式。
package queue;
/*
* 数组实现的循环队列 有数据项计数字段
* insert : 判断isFull 队尾指针先+1，再插值，到达最大索引时队尾指针则置为-1，接着+1插值
* remove : 判断isEmpty 出队，队头指针+1，出队后队头指针大于最大索引时，队头指针置为0，
* peekFront 查看队头
* isEmpty
* isFull
* size
* */
public class Queue01 {
private int maxSize; //最大空间
private long[] queArray; //实现队列的数组
private int front; //队头指针
private int rear; //队尾指针
private int nItems; //已入队的数量
//构造器
public Queue01(int maxSize) {
this.maxSize = maxSize;
this.queArray = new long[maxSize];
this.front = 0;
this.rear = -1; // 插入数据时，rear是先+1再插数据，因此初始化为-1
this.nItems = 0;
}
public void insert(long item) throws Exception {
if(isFull())throw new Exception("队列满");
if (rear==maxSize-1) rear=-1;
queArray[++rear]=item;
nItems++;
}
public long remove() throws Exception {
if (isEmpty())throw new Exception("队列空");
long temp=queArray[front++];
if (front==maxSize) front=0;
nItems--;
return temp;
}
public long peekFront(){
return queArray[front];
}
public boolean isEmpty(){
return nItems==0;
}
public boolean isFull(){
return nItems==maxSize;
}
public int size(){
return nItems;
}
}
队列插入数据时，rear指针向上移动，移向数组下标大的位置。移除数据时，front指针也会向上移动，这样问题是队尾指针很快移动到数组的末端（数组下标最大），但虽然前面有空的单元，由于队尾 rear指针无法移动吗，因此不能插入新数据。
为了避免队列不满却不能插入新数据的问题，可以让队头队尾指针绕回到数组开始的位置，这就是循环队列（又是也称为“缓冲换”）。
构造器根据参数规定的容量大小创建一个队列，front 为队头指针，rear为队尾指针，同时使用了一个数据项计数字段 nItems来记录队列里的元素个数。
插入操作时 rear（队尾指针）加一后，在队尾指针所指的位置处插入新的数据。但是，当rear指针指向数据的顶端，即maxSize-1位置的时候，在插入数据像之前，必须回绕到数组的底端。回绕操作是把 rear 设置为-1，因此这是 rear 加1后，它等于0，是数组底端的下标值。最后，nItem 加一。
出队操作总是由 front 指针得到队头数据项的值，然后 front 加一，但是可能导致 front的值大于数组的顶端（即最大索引），这种情况下 front 就必须回到数组底端。
返回front指针所指的数据项的值，有些队列的实现也允许查看队列队尾的值。
空、满判断在数据结构里是非常重要的，在基本数据结构的实现中，会根据判断结果设计不同的后续处理，在后面的文章中会有所体现。
另外，isEmpty(),isFull(), size() 这些方法的实现依赖于nItems字段，包含 字段nItems 会使 insert()和remove() 方法增加一点额外的操作，因为得分别递增和递减这个变量值。这可能算不上额外的开销，但如果处理大量的入队和出队操作，可能就会影响性能了。
因此一些队列的实现不使用数据项计数的字段，而是通过 front 和 rear 计算出队列是否空满以及插入数据个数，如果这样做，isEmpty(),isFull(), size() 这些方法的实现会比较复杂。
下面是 没有数据项计数字段的队列实现，对于如何通过front 和 rear 指针判断的，可以查看大话数据结构里的队列部分，或者网上查阅，主要理解指针移动后里面的数学关系。
/*
* 数组实现的循环队列 没有数据项计数字段，
* 通过rear 和front的关系计算队列是否为空、满、数据个数
* 注意 isEmpty(),isFull(),size()的复杂性
* */
public class Queue02 {
private int maxSize; //最大空间
private long[] queArray; //实现队列的数组
private int front; //队头指针
private int rear; //队尾指针
// private int nItems;
//构造器
public Queue02(int maxSize) {
this.maxSize = maxSize+1; //数组容量比数据项个数多1
this.queArray = new long[maxSize];
this.front = 0;
this.rear = -1;
}
public void insert(long item) throws Exception {
if(isFull())throw new Exception("队列满");
if (rear==maxSize-1) rear=-1;
queArray[++rear]=item;
}
public long remove() throws Exception {
if (isEmpty())throw new Exception("队列空");
long temp=queArray[front++];
if (front==maxSize) front=0;
return temp;
}
public long peekFront(){
return queArray[front];
}
// 通过 front 和 rear的数学关系判断
public boolean isEmpty(){
return rear+1==front||front+maxSize-1==rear;
}
public boolean isFull(){
return rear+2==front||front+maxSize-2==rear;
}
public int size(){
if (rear>=front)
return rear-front+1;
else
return (maxSize-front)+(rear+1);
}
}
public class QueueTest {
public static void main(String[] args) throws Exception {
System.out.println("数组实现的循环队列 有数据项计数字段");
Queue01 theQueue=new Queue01(5);
theQueue.insert(10);
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.insert(50);
System.out.println(theQueue.peekFront());
System.out.println(theQueue.remove());
System.out.println(theQueue.remove());
}
}
/*
数组实现的循环队列 有数据项计数字段
10
10
20
*/