Add to Favorites    Make Home Page 7560 Online  
 Language Categories  
 Our Services  

Java Data Structures - Contents


Array Queues...

A D V E R T I S E M E N T

Search Projects & Source Codes:

    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




Google Groups Subscribe to SourceCodesWorld - Techies Talk
Email:

Free eBook - Interview Questions: Get over 1,000 Interview Questions in an eBook for free when you join JobsAssist. Just click on the button below to join JobsAssist and you will immediately receive the Free eBook with thousands of Interview Questions in an ebook when you join.

 Advertisements  

Google Search

Google

is a part of Vyom Network.

Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Interview Questions | Jobs, Discussions | Placement Papers | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | Arabic, French, German | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Software Testing | Google Logo Maker | Freshers Jobs

Sitemap | Privacy Policy | Terms and Conditions
Copyright ©2003-2018 SourceCodesWorld.com, All Rights Reserved.
Page URL: /articles/java/java-data-structures/Array_Queue.asp


Download Yahoo Messenger | Placement Papers | Free SMS | C Interview Questions | C++ Interview Questions | Quick2Host Review