Generics and the Stack

[chili5]

Generics

Using generics allows you to define classes that can work with any defined type. This is very similar to the use of templates in C++.

When you use collections like the vector and the stack you do not have to do any typecasting to get the correct value. This ensures that you cannot make silly errors with getting items from a collection. Without generics we had to use typecasting to get the correct data out of structures. The other problem is we are going to have problems if try to add the wrong data type. Generics ensure that we use the right data type and that we do not have any typecasting to do.

If we use the wrong data type then the program will not compile.

Example:

Vector<Integer> v = new Vector<Integer>();

The vector is a class that uses generics. The above line declares a vector that can only function on integer objects. If we try to add a String object we will get an error.

Try this:

v.add("james");

When I do this I get a message that says:

cannot find symbol
symbol: method add(java.lang.String)
location: class java.util.Vector<java.util.Integer>;

This occurs because when I created the Vector it was compiled in a way that it can only use Integers. Anything else crashes at compilation. So if you use the wrong data type you will get an error at compile time instead of running time. Making it easier to find your error.

Creating generic classes

We can make our own generic classes. To do this we are going to make our own Stack class it is going to be a very simple Stack. If you don't know, the Stack is a structure that has restricted access. You can only access the top item of the Stack. The stack provides a first-in, last-out order meaning you can only access the top item of the stack. See my tutorial here: Stacks to see more information on the stack. Are stack class is only going to push items onto the stack and remove items from the stack. Our stack will use a Vector as the underlying structure so it will be able to resize. Note that we cannot use an array as the underlying structure?

Why? This is because generic classes are compiled at runtime and the parameters are replaced with the appropriate type. However, arrays are initalized with a type at declaration and thus they cannot be generic. So our underlying structure will be a vector.

Creating a stack is really easy. All we need is a member variable that keeps track of the index of the top item. We store all the items in a private vector but only provide a method that can access the top item of the stack. The use of the private keyword in front of the Vector is what makes this structure possible. If we didn't include it then we would just be creating a wrapper of the Vector and what is the purpose of that?


Creating the stack

To define that our stack is generic we use angle brackets after the class name and in those brackets we place the names of different parameters. These parameters will define what type of data the stack holds.

So the class skeleton looks like this:

public class Stack<E> {
	
}

Now what instance members do we need? We need a vector, and a counter for the index of the top. That is all. The vector will be of type E indicating that it holds a user defined data type and the index variable will be an integer set to -1.

So add these just after the class declaration.

private Vector<E> stack; // holds the contents of the stack
private int top; // the index of the top item in the stack. -1 indicates empty.

Now to declare the constructor.

public Stack() {
	this.stack = new Vector<Integer>();
	this.top = -1;
}

We create a new Vector that is empty, this is going to hold the stack. We will initalize the top variable to -1 which indicates that the stack is empty.

Now the next two methods we will define are push and pop. The push method adds an item to the top of the stack and the pop method removes an item from the stack and returns it. The push method:

public void push(E obj) {
    stack.add(obj);
    top++;
}

We use the add method in the vector to add the parameter to the stack. The parameter is of type E which will be replaced with the type defined by the programmer when it is used. We increase the top variable by 1 so we have the index of the top item stored.

The pop method is very similar to this, it returns type E and returns the item at the top of the stack. However we have to remove this item from the stack so we need to store it in a temporary variable.

We can't just do

return stack.get(top);

Why? We have to do two other things, decrease the top variable by 1 so it points to the new top of the stack. We also have to remove the item from the Vector. If we don't we will run into problems if we add a new item later. We will see this item again which is not what we want. The problem with this I illustrated in my tutorial about Vectors. We have to copy the vector contents into a new array every time we erase the end item. This can take a really long time for big stacks. We will only remove an item from the Stack if it is not empty. The pop method returns null if the stack is empty.

So the pop method looks like this:

public E pop() {
	if (top == -1) {
        return null; // stack is empty
    }
     E temp = stack.get(top);
     stack.remove(top);
     top--;
     return temp;
}

This covers everything the Stack needs to do but it might be useful to define two methods that check if the stack is empty and how many items are in the stack. The stack is empty if top = -1. So the empty method looks like this:

public boolean isEmpty(){
        return top == -1;
}

The number of items in the stack then is top+1. If the stack is empty (top = -1) and the number of items is 0.

public int size() {
        return top+1;
}

So the full class looks like this:

import java.util.Vector;


public class Stack<E> {
    private Vector<E> stack;
    private int top = -1; // index of the top item of the stack

    public Stack() {
        stack = new Vector<E>();
    }

    public void push(E obj) {
        stack.add(obj);
        top++;
    }

    public E pop() {
        if (top == -1) {
            return null; // stack is empty
        }
        E temp = stack.get(top);
        stack.remove(top);
        top--;
        return temp;
    }

    public boolean isEmpty(){
        return top == -1;
    }

    public int size() {
        return top+1;
    }
}

Now to test this class you can use this code:

public class generics {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Stack<Integer> st = new Stack<Integer>();

        st.push(5);
        st.push(4);
        st.push(3);
        st.push(9);

        if (st.size() == 0) {
            System.out.println("Stack is empty.");
        } else {
            System.out.println("Stack contains " + st.size() + " items.");
        }

        while (!st.isEmpty()) {
            System.out.println(st.pop());
        }

        if (st.size() == 0) {
            System.out.println("Stack is empty.");
        } else {
            System.out.println("Stack contains " + st.size() + " items.");
        }
        st.push(7);

        System.out.println("Size: " + st.size());
        System.out.println(st.pop());
        
    }

}

Notice how in the angle brackets I have included Integer? This means that the stack can only hold integer objects. Next we add 4 items to the stack. If you run the code you will notice that the items are outputted in reverse order. This is how the stack works. Now notice how the size method works. If displays how many items are in the stack.

We can note that st.size() == 0 is the same as isEmpty.

Now the Java programmers can enjoy the same comfort that the C++ programmers enjoy with templates. The major difference beginning with generics the code is only compiled once unlike in C++ when the function is compiled once for each data type that is being used.

Enjoy!

[WingedPanther]

Just a note: in C++ the equivalent to generics is templates. One thing I always find odd is that Java doesn't allow generics to contain primitives, but C++ does.

[Turk4n]

Wow, this one is my favorite tutorial !
Great job chili5 !
rep+

[Jordan]

Another great tutorial by Chili5! +rep
Keep it up!

[bloodchains]

Just to let you know, when I'm making the initialization for the Vector in the constructor:

this.stack = new Vector<Integer>();

I'm getting this error on NetBeans:

incompatible types
  required: java.util.Vector<E>
  found:    java.util.Vector<java.lang.Integer>

Obsolete Collection

Don't I need to initialize it as Vector<E> instead of Vector<Integer>? Also, it looks like we can also use ArrayList instead of Vector, since NetBeans tells me that Vector is an obsolete collection.