Friday, 29 June 2012

Stack implementation in Java

Most of java developers are not really interested to know about the internal implementation of collections framework/data structure implementation. Of-course, I too was not the exceptional, initial days of my programming, I never really bothered about this, however, during last one year I started looking into the internal implementation of collections framework/data structure.

Recently I have taken decision to document all of my work, so that it would be helpful for both me and others who are interested to know.

Now, lets look how we can implement Stack data-structure using java.
Stack data-structure principle: First-In, Last-Out

1. StackEmptyException.java

package ora.stackex;

public class StackEmptyException extends RuntimeException {

    /**
     * serialVersionUID
     */
    private static final long serialVersionUID = 1L;
   
    public StackEmptyException(String message) {
        super(message);
    }

}

2.  StackOverflowException.java 

package ora.stackex;

public class StackOverflowException extends RuntimeException {

    /**
     *
     */
    private static final long serialVersionUID = 1L;
   
    public StackOverflowException(String message) {
        super(message);
    }

}

3. Stack.java

package ora.stackex;

public interface Stack {

    int size();
   
    boolean isEmpty();
   
    Object top() throws StackEmptyException;
   
    void push(Object obj) throws StackOverflowException;
   
    Object pop() throws StackEmptyException;
}


4. StackImpl.java


package ora.stackex;

public class StackImpl implements Stack {

    Object[] stackArr = new Object[10];
    int pos = -1; 
   
    @Override
    public boolean isEmpty() {
        if(pos == -1)
            return true;
        return false;
    }

    @Override
    public Object pop() throws StackEmptyException {
        if (pos == -1) {
            throw new StackEmptyException("Stack is empty");
        }
       
        Object obj = stackArr[pos];
        stackArr[pos] = null;
        pos--;
        return obj;
    }

    @Override
    public void push(Object obj) throws StackOverflowException {
        int npos = pos + 1;
        if (npos == 10)
            throw new StackOverflowException("Stack is full");
        pos = npos;
        stackArr[pos] = obj;       
    }

    @Override
    public int size() {
        return pos+1;
    }

    @Override
    public Object top() throws StackEmptyException {
        if (pos == -1)
            throw new StackEmptyException("Stack is empty");
        Object obj = stackArr[pos];
        return obj;
    }

}


3 comments:

  1. In the isEmpty() method implementation, the condition should be if(pos==-1), instead of if(stackArr.length==0).

    ReplyDelete
    Replies
    1. Thanks for the correction, I have done the changes

      Delete
  2. This is very useful explanation though. Thank you.

    ReplyDelete