Stack Data Structure

Intro

Stack is a special type of data structure. The order in a Stack is LIFO (First In First Out) which means the element we added last will be first removed from the stack.

In the stack, the elements are added and removed on the same end - called top of the stack:

Stack support operations like push (add element), pop (remove the element), and peek (retrieve or fetch the first element of the Stack or the element present at the top of the Stack).

Implementing Stack from scratch in Java

We can implement a Stack data structure in two ways: using an array and using a Linked List as a backed data structure.

Implementing Stack using an array

Let's create a Stack class

public class Stack<T> {

  public T[] array;
  public int size = 0;
  public int capacity;

  public Stack() {
    this(5);
  }

  public Stack(int capacity) {
    this.capacity = capacity;
    array = (T[]) new Object[capacity];
  }

}

While initializing the stack, we need to initialize the array behind the scene with a default value if not provided.

Method for pushing the element:

public void push(T data) {
  if(size >= capacity) {
    throw new RuntimeException("The stack is full!");
  }

  array[size++] = data;
}

Method for removing the element from the top of the stack:

public T pop() {
  if (size == 0) {
    throw new RuntimeException("The stack is empty!");
  }

  T element = array[array.length - 1];
  array[array.length - 1] = null;
  --size;

  return element;
}

Take a peek at the last added element:

public T peek() {
  if (size == 0) {
    throw new RuntimeException("The stack is empty!");
  }

  return array[array.length - 1];
}

Here is the complete Stack class:

public class Stack<T> {

  private T[] array;
  private int size = 0;
  private int capacity;

  public Stack() {
    this(5);
  }

  public Stack(int capacity) {
    this.capacity = capacity;
    array = (T[]) new Object[capacity];
  }

  public void push(T data) {
    if (size >= capacity) {
      throw new RuntimeException("The stack is full!");
    }

    array[size++] = data;
  }

  public T pop() {
    if (size == 0) {
      throw new RuntimeException("The stack is empty!");
    }

    T element = array[array.length - 1];
    array[array.length - 1] = null;
    --size;

    return element;
  }

  public T peek() {
    if (size == 0) {
      throw new RuntimeException("The stack is empty!");
    }

    return array[array.length - 1];
  }

  public void show() {
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
  }
}

Implementing Stack using Linked List

Now, let's see how we can create a stack that has a Linked List as a backed data structure.

public class LStack<T> {
  public Node<T> top;
  public int size;

}

class Node<T> {
  public T data;
  public Node<T> next;
}

Method for pushing the element to the stack:

public class LStack<T> {
  public Node<T> top;
  public int size;

  public void push(T data) {
    Node<T> newNode = new Node<>(data);

    newNode.next = top;
    top = newNode;
    size++;
  }

In the stack, the top element (element that is last added) points to the element that is added before it, and so on... - that is the direction of pointers in the Stack data structure - from the top to the bottom.

Method for removing the element from the top of the stack:

public T pop() {
  if (top == null) {
    throw new NoSuchElementException("The stack is empty!");
  }

  T data = top.data;
  top = top.next;
  size--;

  return data;
}

The peek() method:

public T peek() {
  if (top == null) {
    throw new NoSuchElementException("The stack is empty!");
  }
  return top.data;
}

The complete LStack class:

public class LStack<T> {
  public Node<T> top;
  public int size;

  public void push(T data) {
    Node<T> newNode = new Node<>(data);

    newNode.next = top;
    top = newNode;
    size++;
  }

  public T pop() {
    if (top == null) {
      throw new NoSuchElementException("The stack is empty!");
    }

    T data = top.data;
    top = top.next;
    size--;

    return data;
  }


  public T peek() {
    if (top == null) {
      throw new NoSuchElementException("The stack is empty!");
    }
    return top.data;
  }

}

class Node<T> {
  public T data;
  public Node<T> next;
}

Bonus: Stack with a dynamic array

Here is the complete Stack class where we used a dynamic array as a backed data structure:

// Stack using dynamic size array
public class DStack<T> {

  int size = 0;
  int capacity;
  T[] arr;

  public DStack() {
    this(5);
  }

  @SuppressWarnings("unchecked")
  public DStack(int capacity) {
    this.capacity = capacity;
    arr = (T[]) new Object[capacity];
  }

  public void push(T data) { // O(1)
    if (size >= capacity) {
      expandArray();
    }
    arr[size++] = data;
  }

  public T pop() { // O(1)
    if (size == 0) {
      throw new RuntimeException("Underflow error. Stack is empty.");
    }

    T data = arr[size - 1];
    arr[size - 1] = null;
    --size;

    shrink();

    return data;
  }

  public T peek() { // O(1)
    if (size == 0) {
      throw new RuntimeException("Underflow error. Stack is empty");
    }

    return arr[size - 1];
  }

  public boolean isEmpty() { // O(1)
    return size == 0;
  }

  public int size() { // O(1)
    return size;
  }

  public void show() {
    for (T t : arr) {
      System.out.println(t);
    }
  }

  private void expandArray() {
    capacity *= 2;
    T[] newArray = (T[]) new Object[capacity];
    System.arraycopy(arr, 0, newArray, 0, size());
    arr = newArray;
  }

  public void shrink() {
    int length = size;

    if (length <= (capacity / 2) / 2) {
      length = capacity / 2;
      T[] newArray = (T[]) new Object[length];
      System.arraycopy(arr, 0, newArray, 0, size());
      arr = newArray;
    }
  }

}

Stack data structure - analysis

The time complexity of all three operations (push, pop, peek) is O(1) since we are not iterating over the elements, we just visit the top node - the node we added last.