How To Implement A Generic Stack Data Structure In Java

Java is a statically typed language, it requires the user to define the type of the data before declaring the variable (Oracle). Thus, a programmer who may not know about generics, will end up re-writing the same class multiply times to create an object of integer, double and string in order to meet an application’s requirement. Therefore, it is important to have a good knowledge of generics in Java. Languages such as JavaScript or Python allow users to define the variable without defining the data type. As a result, a programmer can use the same class with different data types. However, Java is not that flexible, but the need for a flexibility in variable declaration and datatypes has led Java developers to create the generic object, which almost behaves similar to non-statically typed languages. In this tutorial, we use a generic stack class and data structure to illustrate the benefit of using generics.

A Generic Class can be written once, but used multiple times, which is the principle of Don’t Repeat Yourself (DRY). Let’s review the following generic and non-generic classes.

public class Car<T> {
String model;
int vinNumber;
T serialCode;
T weight;

public Car(String model, int vinNumber, T serialCode, T weight) {
this.model = model;
this.vinNumber = vinNumber;
this.serialCode = serialCode;
this.weight = weight;
}
public String toString() {
return "Model: " + model + ", Vin Number: " + ", Serial Code: " + serialCode + ", Weight: " + weight;
}

//Main method to test the object
public static void main(String[] args) {
Car<Integer> sedan = new Car<>("Camry", 293393934, 102929383, 8938822);
Car<String> truck = new Car<>("F150", 38038282, "A39384224", "3004.5943");

System.out.println("Sedan: " + sedan); //sedan.toString() will be invoked inside the print
System.out.println("Truck: " + truck.toString());
}
}

https://raw.githubusercontent.com/menhaj007/genericStack/main/Car.java

public class Car1 {
String model;
int vinNumber;
int serialCode;
int weight;

public Car1(String model, int vinNumber, int serialCode, int weight) {
this.model = model;
this.vinNumber = vinNumber;
this.serialCode = serialCode;
this.weight = weight;
}
public String toString() {
return "Model: " + model + ", Vin Number: " + ", Serial Code: " + serialCode + ", Weight: " + weight;
}

//Main method to test the object
public static void main(String[] args) {
Car1 sedan = new Car1("Camry", 293393934, 102929383, 8938822);
// Car1 truck = new Car1("F150", 38038282, "A39384224", "3004.5943");

System.out.println("Sedan: " + sedan); //sedan.toString() will be invoked inside the print
// System.out.println("Truck: " + truck.toString());
}
}

https://raw.githubusercontent.com/menhaj007/genericStack/main/Car1.java

public class ZipCode<code, city> {
code areaCode;
city cityName;

public ZipCode(code areaCode, city cityName) {
this.areaCode = areaCode;
this.cityName = cityName;
}
public String toString() {
return "Zip code: " + areaCode + ", City name: " + cityName;
}

public static void main(String[] args) {
ZipCode<Integer, String> alexandria = new ZipCode<>(22304, "Alexandria");
ZipCode<Integer, String> fairfax = new ZipCode<>(22030, "Fairfax");
System.out.println(alexandria);
System.out.println(fairfax);
ZipCode<Long, String> Himalaya = new ZipCode<>(33939932223L, "Himalaya");
System.out.println(Himalaya);

}
}

https://raw.githubusercontent.com/menhaj007/genericStack/main/ZipCode.java

To instantiate a generic Java class, add <T>or <E> or any other preferred word or letter next to the class name. For example, public class Car<T>, public class Queue<E> or public class Tree<Node>.

Let’s compare the above two samples /(links) classes:

There are two key differences in the above examples. The first difference is that a generic class needs to be instantiated with Object Wrappers such as <Integer>, <Double>, <String>. The other difference is that multiple instances of the same class can be created with different datatypes in the main method. On the other hand, in class Car1’s variable type must be defined before creating an instance of it. There will be a need for a new class if the datatype for serialCode and weight needs to be changed. Thus, a generic class can save both time and space when used efficiently.

Note: A user can define generic class with multiple key and value pairs such as HashMap. For instance, public class Zipcode<code, cityName>.

public class ZipCode<code, city> {
code areaCode;
city cityName;

public ZipCode(code areaCode, city cityName) {
this.areaCode = areaCode;
this.cityName = cityName;
}
public String toString() {
return "Zip code: " + areaCode + ", City name: " + cityName;
}

public static void main(String[] args) {
ZipCode<Integer, String> alexandria = new ZipCode<>(22304, "Alexandria");
ZipCode<Integer, String> fairfax = new ZipCode<>(22030, "Fairfax");
System.out.println(alexandria);
System.out.println(fairfax);
ZipCode<Long, String> Himalaya = new ZipCode<>(33939932223L, "Himalaya");
System.out.println(Himalaya);

}
}

https://raw.githubusercontent.com/menhaj007/genericStack/main/ZipCode.java

In order to allow a number longer than integer’s capacity, all it needed was to replace <Integer, String> with <Long, String>.

Let’s review the Stack Data Structure before implementation. A stack is a Last in First Out (LIFO) data structure (Wikipedia). This means when a programmer decides to design a stack data structure, he/she implements at least the following methods or algorithms:

pop(), push(), top(), isFull(), isEmpty() and size(). One of the commonly used data structures in a stack is array object. In Java, the size and data type of an array must be defined at the time of instantiation. Otherwise, it will throw error. Let’s compare JavaScript’s array and Java’s Array.

JavaScript: let myArray = []

Java: int[] myArray = new int[10],
or
data-type[] variable = new data-type[size]

By looking at Java’s array implementation, it is clear that if a programmer needs to create an array of string, then he/she must redo the whole work, unless generic object is used. In general, datatypes must be statically typed before declaring the variables.

If a programmer doesn’t use a generic datatype for implementing a stack data structure, and if the need for having multiple types of the stack or other classes rise, then the programmer has to create multiples of similar stacks or classes.

The followings are sample implementation of integer stack, string stack and generic stacks:

Stack Data Structure
public class IntStack {
private int[] data;
private int topIndexLocation;

public IntStack(int defaultCapacity) {
data = new int[defaultCapacity]; //instantiating the stack array.
topIndexLocation = -1;
// Initially, the top-index position points outside of the array.
// When the push method is called, the topIndexLocation gets incremented first such
// as -1 + 1 =0, will give the first index then the new value will be added.
//topIndexLocation = 0; // This an alternative to setting index to -1. If you chose
// to start from 0, then the value at data[0] will be inserted first,
// then the topIndexLocation get incremented.
}
public boolean isEmpty() {
return (topIndexLocation == -1);
// This compares topIndexLocation against -1 and returns either true or false.
// Below is the alternative of way of writing line 16
//if (topIndexLocation == -1) {
//return true;
//} else {
// return false;
//}
}
public boolean isFull() {
return (topIndexLocation == data.length-1);
}

public void push(int value) {
if (!isFull()) {
topIndexLocation++;
// Notice, the topIndexLocation is -1. Adding -1 + 1 = 0.
// Therefore topIndexLocation must become 0 for the first value to be inserted
// System.out.println(topIndexLocation + " at location " + value);
// add print statement to see result
data[topIndexLocation] = value;
} else { // This is not necessary, but adding it will help you to see the error
throw new IndexOutOfBoundsException("Stack is full");
}
//if (!isFull()) data[++topIndexLocation] = value;
// if you prefer one line. Since this is a void method you don't need the else condition
}
public void pop() {
if (!isEmpty()) {
topIndexLocation--;
// This is equivalent to topIndexLocation = (topIndexLocation - 1);
} else {
throw new IndexOutOfBoundsException("Stack is empty");
}
}
//second version, you can use pop to return data too.
//public int pop() {
// if (!isEmpty()) {
// int valueToBeRemove = data[topIndexLocation];
// data[topIndexLocation] = 0; // int not is not object.
// topIndexLocation--;
// return valueToBeRemove;
// } else {
// throw new IndexOutOfBoundsException("Stack is empty");
// }
//}
public int top() {
if (isEmpty()) throw new IndexOutOfBoundsException("Stack is empty, no top value exist");
return data[topIndexLocation];
}
public int size() {
return topIndexLocation+1;
// Since the topIndexLocation is set to -1, and it increments with the index numbers,
// in order to get data.lengthy, we will add 1. Ex. The last array index location is
// data.length-1, but to get the data.length.
//Thus, topIndexLocation match the indices of the array, but when the size is required,
// then topIndexLocation +1 will give a size which counts from 1 up to the inserted elements.
}
}

https://raw.githubusercontent.com/menhaj007/genericStack/main/IntStack.java

public class StringStack {
private String[] data;
private int topIndexLocation;


public StringStack(int defaultCapacity) {
data = new String[defaultCapacity];
}
public boolean isEmpty() {
return (topIndexLocation == -1);
//if (topIndexLocation == -1) {
// return false;
// } else {
// return true;
//}
}
public boolean isFull() {
return (topIndexLocation == data.length-1);
// if (topIndexLocation == data.length -1) {
// return true;
// } else {
// return false;
// }
}

public void push(String value) {
if (!isFull()) {
topIndexLocation++;
data[topIndexLocation] = value;
} else {
throw new IndexOutOfBoundsException("Stack is full");
}
// if (!isFull()) data[++topIndexLocation] = value ;
}
public void pop() {
if (!isEmpty()) {
data[topIndexLocation] = null;
topIndexLocation--;
} else {
throw new IndexOutOfBoundsException("Stack is empty");
}
}
//second version, you can use pop to return data too.
// public T pop() {
// if (!isEmpty()) {
// T valueToBeRemove = data[topIndexLocation];
// data[topIndexLocation] = null;
// topIndexLocation--;
// return valueToBeRemove;
// } else {
// return null;
// }
// }
public String top() {
if (isEmpty()) return null;
return data[topIndexLocation];
}
public int size() {
return topIndexLocation+1;
}

}

https://raw.githubusercontent.com/menhaj007/genericStack/main/StringStack.java

public class Stack<T> {
private T[] data;
private int topIndexLocation;

@SuppressWarnings("uncheck")
public Stack(int defaultCapacity) {
data = (T[]) new Object[defaultCapacity];
topIndexLocation = -1;
}
public boolean isEmpty() {
return (topIndexLocation == -1);
// if (topIndexLocation == -1) {
// return false;
// } else {
// return true;
// }
}
public boolean isFull() {
return (topIndexLocation == data.length-1);
// if (topIndexLocation == data.length -1) { // topIndexLocation equals to the index of the last element
// return true;
// } else {
// return false;
// }
}

public void push(T value) {
if (!isFull()) {
topIndexLocation++;
data[topIndexLocation] = value;
} else { // This is not necessary, but adding it will help you to see the error
throw new IndexOutOfBoundsException("Stack is full");
}
//if (!isFull()) data[++topIndexLocation] = value ;//if you prefer one line.
// Since this is a void method you don't need the else condition
}
public void pop() {
if (!isEmpty()) {
data[topIndexLocation] = null;
topIndexLocation--;
} else {
throw new IndexOutOfBoundsException("Stack is empty");
}
}
//second version, you can use pop to return data too.
//public T pop() {
// if (!isEmpty()) {
// T valueToBeRemove = data[topIndexLocation];
// data[topIndexLocation] = null;
// topIndexLocation--;
// return valueToBeRemove;
// } else {
// return null;
// }
//}
public T top() {
if (isEmpty()) return null;
return data[topIndexLocation];
}
public int size() {
return topIndexLocation+1;
}

}

https://raw.githubusercontent.com/menhaj007/genericStack/main/Stack.java

public class Main {
public static void main(String[] args) {
Stack<Integer> intStack = new Stack<>(3);
intStack.push(199);
intStack.push(200);

System.out.println(intStack.size());

System.out.println(intStack.top());
intStack.pop();
System.out.println(intStack.top());
intStack.pop();


intStack.push(200);
intStack.pop();
intStack.pop();
intStack.pop();
intStack.push(500);
System.out.println(intStack.isEmpty());
System.out.println(intStack.isFull());
System.out.println(intStack.top());
System.out.println(intStack.isFull() + ", isEmpty " + intStack.isEmpty());
System.out.println(intStack.top());
intStack.pop();
intStack.pop();
intStack.pop();
System.out.println(intStack.isEmpty());

Stack<String> stringStack = new Stack<>(4);
stringStack.push("Hello world");
System.out.println(stringStack.size());
// stringStack.pop();
System.out.println(stringStack.size());
System.out.println(stringStack.isEmpty());
StringStack st = new StringStack(1);
st.push("Hello world");
System.out.println(st.isFull());
System.out.println(st.top());
System.out.println(st.isEmpty());
System.out.println(st.top());
st.pop();


Stack<Integer> numberStack = new Stack<>(3);
Stack<String> stringStack1 = new Stack<>(6);
Stack<Double> doubleStack = new Stack<>(100);
//By using a generic stack, we eliminated the need for IntStack and StringStack class.
}
}

https://raw.githubusercontent.com/menhaj007/genericStack/main/Main.java

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store