The Queue Interface :
A queue is a sequence of items that allow access only at two ends of the sequence. We refer to the ends of the sequence as the front and back. A queue inserts a new item at the back and removes an element from the front.
The Queue interface describe a queue as a storage structure. It defines the same methods as the Stack interface. The operation push() adds an item at the back of the queue. The operation pop() removes the first element (front) of the queue. To access the value of the first element, use the method peek(). Like any collection, a queue uses size() and the boolean isEmpty() to reflect the number of elements that are currently stored. Below figure illustrates the push() and pop() operations :
A queue removes elements in the same order they were stored, and hence it provides FIFO(First-In/First-Out) ordering. The abstract concept of a queue allows for an arbitrary large storage data. Hence, the push() operation has no precondition. The same is not true for the methods pop() and peak(), which assumes that the queue has at least one element. If the queue is empty, the methods throws a NoSuchElementException. The following is a interface definition of generic Queue interface :
Creating a Queue Collection Class :
In Section 14.1, we developed the ALStack class, which implements the Stack interface by composition. An ArrayList object is the underlying storage structure with methods that correspond to those in the interface. We use the same approach with the LinkedQueue class. In this interface, a LinkedList is the storage structure. The collection has methods getFirst() and removeFirst() that efficiently access and delete the front of the sequence. These operations provide a simple implementation of the queue peek() and pop() methods. A linked list also has the method add(), which efficiently inserts an element at the back of the sequence. We will use this to implement the queue push() operation.
The declaration of the LinkedQueue class implements the Queue interface using a private LinkedList reference variable qList and composition. The constructor creates an empty queue by initializing qList as an empty list. Below is the implementation :
Application: Scheduling Queue :
Let us look at one of the main applications of a queue, namely, a process or task scheduler. An executive secretary for a personnel director schedules a series of job interviews for applications seeking a position. The secretary uses a queue to store the starting times for the interviews. Also because the office closes at 5:00 P.M., and the last appointment begins at 16:30(4:30 P.M.), the last appointment lasts at most 30 minutes. Throughout the day, the director begins each interview by popping the queue and then calling peek() to identify the time for the next view. The information enables the director to determine the amount of time available for the interview :
A queue is a sequence of items that allow access only at two ends of the sequence. We refer to the ends of the sequence as the front and back. A queue inserts a new item at the back and removes an element from the front.
The Queue interface describe a queue as a storage structure. It defines the same methods as the Stack interface. The operation push() adds an item at the back of the queue. The operation pop() removes the first element (front) of the queue. To access the value of the first element, use the method peek(). Like any collection, a queue uses size() and the boolean isEmpty() to reflect the number of elements that are currently stored. Below figure illustrates the push() and pop() operations :
A queue removes elements in the same order they were stored, and hence it provides FIFO(First-In/First-Out) ordering. The abstract concept of a queue allows for an arbitrary large storage data. Hence, the push() operation has no precondition. The same is not true for the methods pop() and peak(), which assumes that the queue has at least one element. If the queue is empty, the methods throws a NoSuchElementException. The following is a interface definition of generic Queue interface :
Creating a Queue Collection Class :
In Section 14.1, we developed the ALStack class, which implements the Stack interface by composition. An ArrayList object is the underlying storage structure with methods that correspond to those in the interface. We use the same approach with the LinkedQueue class. In this interface, a LinkedList is the storage structure. The collection has methods getFirst() and removeFirst() that efficiently access and delete the front of the sequence. These operations provide a simple implementation of the queue peek() and pop() methods. A linked list also has the method add(), which efficiently inserts an element at the back of the sequence. We will use this to implement the queue push() operation.
The declaration of the LinkedQueue class implements the Queue interface using a private LinkedList reference variable qList and composition. The constructor creates an empty queue by initializing qList as an empty list. Below is the implementation :
Application: Scheduling Queue :
Let us look at one of the main applications of a queue, namely, a process or task scheduler. An executive secretary for a personnel director schedules a series of job interviews for applications seeking a position. The secretary uses a queue to store the starting times for the interviews. Also because the office closes at 5:00 P.M., and the last appointment begins at 16:30(4:30 P.M.), the last appointment lasts at most 30 minutes. Throughout the day, the director begins each interview by popping the queue and then calling peek() to identify the time for the next view. The information enables the director to determine the amount of time available for the interview :
This message was edited 2 times. Last update was at 11/10/2010 11:44:03
沒有留言:
張貼留言