Java Data Structures - Contents
A D V E R T I S E M E N T
A queue is a FIFO (First In, First Out) structure.
Anything that's inserted first, will be the first to leave (kind of like the real world
queues.) This is totally the opposite of what a stack is. Although that is true, the queue
implementation is quite similar to the stack one. It also involves pointers to specific
places inside the array.
With a queue, we need to maintain two pointers, the start
and the end. We'll determine when the queue is empty if start
and end point to the same element. To determine if the queue is full (since
it's an array), we'll have a boolean variable named full. To
insert, we'll add one to the start, and mod (the % operator)
with the size of the array. To remove, we'll add one to the end, and mod (the
% operator) with the size of the array. Simple? Well, lets write it.
public class pArrayQueue{
protected Object[] array;
protected int start,end;
protected boolean full;
public pArrayQueue(int maxsize){
array = new Object[maxsize];
start = end = 0;
full = false;
}
public boolean isEmpty(){
return ((start == end) && !full);
}
public void insert(Object o){
if(!full)
array[start = (++start % array.length)] = o;
if(start == end)
full = true;
}
public Object remove(){
if(full)
full = false;
else if(isEmpty())
return null;
return array[end = (++end % array.length)];
}
}
Well, that's the queue class. In it, we have four
variables, the array, the start and end, and a boolean
full. The constructor pArrayQueue(int maxsize) initializes the queue,
and allocates an array for data storage. The isEmpty() method is
self explanatory, it checks to see if start and end are equal;
this can only be in two situations: when the queue is empty, and when the queue is full.
It later checks the full variable and returns whether this queue is empty or
not.
The insert(Object) method, accepts an Object
as a parameter, checks whether the queue is not full, and inserts it. The
insert works by adding one to start, and doing a mod with array.length
(the size of the array), the resulting location is set to the incoming
object. We later check to see if this insertion caused the queue to become full, if yes,
we note this by setting the full variable to true.
The Object remove() method, doesn't
accept any parameters, and returns an Object. It first checks to see if the
queue is full, if it is, it sets full to false
(since it will not be full after this removal). If it's not full,
it checks if the queue is empty, by calling isEmpty(). If it is, the method
returns a null, indicating that there's been an error. This is usually a
pretty bad bug inside a program, for it to try to remove something from an empty queue,
so, you might want to do something more drastic in such a situation (like an exception
throw). The method continues by removing the end object from the queue. The removal is
done in the same way insertion was done. By adding one to the end, and later
mod it with array.length (array size), and that position is
returned.
There are other implementations of the same thing, a
little re-arrangement can make several if() statements disappear. The reason
it's like this is because it's pretty easy to think of it. Upon insertion, you add one to start
and mod, and upon removal, you add one to end and mod... easy?
Well, now that we know how it works, lets actually
test it! I've modified that pretty cool test driver from the stack example, and got it
ready for this queue, so, here it comes:
import java.io.*;
import pArrayQueue;
class pArrayQueueTest{
public static void main(String[] args){
pArrayQueue q = new pArrayQueue(10);
Integer j = null;
int i;
System.out.println("starting...");
for(i=0;i<10;i++){
j = new Integer((int)(Math.random() * 100));
q.insert(j);
System.out.println("insert: " + j);
}
while(!q.isEmpty()){
System.out.println("remove: " + ((Integer)q.remove()));
}
System.out.println("Done ;-)");
}
}
As you can see, it inserts ten random java.lang.Integer
Objects onto the queue, and later prints them out. The output from the program
follows:
starting...
insert: 3
insert: 70
insert: 5
insert: 17
insert: 26
insert: 79
insert: 12
insert: 44
insert: 25
insert: 27
remove: 3
remove: 70
remove: 5
remove: 17
remove: 26
remove: 79
remove: 12
remove: 44
remove: 25
remove: 27
Done ;-)
I suggest you compare this output to the one from
stack. It's almost completely different. I guess that's it for this array implementation
of this FIFO data structure. And now, onto something more complex...
Back to Table of Contents
A D V E R T I S E M E N T
|
Subscribe to SourceCodesWorld - Techies Talk |
|
Add to Favorites
Make Home Page
