Uipoka’s Weblog

Archive for the ‘Data Structures’ Category

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

Stack Implementation Using Java

with 2 comments

Stack
Stack is an abstract data type and data structure based on the principle of Last In First Out (LIFO). Stacks are used in the basic design of an operating system for interrupt handling and operating system function calls. Stacks are used to run a Java Virtual Machine. The stack is ubiquitous.
First i write an interface for implementing stack:

public interface Stacks {
	void push(Object x);
	void pop();
	Object top();
	Object topAndPop();
	boolean isEmpty();
	void makeEmpty();
}

Now look at the RishanStack class which implements the interface stacks


public class RishanStack implements Stacks{

	private static final int DEFAULT_CAPACITY = 10;
	private Object [] theArray; 
	private int topOfStack;
	
    public RishanStack() {
    	theArray = new Object[DEFAULT_CAPACITY];
    	topOfStack = -1;	
    }
    
    public boolean isEmpty(){
    	return topOfStack == -1;
    }
    
    public void makeEmpty(){
    	topOfStack = -1;	
    }
    
    public void push(Object x){
    	if(theArray.length==topOfStack+1)increaseSize();
    	theArray[++topOfStack]=x;
    }
    
    public Object top(){
    	if(isEmpty())throw new RishanStackException("Stack top");
    	return theArray[topOfStack];
    }
    
    public void pop(){
    	if(isEmpty())throw new RishanStackException("Stack pop");
    	topOfStack--;
    }
    
    public Object topAndPop(){
    	if(isEmpty())throw new RishanStackException("Stack top and pop");
    	return theArray[topOfStack--];
    }
    
    public void status(){
    	for(int i=0;i<theArray.length;i++){
    		System.out.println(theArray&#91;i&#93;);
    	}
    }
    
    public void increaseSize(){
    	Object &#91;&#93; dummy = new Object&#91;theArray.length*2&#93;;
    	for(int i=0;i<theArray.length;i++){
    		dummy&#91;i&#93;=theArray&#91;i&#93;;
    	}
    	theArray = dummy;
    }
}
&#91;/sourcecode&#93;

And lastly the RishanStackException class which extends <em>java.io.RuntimeException</em>
and overridden constructor:

public class RishanStackException extends RuntimeException{
    public RishanStackException(String msg) {
    	super(msg);
    }
}

Written by uipoka

August 13, 2008 at 7:18 pm