Uipoka’s Weblog

Dealing with queue

with 3 comments

A queue is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. This makes the queue a First-In-First-Out (FIFO) data structure.Queue is a linear data structure.

Codes:

Interface

public interface InterQueue {
	boolean isEmpty();
    	void enqueue(Object x);
    	Object dequeue();
}

Basic class:

public class RishanQueue {

    public RishanQueue() {
    	theArray = new Object[DEFAULT_CAPACITY];
    	head = 0;
    	tail = 0;
    }
    
    public boolean isEmpty(){
    	return queueSize==0;
    }
    
    public void enqueue(Object x){
    	if(queueSize==theArray.length)throw new RishanException("Enqueue");
    	theArray[tail] = x;
    	queueSize++;
    	if(queueSize<theArray.length && tail+1 == theArray.length){
    		tail = 0;
    	}else tail++;
    }
    
    public Object dequeue(){
    	if(isEmpty())throw new RishanException("Dequeue");
    	Object x = theArray&#91;head&#93;;
    	queueSize--;
    	if(++head==theArray.length)
    		head = 0;
    	return x;
    }
      
    private final int DEFAULT_CAPACITY = 10;
    private int &#91;&#93; theArray;
    private int head=0;
    private int tail=0;
    private int queueSize=0;
    
}
&#91;/sourcecode&#93;

<strong>Exception class:</strong>


public class RishanException extends java.io.RuntimeException {
    public RishanException(String msg) {
        super(msg);
    }
}

In this implementation i used a fixed length of array but if anyone we want to increase out queue size
then we can use following method:

private void doubleQueue( )
{
Object [ ] dummy;
dummy = new Object[ theArray.length * 2 ];
for(int i=0;i

Advertisements

Written by uipoka

August 19, 2008 at 3:24 am

Posted in Data Structures, Java

3 Responses

Subscribe to comments with RSS.

  1. another helpful post.
    thank u man.

    osamajik

    August 19, 2008 at 4:23 pm

  2. Hey, ur codes… It looks finer than mine… Ha ha… how did u do that?… Give me some tips man!!!

    shiman

    August 20, 2008 at 4:03 pm

  3. in enqueue method

    if(queueSize<theArray.length && tail+1 == theArray.length){

    I didn’t understand why (queueSize<theArray.length) this condition is here.
    Please explain.

    Md. Arifuzzaman Arif

    December 25, 2008 at 12:38 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: