Java 队列实现原理及简单实现代码.docx

Java队列实现原理及简单实现代码Java队列实现原理及简单实现代码Java队列实现原理“队列”这个单词是英国人说的“排”。在英国“排队”的意思就是站到一排当中去。计算机科学中，队列是一种数据结构，有点类似栈，只是在队列中第一个插入的数据项也会最先被移除，而在栈中，最后插入的数据项最先移除。队列的作用就像电影院前的人们站成的排一样：第一个进入附属的人将最先到达队头买票。最后排队的人最后才能买到票。队列和栈一样也被用作程序员的工具。它也可以用于模拟真实世界的环境，例如模拟人们在银行里排队等待，飞机等待起飞，或者因特网络上数据包等待传送。在计算机操作系统里，有各种队列在安静地工作着。打印作业在打印队列中等待打印。当在键盘上敲击时，也有一个存储键入内容的队列。同样，如果使用文字处理程序敲击一个键，而计算机又暂时要做其它的事，敲击的内容不会丢失，它会排在队列中等待，直到文字处理程序有时间来读取它。利用队列保证了键入内容在处理时其顺序不会改变。队列的基本操作队列的两个基本操作是ing(插入)一个数据项，即把一个数据项放入队尾，另一个是removing(移除)一个数据项，即移除队头的数据项。这类似于电影爱好者排队买票时先排到队尾，然后到达队头买票后离开队列。栈中的插入和移除数据项方法的命名是很标准，称为push和pop。队列的方法至今没有标准化的命名。“插入”可以称为put、add或enque，而“删除”可以叫、get或deque。插入数据项的队尾，也可以叫作back、tail或end。而移除数据项的队头，也可以叫head。下面将使用、remove、front和rear。插入将值插入队尾，同时队尾箭头增加一，指向新的数据项。数据项被移除后，同时队头指针增加一。通常实现队列时，删除的数据项还会保存在内存中，只是它不能被访问了，因为队头指针已经移到它的下一个位置了。和栈中的情况不同，队列中的数据项不总是从数组的0下标处开始。移除了一些数据项后，队头指针会指向一个较高的下标位置。查看操作返回队头数据项的值，然而并不从队中删除这个数据项。要是想从空队列中移除一个数据项或想在已经满的队列中插入一个数据项，应用程序都要提示出错消息。循环队列当在队列中插入一个新数据项，队头的Rear箭头向上移动，移向数组下标大的位置。移除数据项时，队尾Front指针也会向上移动。这种设计可能和人们直观察觉相反，因为人们在买电影票排队时，队伍总是向前移动的，当前面的人买完票离开队伍后，其他人都向前移动。计算机中在队列里删除一个数据项后，也可以将其他数据项都向前移动，但这样做的效率很差。相反，我们通过队列中队头和队尾指针的移动保持所有数据项的位置不变。这样设计的问题是队尾指针很快就会移到数组的末端。虽然在数组的开始部分有空的数据项单元，这是移除的数据项的位置，但是由于因为队尾指针不能再向后移动了，因此也不能再插入新的`数据项，这该怎么办？环绕式处理为了避免队列不满却不能插入新数据项的问题，可以让队头队尾指针绕回到数组开始的位置。这就是循环队列（有时也称为“缓冲环”）。指针回绕的过程：在队列中插入足够多的数据项，使队尾指针指向数组的未端。再删除几个数组前端的数据项。现在插入一个新的数据项。就会看到队尾指针从未端回绕到开始处的位置。新的数据项将插入这个位置。插入更多的数据项。队尾指针如预计的那样向上移动。注意在队尾指针回绕之后，它现在处在队头指针的下面，这就颠倒了初始的位置。这可以称为“折断的序列”：队列中的数据项存在数组两个不同的序列中。删除足够多的数据项后，队头指针也回绕。这时队列的指针回到了初始运行时的位置状态，队头指针在队尾指针的下面。数据项也恢复为单一的连续的序列。队列的Java代码Queue.java程序创建了一个Queue类，它有()、remove()、peek()、isEmpty()和size()方法。package栈和队列;classQueue{privateintmaxSize;privatelong[]queArray;privateintfront;privateintrear;privateintnItems;publicQueue(ints){maxSize=s;queArray=newlong[maxSize];front=0;rear=-1;nItems=0;}publicvoid(longj){if(rear==maxSize-1)rear=-1;queArray[++rear]=j;nItems++;}publiclongremove(){longtemp=queArray[front++];if(front==maxSize)front=0;nItems--;returntemp;}publiclongpeekFront(){return