Queue: A lost Java.util class
Standard Java Bag Java.util's appearance, brings a lot of useful data structures (like stack stack, link table LinkedList, Hashi Hashset and Tree Set Treeset). But unfortunately, queue classes in this standard package Not implemented. In this article, we discuss three methods to implement the queue class.
The stack and queue stack is a data structure that can only operate the elements of it. For the stack of the computer, you can add an element to it, you can add an element above it (or add a plate). You can also delete an element (take a tray). This is called LIFO in this operational behavior (first out). In contrast, the queue is deleted in the order entered by an element. Usually we call FIFO (advanced first). The two basic operations of the stack are as follows:
Push: Push a new element into the top of the stack Pop: Remove and return the elements at the top of the stack. If the stack is empty, this action may trigger an exception.
a. Stack B containing four elements. PoP operation
Figure 1: Pop operation of the stack class.
Figure 1. The stack in Figure 1. The brown element is element of the top of the stack. Figure 1.B shows the same stack, the POP operation is performed, the brown element has been removed while the green element has become Stack top element.
Below is the two basic operations of the queue: Enqueue: Insert a new element in the tail of the queue Dequeue: Remove the team head element and return it, this action may trigger an exception if the queue is empty.
EmptyQueueException exception This exception is thrown by the queue Queue class to indicate queue Queue empty. This exception will be used in the three implementations discussed below.
Public Class EmptyQueueException Extends RuntimeException {Public EmptyQueueException () {}} First Method:
The first implementation method is similar to the implementation of the java.util.stack stack. The Java.util.Vector class will be expanded when realizing queue1.class. With some function operations, you can work with the queue. Public class Queue1 Extends Vector {public Object Enqueue (Object Element) {addElement; Return Element;
Public Object Dequeue () {int Len = size (); if (len == 0) throw new emptyqueueexception (); object obj = elementat (transoveElementatat (0); return obj;}}
The enqueue method uses inherited addelement methods to add an object to the vector vector, and the Dequeue method uses a inherited REMOEEEMENTAT method to remove the first object stored in the Vector. In the actual RemoveElementat method removes some additional tasks when the first element in the vector is removed. The remaining other elements in the vector must move a position up, please see Figure 2
It should be noted that this operation is performed, there is a performance problem, especially in a queue in the number of elements. Figure 2 demonstrates the first element of the vector vector each time the demueue method, causing the remaining other vector vectors to move upward. But this is no such problem for the stack stack, each call the POP method The last element of the vector vector will be removed, so other remaining elements are not necessary to move again (Figure 1). In other words, although this implementation method can effectively implement the stack Stack class, the power of the queue Queue class is not from the heart. a. Queue Queue B.dequeue with four elements Queue B.dequeue
Figure 2 is performed for the first time (other remaining elements have been moved upward.)
Last continued
Translated by windowsdna 2004/01/08
