程式扎記: [ Data Structures with Java ] Section 15.1 : The Queue Interface

標籤

2011年2月26日 星期六

[ Data Structures with Java ] Section 15.1 : The Queue Interface


The Queue Interface :
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 :
- Queue.java :
  1. package DSwJ.S15;  
  2.   
  3. public interface Queue {  
  4.     public T pop();  
  5.     public void push(T item);  
  6.     public boolean isEmpty();  
  7.     public int size();  
  8.     public T peek();  
  9. }  

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 :
- LinkedQueue.java :
  1. package DSwJ.S15;  
  2.   
  3. import java.util.LinkedList;  
  4.   
  5. public class LinkedQueue implements Queue{  
  6.     private LinkedList qList;  
  7.       
  8.     public LinkedQueue(){  
  9.         qList = new LinkedList();  
  10.     }  
  11.   
  12.     @Override  
  13.     public boolean isEmpty() {        
  14.         return qList.isEmpty();  
  15.     }  
  16.   
  17.     @Override  
  18.     public T peek() {         
  19.         return qList.peekFirst();  
  20.     }  
  21.   
  22.     @Override  
  23.     public T pop() {          
  24.         if(!isEmpty()) return qList.removeFirst();  
  25.         throw new NoSuchElementException("Empty Queue!!!");  
  26.     }  
  27.   
  28.     @Override  
  29.     public void push(T item) {  
  30.         qList.addLast(item);  
  31.     }  
  32.   
  33.     @Override  
  34.     public int size() {       
  35.         return qList.size();  
  36.     }  
  37. }  

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 :
- Demonstration code :
  1. public static void prog15_1(){  
  2.     Time24 offTime = new Time24(17,0);  
  3.     LinkedQueue taskSchr = new LinkedQueue();  
  4.     taskSchr.push(new Time24(10,0));  
  5.     taskSchr.push(new Time24(11,15));  
  6.     taskSchr.push(new Time24(13,0));  
  7.     taskSchr.push(new Time24(13,45));  
  8.     taskSchr.push(new Time24(14,30));  
  9.     taskSchr.push(new Time24(15,30));  
  10.     taskSchr.push(new Time24(16,30));  
  11.     Time24 taskTime = taskSchr.pop(),nextTask;  
  12.     while(true) {  
  13.         nextTask = taskSchr.peek();  
  14.         if(nextTask!=null) {  
  15.             System.out.println("Task("+taskTime.toString()+") has Time "+taskTime.interval(nextTask)+".");  
  16.         } else {  
  17.             System.out.println("Task("+taskTime.toString()+") has Time "+taskTime.interval(offTime)+".");  
  18.         }  
  19.         if(!taskSchr.isEmpty())  
  20.             taskTime = taskSchr.pop();  
  21.         else  
  22.             break;  
  23.     }  
  24. }  

Run:
Task(10:00) has Time 1:15.
Task(11:15) has Time 1:45.
Task(13:00) has Time 0:45.
Task(13:45) has Time 0:45.
Task(14:30) has Time 1:00.
Task(15:30) has Time 1:00.
Task(16:30) has Time 0:30.
This message was edited 2 times. Last update was at 11/10/2010 11:44:03

沒有留言:

張貼留言

網誌存檔