How to implement Stack in java / Custom Stack implementation in java using different methods

What is Stack ?

A linear data structure which stores newly added items at its top and retrieves newly added items from its top. Consider a pile of books where each new book added to the pile is placed at its top and at the time of removal, the book at the top is removed. A stack works on LIFO (Last In First Out) principle and supports only two operations :

1. push – An item is added to the stack. As stated before, the newly added item is always placed at its top.
2. pop – Removing an item from the stack. Every pop operation returns the item at the top of the stack. The item popped out is removed from the stack when this operation is performed.

Why Custom Implementation ?

Java provides the stack data structure implementation in the form of class java.util.Stackwhich also provides push and pop operations. Question arises as why a custom implementation is needed. There are a couple of answers to this question.

1. There are some application requirements where you want a functionality which is not provided by the language classes. In that case you are forced to change the requirements according to language support. It is thus, always better to have your own implementation so that you can modify it as per requirement.
2. This type of scenarios are usually asked in interviews to test the logic of the candidate.

Custom Stack implementation

Designing a custom data structure implies that its user should not be aware about its internal details but should only be able to see the operations supported by it. Now let’s discuss ways to implement custom stack. There are two methods which are as below :

Method 1 : Using Array

This method uses array as the data structure which holds stack data. There would be only two public methods push and pop which define Stack for the user.

import java.util.Arrays;

public class Stack {

	private int currentElementPosition = 0;
	private Object[] elements;
	private int INITIAL_SIZE = 10;

	/**
	 * Constructor which initializes the array to be used as the stack
	 */
	public Stack() {
		elements = new Object[INITIAL_SIZE];
	}

	/**
	 * Pop operation which retrieves topmost element from the stack
	 * 
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public T pop() {
		// retrieve top most element
		T t = (T) elements[--currentElementPosition];
		// empty its position
		elements[currentElementPosition] = null;
		return t;
	}

	/**
	 * Push operation which adds item to the stack
	 * 
	 * @param elementToPush
	 */
	public void push(T elementToPush) {
		// check if array is full
		if (currentElementPosition == elements.length) {
			expandSize();
		}
		elements[currentElementPosition++] = elementToPush;
	}

	public int size() {
		return currentElementPosition;
	}

	/**
	 * Increases the size of the array by double its existing size
	 */
	private void expandSize() {
		int increasedSize = elements.length * 2;
		// create a new array with double size and copy existing contents into it
		elements = Arrays.copyOf(elements, increasedSize);
	}
}

Details :

Create a generic class which has two public methods – push and pop. The class contains following fields :

1. Object [] elements – An object array which is the backing data structure and holds the stack elements.
2. int currentElementPosition – An integer which acts as a pointer to the current stack position. It is always equal to the number of elements in the stack and 1 greater than the topmost array index occupied by an element. For Example, if its value is 5 means there are 5 elements in the stack and the index of topmost element is 4.
3. int INITIAL_SIZE – Denotes the size with which the array is created when the stack is initialized.

 

Following is the explanation of the supported operations :

1. Push – When a push operation is performed, first the size of array is checked to ensure that there is space to add a new elements. If not, the size of array is increased to double its present size. This is done by creating a new array of double capacity and copying all the existing elements into it. When the size check is complete, the new element is added to the top of the array and  counter variable is incremented.
2. Pop – Element at index equal to the value of field currentElementPosition – 1 is retrieved and returned since at any time this field contains the total number of elements in the stack and its value -1 points to the topmost element. Finally the topmost place in the stack is set to nullto indicate that it is now empty.

Below is a test program to test our implementation. The stack is created to hold elements of type java.lang.String.

   public static void main(String args[]) {
	System.out.println("Stack using Array");
        System.out.println("----------------------------");
        // Stack is defined to hold only String values
	Stack arrayStack = new Stack();
	System.out.println("Initial Stack size : "+arrayStack.size());
	arrayStack.push("Element One");
	arrayStack.push("Element Two");
	System.out.println("Stack size after push : "+arrayStack.size());
	System.out.println("Topmost element : "+arrayStack.pop());
	System.out.println("Stack size after pop : "+arrayStack.size());
   }

Output is :

Method 2 : Using ArrayList

This method uses a java.util.ArrayListas the backing data structure for the Stack. Since there are already methods available in the java api to add and remove the elements from the arraylist which automatically manage its resizing, we are not required to do so.

import java.util.ArrayList;

public class StackUsingArrayList extends ArrayList {

	public void push(T t){
		add(t);
	}
	
	public T pop(){
		int currentSize = size();
		T t = get(currentSize - 1);
		remove(currentSize-1);
		return t;
	}
}

Detail :

Create a generic class which extends a java.util.ArrayListwhich manages the element management. In the push method, we simply call the add()method of java.util.ArrayListwhich handles insertion logic.

In the pop method, first retrieve the size of the array list which gives the total number of elements in the list. Since java.util.ArrayListstores the elements starting from index 0, the element at position size – 1 gives the top-most element. This method does not require any special logic to handle resizing of the backing data structure as it is handled by the array list itself.

Now let’s test the above implementation with the sample code below. The stack is created to hold elements of type java.lang.Integer.

  public static void main(String args[]) {
	System.out.println("Stack using Array List");
        System.out.println("-----------------------------");
        // stack is defined to hold only integers
        Stack arrayListStack = new Stack();
	System.out.println("Initial Stack size : "+arrayListStack.size());
	arrayListStack.push(10);
	arrayListStack.push(20);
	System.out.println("Stack size after push : "+arrayListStack.size());
	System.out.println("Topmost element : "+arrayListStack.pop());
	System.out.println("Stack size after pop : "+arrayListStack.size());	
  }

Output is :

Let’s tweak in :

1. If creating a custom stack is asked in an interview, then always go with Method 1 as it does not utilize any java Collection classes and involves creating a user defined logic to manage insertion and retrieval of objects.
2. Instead of using java.util.ArrayListany other collection such as java.util.LinkedList, java.util.Vectoretc., can be used in Method 2 as all of them have methods to insert element and retrieve element from any index.
3. Both the above Stack implementation are created to be generic so as to hold elements of any data type.
4. java.util.ArrayListalso uses an Object array to hold its elements.

 

Learnt something from this post ? Great !!! Keep Visiting, Keep Learning….