In this post I would be discussing Array and Linked List based implementation of a Stack in Java along with the proper provision for overflow and underflow conditions. Wikipedia defines a Stack as follows:

Stack

In computer science, a stack is a particular kind of abstract data type or collection in which the principal (or only) operations on the collection are the addition of an entity to the collection, known as push and removal of an entity, known as pop. The relation between the push and pop operations is such that the stack is a Last-In-First-Out (LIFO) data structure. In a LIFO data structure, the last element added to the structure must be the first one to be removed. This is equivalent to the requirement that, considered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack. Often a peek or top operation is also implemented, returning the value of the top element without removing it.

A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept an entity to be pushed, the stack is then considered to be in an overflow state. The pop operation removes an item from the top of the stack. A pop either reveals previously concealed items or results in an empty stack, but, if the stack is empty, it goes into underflow state, which means no items are present in stack to be removed.

A stack is a restricted data structure, because only a small number of operations are performed on it. The nature of the pop and push operations also means that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition. Therefore, the lower elements are those that have been on the stack the longest.

In Java, a stack can be implemented using an array or as a linked list representation using reference variables and objects. Array based arrays are good for conceptual clarity but unlike linked list implementation they are not truly dynamic because the size of an array must be declared at the time of creation/memory allocation. Once created an array can neither shrink nor expand and hence, is not dynamic in true sense of the word. In linked list representation the nodes are allocated/unallocated as and when the need arises and are truly dynamic, however, there is some memory overhead due to the use of reference variables. Please note that in real life scenarios the number of data items in each node is usually more than one and thus, the overheads are not significant.

Handling of overflow and underflow conditions

This is one of those topics where I prefer my own implementation over the implementation given in most textbooks. The reason being that most textbooks for ISC do not use exception handling for signalling overflow and underflow conditions even though exception handling is in the ISC syllabus. I do not subscribe to the idea of displaying a message on the console when overflow or underflow condition is encountered because in that case the programmer who is using the methods ( that is push( ) or pop( ) methods ) has no control over the flow of control once the abnormal condition occurs. Stacks are used as a means to an end and is not an end in itself. It should be obvious, that once the memory is used up or there are no nodes left when the user is trying to pop a node, there is no point in continuously displaying error messages which are displayed on the screen. The code segment using the push or pop methods cannot see the messages!

The process of creating custom exceptions for overflow and underflow is neither complex nor cumbersome. I would be creating two exception classes for the purpose of this post, one for overflow and the other for underflow exception by the name OverflowException and UnderflowException respectively.

In order to create an exception one needs to create a class and extend it from either Exception class or RuntimeException class. When we extend from Exception class out exception is a checked exception meaning that we must catch ( use try…catch block) or declare that an exception can be thrown (use throws where the methods are being used). When we extend from RuntimeException, the exception is an unchecked exception meaning there is no need to use try-catch block or use throws.

Let us understand the distinction between extending from Exception or RuntimeException  with the help of something which everyone probably know. When we use readLine() method of BufferedReader class we either use try-catch or declare the enclosing function as throws IOException- the underlying idea is that IOException is a checked exception. The compiler would check that we are doing something to handle the exception. When we are using the division operator, an exception ArithmeticException may be thrown, if the divisor is zero; but we never use try-catch or throws for the same because it’s an unchecked exception. Now, I would be using RuntimeException in this post primarily to decrease code clutter and keep things simple. Overflow and underflow classes would be as follows:

class OverflowException extends RuntimeException{
    public OverflowException(){
        super("Overflow exception. No memory left");
    }
}
class UnderflowException extends RuntimeException{
    public UnderflowException(){
        super( "Underflow exception. No nodes left" );
    }
}

For our purpose, the above code would be functional even if we remove the highlighted lines. The purpose of the constructor is to pass the message ( “Overflow exception. No memory left” or “Underflow exception. No nodes left” ) to the base class constructor so that it can be displayed if and when the exception is thrown. Students are advised to run the code once after removing the highlighted code to see the effect. When we need to throw an exception, we would create an object of the required class and throw it using the keyword throw.

Array based implementation of a stack in Java

An array based implementation of a stack in Java is as follows:

class Stack{
    int data[], top;
    public Stack(){
        data = new int[ 10 ];
        top = -1;
    }
    public Stack( int size ){
        if( size <= 0 ) 
            throw new IllegalArgumentException();
        data = new int[ size ];
        top = -1;
    }
    public boolean isEmpty(){
        return top == -1;
    }
    public void push( int data ){
        if( top == this.data.length-1 ){
            throw new OverflowException();
        }else{
            this.data[ ++top ] = data;
        }
    }
    public int pop(){
        if( isEmpty() ){
            throw new UnderflowException();
        }else{
            return data[top--];
        }
    }
}
class OverflowException extends RuntimeException{
    public OverflowException(){
        super("Overflow exception. No memory left");
    }
}
class UnderflowException extends RuntimeException{
    public UnderflowException(){
        super( "Underflow exception. No nodes left" );
    }
}
class StackTest{
    public static void main( String args[] ){
        Stack s =new Stack();
        for( int i = 1 ; i <= 10; i++ ){
            s.push(i);
        }
        while(!s.isEmpty( )){
            System.out.println( s.pop( ) );
        }
    }
}

In the above program we are using the array data to store the node data and the integer variable top to hold the index position of the current top in the array. There are two constructors, the default constructor would allocate an array of size 10 and the parametrized constructor would accept a size at the time of instantiation of the Stack object.

We are throwing an IllegalException in case the value is negative or zero as it arrays can only have positive size. The value of top is initialized to -1 in the beginning, since array index of an array starts from 0, the value of -1 would indicate empty stack.

The value of top would increase on push operation and decrease on pop operation. If the value of top exceed the maximum subscript value (data.length-1) of the data array overflow would result and if pop operation is attempted when the stack is empty (top =1) then underflow would occur.

The main function simply pushes values from 1 to 10 and then pops out element one by one till the stack is not empty. The output of all integers from 10 to 1 would indicate that the Stack is functioning properly.

 Linked List  based implementation of a stack in Java

A Linked List based implementation of a stack in Java is as follows:

class Stack{
    class Node{
        int data;
        Node next;
        public Node( int data ){
            this.data = data;
            next = null;
        }
    }
    private Node top;
    public Stack(){
        top = null;
    }
    public boolean isEmpty(){
        return top == null;
    }
    public void push( int data ){
        try{
            Node temp = new Node( data );
            temp.next = top;
            top = temp;
        }catch( OutOfMemoryError e ){
            top = null;
            throw new OverflowException();
        }
    }
    public int pop(){
        if( isEmpty() ){
            throw new UnderflowException();
        }
        int data = top.data;
        top = top.next;
        return data;
    }
}
class OverflowException extends RuntimeException{
    public OverflowException(){
        super("Overflow exception. No memory left");
    }
}
class UnderflowException extends RuntimeException{
    public UnderflowException(){
        super( "Underflow exception. No nodes left" );
    }
}
class StackTest{
    public static void main( String args[] ){
        Stack s =new Stack();
        for( int i = 1 ; i <= 10; i++ ){
            s.push(i);
        }
        while(!s.isEmpty( )){
            System.out.println( s.pop( ) );
        }
    }
}

In the above program the class Node is modelling a node and encapsulates the two parts of the node-the data part and the next part. The initialization of node is done through the Node constructor. Since the creation of node is always followed by storing of the node value I have used a constructor instead of a dedicated function for storing data in the node.

The data member top which is a reference variable holds the reference of the last node added. If the value of top is null it means that the stack is empty.

The push function deserves some explanation particularly the exception handling part. When we allocate memory using the operator new there is possibility that it would fail if there is no heap memory left. In that case JVM would throw OutOfMemoryError. This is actually our overflow condition. Notice that in the catch block we are assigning top to null. This is important because when all memory is exhausted we cannot do anything, not even display a message because println() function also requires some memory to execute. Now, since all the memory is exhausted it is obvious that we cannot continue. We must free some memory so that we can recover from memory crises and take some alternative action. As soon as we assign null to top. The block of memory which top was referring to would be eligible for garbage collection. This implies that JVM would free that block of memory. As soon as this happens there would be no one referring to the second node now because the next part of the fist node is now gone. Thus, the memory allocated to the second node would also be free. This would go on till all the memory occupied by all the nodes is free.

The underflow condition is pretty straight forward and occurs when we try to remove a node from an empty stack.

The main function simply pushes values from 1 to 10 and then pops out element one by one till the stack is not empty. The output of all integers from 10 to 1 would indicate that the Stack is functioning properly.

Creating the underflow condition

Underflow condition can easily be created by modifying the main function of the StackTest as follows:

class StackTest{
    public static void main( String args[] ){
        Stack s = new Stack();
        System.out.println( s.pop( ) );
    }
}

Creating the overflow condition

Overflow condition can be created by modifying the main function of the StackTest as follows:

class StackTest{
    public static void main( String args[] ){
        Stack s = new Stack();
        while(true){
                s.push( 1 );
        }
    }
}

The above code would repeteadly add new nodes till all the memory is exhausted and would eventually lead to overflow condition.