[ Data Structures with Java ] Section 15.3 : A Bounded Queue

Preface :
The general description of a queue assumes that the list can grow without bounds. The LinkedQueue class in Section 15.1 corresponds to this view. The underlying LinkeList storage class allow a queue to grow as necessary, and so there is no queue-full condition. For some applications, however, entiries might have to reside in a memory area of fixed size.
In this section, we will introduce a bounded-queue class called BQueue. The class uses a finite array as the underlying storage structure. A user may use a default constructor to set the fixed size at 50. A second constructor allows the users to pass the size as an argument. The BQueue class implements the Queue interface and adds the method full(), which returns a boolean value indicating the array is full. If a program attempts to add an element to a full queue, push() throws an IndexOutOfBoundsException.

The BQueue Class - Design
The BQueue uses a fixed-length array of generic type to store the elements. The array, called queueArray, uses a set of private integer variables that locate elements in the queue and maintain the size and fixed-length capacity of the queue. The variable qfront is an index that references the front of the queue, and the variable qback is the location at which a new element enters the queue. The variables qcount and qcapacity maintain the current size of the queue and the size of the storage array respectively. The nondefault constructor initializes the variables using the user specified size; the default constructor calls this constructor with size=50.
The implementation of the BQueue class involves a circular array model for storing elements in the queue. We illustrate the model by using a queue withqcapacity=4 elements. Assume that the queue already contains three elements. The index qfront identifies the first element in the queue, and the index qbackidentifies that location at which the next insertion occurs.
Actually, we can use a new way to view the queue in this case. Think of the queue as a circular sequence with a series of slots that allow elements to enter in a clockwise fashion. The exit point for an element is the slot designated by qfront, and the entry point for a new element occurs at the slot identifies byqback. Let us retrace the activity in our four element queue, assuming the circular storage model in below figure :


In the circular model, element E can enter the queue at location qback. Note that qback is now the position that was formerly occupied by A. While the circular model is a good abstract view of how items enter and leave a queue, our implementation of the BQueue class must deal with the array, which stores elements sequentially. Treating the array as a circular sequence involves updating qfront and qback to cycle back to the front of the array as soon as they move past the end of the array (index = qcapacity). Below figure illustrate how E would be added to the queue at the front of the array. Not that qback has a value that is less than qfront. This can be a little disconcerting, even counterintuitive, given our familiar linear view of a queue. Do not let this bother you; the circularity will be handled in the implementation of the class.


The BQueue Class - Implementation
In the BQueue class, the operation push() and pop() have complexity O(1), because each method simply access the array at one of the indices qfront orqback. Below is the implementation :

- BQueue.java :

view plaincopy to clipboardprint?

1. package DSwJ.S15;  
2.   
3. public class BQueue implements Queue{  
4.     private T[] queueArray;  
5.     private int qfront,qback;  
6.     private int qcapacity, qcount;  
7.       
8.     public BQueue(){  
9.         this(50);  
10.     }  
11.   
12.     public BQueue(int size) {  
13.         qfront = 0;   
14.         qback = 0;  
15.         qcapacity = size;  
16.         qcount = 0;  
17.         queueArray = (T[])new Object[qcapacity];  
18.     }  
19.       
20.     @Override  
21.     public boolean isEmpty() {  
22.         if(qcount==0) return true;  
23.         return false;  
24.     }  
25.   
26.     public boolean full(){  
27.         if(qcount==qcapacity) return true;  
28.         return false;  
29.     }  
30.       
31.     @Override  
32.     public T peek() {  
33.         if(isEmpty()) return null;  
34.         return queueArray[qfront];  
35.     }  
36.   
37.     @Override  
38.     public T pop() {  
39.         if(isEmpty()) return null;  
40.         int index = qfront;  
41.         qcount--;         
42.         qfront = (qfront+1)%qcapacity;  
43.         return queueArray[index];  
44.     }  
45.   
46.     @Override  
47.     public void push(T item) {  
48.         if(!full()) {  
49.             qcount++;  
50.             queueArray[qback] = item;  
51.             qback = (qback+1)%qcapacity;  
52.         } else throw new IndexOutBoundsException("Queue is full already!!!");  
53.     }  
54.   
55.     @Override  
56.     public int size() {       
57.         return qcount;  
58.     }  
59.   
60.     public static void main(String args[]) {  
61.         BQueue q = new BQueue(4);  
62.         q.push("Red");  
63.         q.push("Blue");  
64.         q.push("Green");  
65.         q.push("Black");  
66.         while(!q.isEmpty()){  
67.             System.out.print(q.pop()+" ");  
68.         }  
69.     }  
70. }  

Run:
Red Blue Green Black

Supplement :
* [ 資料結構 小學堂 ] 佇列 : 佇列的應用 (環狀佇列)

This message was edited 1 time. Last update was at 15/10/2010 16:21:38