Monday, October 26, 2009

Stack Implementation in Java

Below is my code to implement Stack from ground-up. I tried (in a very short time) to emulate the behavior of Stack in the Java Util package. The methods I have written are:
size()
get(int index)
empty()
clear()
pop()
push(Object input)
bottom()
top()


I call my Stack implementation as CustomStack as it may evolve over time. I have also provided some test cases to validate that the implementation actually works. The sample output is shown below the codes.

import java.lang.reflect.Array;

public class CustomStack {

private Object[] stackElements;
private int stackIndex = -1;
private int stackSize = 0;
private static final int INIT_SIZE = 3;
private boolean stackSizeGiven = false;
private int sizeHolder = 0;

public CustomStack(){
stackElements = new Object[ INIT_SIZE ];
stackSizeGiven = false;
}

public CustomStack(int inputSize){
sizeHolder = inputSize;
stackElements = new Object[ sizeHolder ];
stackSizeGiven = true;
}

public int size(){
return stackSize;
}

public Object get(int index){
if ((index < 0) || (index > (stackSize))) {
throw new RuntimeException("Index out of bound. Supplied " + index);
}
return stackElements[ index ];
}

public boolean empty() {
return stackIndex == -1;
}

public void clear() {
if (stackSizeGiven) {
stackElements = new Object[ sizeHolder ];
} else {
stackElements = new Object[ INIT_SIZE ];
}
stackIndex = -1;
stackSize = 0;
}

public void pop() {
if(empty()){
throw new RuntimeException( "Stack is already empty. No elements to pop." );
}
stackIndex--;
stackSize--;
}

public void push(Object input) {
if( stackIndex + 1 == stackElements.length ) {
int arrayLength = Array.getLength(stackElements);
Object [] newArray = (Object[]) Array.newInstance(stackElements.getClass().getComponentType(), (arrayLength + arrayLength ));
System.arraycopy(stackElements, 0, newArray, 0, arrayLength);
stackElements = newArray;
}
stackElements[ ++stackIndex ] = input;
stackSize++;
}

public Object bottom(){
if(empty())
throw new RuntimeException( "Stack is already empty. No elements at bottom." );
return stackElements[ 0 ];
}

public Object top() {
if(empty())
throw new RuntimeException( "Stack is already empty. No elements at top." );
return stackElements[ stackIndex ];
}

public static void testCases(){
CustomStack aStack = new CustomStack();
System.out.println("Stack is empty: " + aStack.empty());
aStack.push("Nicholas Key");
aStack.push(3.142);
aStack.push(false);
// Prints false
System.out.println("Element at top of Stack: " + aStack.top());
System.out.println("Size of current Stack: " + aStack.size());

aStack.push("Java Developer");
aStack.push("Android App Developer");
// Prints Android App Developer
System.out.println("Element at top of Stack: " + aStack.top());

aStack.push("Web App Developer");
aStack.push("Blogger");
aStack.push(2009);
// Prints 2009
System.out.println("Element at top of Stack: " + aStack.top());
System.out.println("Size of current Stack: " + aStack.size());

// Prints Stack elements
for (int i= 0; i< aStack.size(); i++) {
System.out.println("Index " + i + ": " + aStack.get(i));
}

// Pops 2009
aStack.pop();
// Prints Blogger
System.out.println("Element at top of Stack: " + aStack.top());

// Pops Blogger
aStack.pop();
// Prints Web App Developer
System.out.println("Element at top of Stack: " + aStack.top());

// Prints Stack elements
for (int i= 0; i< aStack.size(); i++) {
System.out.println("Index " + i + ": " + aStack.get(i));
}

System.out.println("Element at bottom of Stack: " + aStack.bottom());

// Pops out all Stack elements
aStack.clear();
System.out.println("Stack is empty: " + aStack.empty());

System.out.println(aStack.get(1));

System.out.println(aStack.get(aStack.size() + 300));
}

public static void main(String[] args) {
testCases();
}
}

Stack is empty: true
Element at top of Stack: false
Size of current Stack: 3
Element at top of Stack: Android App Developer
Element at top of Stack: 2009
Size of current Stack: 8
Index 0: Nicholas Key
Index 1: 3.142
Index 2: false
Index 3: Java Developer
Index 4: Android App Developer
Index 5: Web App Developer
Index 6: Blogger
Index 7: 2009
Element at top of Stack: Blogger
Element at top of Stack: Web App Developer
Index 0: Nicholas Key
Index 1: 3.142
Index 2: false
Index 3: Java Developer
Index 4: Android App Developer
Index 5: Web App Developer
Element at bottom of Stack: Nicholas Key
Stack is empty: true
Exception in thread "main" java.lang.RuntimeException: Index out of bound. Supplied 1
at CustomStack.get(CustomStack.java:29)
at CustomStack.testCases(CustomStack.java:128)
at CustomStack.main(CustomStack.java:136)
Update: I've added several methods to make my CustomStack more robust ;) Click here to look at the improvements.

2 comments:

  1. Grateful readers of your blog demand this class to be named as NtKeyStack in appreciation of the hard work been done.

    Please!

    ReplyDelete
  2. thank you for your suggestion, budchee :)
    i'll modify the class name soon.

    ReplyDelete