Java 队列

“队列”这个单词是英国人说的“排”。在英国“排队”的意思就是站到一排当中去。计算机科学中，队列是一种数据结构，有点类似栈，只是在队列中第一个插入的数据项也会最先被移除，而在栈中，最后插入的数据项最先移除。队列的作用就像电影院前的人们站成的排一样：第一个进入附属的人将最先到达队头买票。最后排队的人最后才能买到票。

队列和栈一样也被用作程序员的工具。它也可以用于模拟真实世界的环境，例如模拟人们在银行里排队等待，飞机等待起飞，或者因特网络上数据包等待传送。

在计算机操作系统里，有各种队列在安静地工作着。打印作业在打印队列中等待打印。当在键盘上敲击时，也有一个存储键入内容的队列。同样，如果使用文字处理程序敲击一个键，而计算机又暂时要做其它的事，敲击的内容不会丢失，它会排在队列中等待，直到文字处理程序有时间来读取它。利用队列保证了键入内容在处理时其顺序不会改变。


队列的基本操作

队列的两个基本操作是inserting(插入)一个数据项，即把一个数据项放入队尾，另一个是removing(移除)一个数据项，即移除队头的数据项。这类似于电影爱好者排队买票时先排到队尾，然后到达队头买票后离开队列。

栈中的插入和移除数据项方法的命名是很标准，称为push和pop。队列的方法至今没有标准化的命名。“插入”可以称为put、add或enque，而“删除”可以叫delete、get或deque。插入数据项的队尾，也可以叫作back、tail或end。而移除数据项的队头，也可以叫head。下面将使用insert、remove、front和rear。

插入将值插入队尾，同时队尾箭头增加一，指向新的数据项。

数据项被移除后，同时队头指针增加一。通常实现队列时，删除的数据项还会保存在内存中，只是它不能被访问了，因为队头指针已经移到它的下一个位置了。

和栈中的情况不同，队列中的数据项不总是从数组的0下标处开始。移除了一些数据项后，队头指针会指向一个较高的下标位置。

查看操作返回队头数据项的值，然而并不从队中删除这个数据项。

要是想从空队列中移除一个数据项或想在已经满的队列中插入一个数据项，应用程序都要提示出错消息。


循环队列

当在队列中插入一个新数据项，队头的Rear箭头向上移动，移向数组下标大的位置。移除数据项时，队尾Front指针也会向上移动。这种设计可能和人们直观察觉相反，因为人们在买电影票排队时，队伍总是向前移动的，当前面的人买完票离开队伍后，其他人都向前移动。计算机中在队列里删除一个数据项后，也可以将其他数据项都向前移动，但这样做的效率很差。相反，我们通过队列中队头和队尾指针的移动保持所有数据项的位置不变。

这样设计的问题是队尾指针很快就会移到数组的末端。虽然在数组的开始部分有空的数据项单元，这是移除的数据项的位置，但是由于因为队尾指针不能再向后移动了，因此也不能再插入新的数据项，这该怎么办？


环绕式处理

为了避免队列不满却不能插入新数据项的问题，可以让队头队尾指针绕回到数组开始的位置。这就是循环队列（有时也称为“缓冲环”）。

指针回绕的过程：在队列中插入足够多的数据项，使队尾指针指向数组的未端。再删除几个数组前端的数据项。现在插入一个新的数据项。就会看到队尾指针从未端回绕到开始处的位置。新的数据项将插入这个位置。

插入更多的数据项。队尾指针如预计的那样向上移动。注意在队尾指针回绕之后， 它现在处在队头指针的下面，这就颠倒了初始的位置。这可以称为“折断的序列”：队列中的数据项存在数组两个不同的序列中。

删除足够多的数据项后，队头指针也回绕。这时队列的指针回到了初始运行时的位置状态，队头指针在队尾指针的下面。数据项也恢复为单一的连续的序列。


队列的Java代码

Queue.java程序创建了一个Queue类，它有insert()、remove()、peek()、isEmpty()和size()方法。

package 栈和队列;

class Queue{

       private int maxSize;

       private long[] queArray;

       private int front;

       private int rear;

       private int nItems;


       public Queue(int s){

              maxSize=s;

              queArray=new long[maxSize];

              front=0;

              rear=-1;

              nItems=0;

       }


       public void insert(long j){

              if(rear==maxSize-1)

                     rear=-1;

              queArray[++rear]=j;

              nItems++;

       }


       public long remove(){

              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 ifFull(){

              return (nItems==maxSize);

       }


       public int size(){

              return nItems;

       }


}

程序实现的Queue类中不但有front(队头)和rear(队尾)字段，还有队列中当前数据项的个数：nItems。

Insert()方法运行的前提条件是队列不满。在Main()中没有显示这个方法，不过通常应该先调用isFull()方法并且返回false后，才调用insert()方法。（更通用的做法是在insert()方法中加入检查队列是否满的判定，如果出现向已满队列里插入数据项的情况就抛出异常。）

一般情况，插入操作是rear（队尾指针）加一后，在队尾指针所指的位置处插入新的数据。但是，当rear指针指向数组的顶端，即maxSize-1位置的时候，在插入数据项之前，它必须回绕到数组的底端。回绕操作把rear设置为-1，因此当rear加1后，它等于0，是数组底端的下标值，最后nItem加一。

Remove()方法运行的前提条件是队列不空，在调用这个方法之前应该调用isEmpty()方法确保队列不空，或者在remove()方法里加入这种出错检查的机制。

移除（remove）操作总是由front指针得到队头数据项的值，然后将front加一。但是，如果这样做使front的值超过数组的顶端，front就必须绕回到数组下标为0的位置上。作这种检验的同时，先将返回值临时存储起来。最后nItem减一。

Peek()方法简单易懂：它返回front指针所指数据项的值。有些队列的实现也允许查看队列队尾数据项的值；比如这些方法可称为peekFront()、peekRear()、或者只是front()和rear()。

isEmpty()、isFull()和size()方法的实现都依赖于nItems字段，它们分别返回nItems是否等于0，是否等于maxSize，或者返回它本身值。

在Queue类中包含数据项计数字段nItems会使insert()和remove()方法增加一点额外的操作，因为insert()和remove()方法必须分别递增和递减这个变量值。这可能算不上额外的开销，但是如果处理大量的插入和移除操作，这就可能会影响性能了。

因为，一些队列的实现不使用数据项计数的字段，而是通过front和rear来计算出队列是否空或者满以及数据项的个数。如果这样做，isEmpty()、ifFull()和size()例程会相当复杂，因为就像前面讲过的那样，数据项的序列或者被折成两段，或者是连续的一段。

而且，一个奇怪的问题出现了。当队列满的时候，front和rear指针取一定的位置，但是当队列为空时，也可能呈现相同的位置关系。于是在同一时间，队列似乎可能是满的，也可能是空的。这个问题的解决方法是：让数组容量比队列数据项个数的最大值学要大一。