Generics

Let’s start to broaden the implementation of stacks and queues to different data types as an example what if we want StackOfUrls, StackOfInts, StackOfVans? How would we approach these scenarios. We could attempt to implement a separate stack class for each type however we start to repeat ourselves in code and maintaining our classes will become tedious and error-prone.

A modern approach to avoiding having multiple implementations of data ensures we are not stuck in the above predicament.

Casting

Lets take a StackOfStrings which we have already implemented, in this scenario we might also want to implement StackOfUrls, StackOfInts, StackOfVans. Casting allows for us to reuse the code already implemented in StackOfStrings for different data types. As an example.

StackOfObjects s = new StackOfObjects();
Apple a = new Apple();
Orange b = new Orange();
s.push(a);
s.push(b);

One thing to note, casting is error prone in particular if we have type mismatches during run time. As an example the below code will result in a runtime error.

a = (Apple) (s.pop());

Casting is considered an unsatisfactory solution as it relies on the run time errors being presented by the client during runtime.

Generics

Generics allow for us to discover mistakes in typed mismatch at compile-time instead of run-time. Generics allow for us to have a type parameter associated with our class (using angle brackets <> )

Stack<Apple> s = new Stack<Apple>();
Apple a = new Apple();
Orange b = new Orange();
s.push(a);
s.push(b); //Compile-time error.
a = s.pop();

The guiding principle in good modular programming is: Welcome compile-time errors; avoid run-time errors.

Generic Stack: Linked-List implementation

public class Stack<Item>
{
  private Node first = null;

  private class Node
  {
    Item item;
    Node next;
  }

  public boolean isEmpty()
  { return first == null; }

  public void push(Item item)
  {
    Node oldfirst = first;
    first = new Node();
    first.item = item;
    first.next = oldfirst;
  }

  public Item pop()
  {
    Item item = first.item;
    first = first.next;
    return item;
  }

}

Here we took our earlier implementation of LinkedStackOfStrings and refactored it to be a generic implementation using <Item> as it’s generic type name. We can now handle multiple types of data with the same implementation.

Generic Stack: Array Implementation

Lets try to apply the same principle to our array implementation.

public class FixedCapacityStack<Item>{
  private Item[] s;
  private int N = 0;

  public FixedCapacityStack(int capacity)
  {
    //THE BELOW LINE OF CODE IS LIMITED IN JAVA
    s = new Item[capacity];
  }

  public boolean isEmpty()
  { return N == 0; }

  public void push(Item item)
  { s[N++] = item; }

  public Item pop()
  { return s[--N]; }
}

It’s important to note here - most programming languages will hit a limitation here when it comes to creating a generic array. The above code whilst correct in theory will also encounter this limitation due to Java not allowing the creation of generic arrays.

And here is where our original approach and new approach will collide. By casting the type of our generic array we ensure we work within the limitations of our language (in this case type erasure) whilst maintaining the overall nature of our generic stack.

public FixedCapacityStack(int capacity){
  s = (Item[]) new Object[capacity];
}

Generic Data Types: Autoboxing

As Java datatypes are based on primitive and reference types sometimes we would need to apply a generic methodology to primitives. Here we would look to wrappers. Every primitive type has a wrapper object type as an example an Integer is a wrapper type for int. Autoboxing is the process of applying an automatic cast between a primitive type and its wrapper.

Stack<Integer> s = new Stack<Integer>();
s.push(17);
int a = s.pop()