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...
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...
0 Komentar untuk "Array Queues"