Data Structures and Algorithms Highly Recommended Java

Java Generic Linked Stack Tutorial

August 14, 2023
codinghelpline

Introduction

Stack is a famous linear data structure that uses LIFO (Last In, First Out) or FILO (First In, Last Out) order of operations for the Push and Pop. Stack is mainly used in memory organization, Redo or Undo Command management tools, Back Tracking, Web Browser history, Checking balancing of brackets and different algorithms, for example, Infix to Postfix expression conversions

Generic Programming

Java included support for writing generic classes in J2SE 5.0 or JDK1.5 version. The generics framework allows us to define a class in terms of a set of parameters that can be used as the type of declared variables, parameters, and return types. Before Java SE 5, generic programming was heavily dependent upon the Java Object class that is the root of the hierarchy in Java Programming Language.

Example

public class MyClass<T> {
    T data;
}

This is a generic class that can be instantiated with any Class type such as Integer, String, Double, etc.

Methods

  • Push(): Push an element at Top of the stack.
  • Pop(): Pop or remove an element from the top of the stack.
  • Peek(): Look at the top element of the Stack.
  • isEmpty(): Check if the Stack is Empty
  • Print(): Print the Stack to see its State.
  • Size(): Total Number of elements stored in the Stack.

Time Complexity

  • Push(): The complexity of push function is O(1) if stored at the beginning of the list. The complexity is O(N) if the element is stored at the end of the List.
  • Pop(): The complexity of the pop function is O(1) if removed from the beginning of the List. In case removed from the end Complexity will be O(N) or you have to add another pointer for the Tail nail to achieve O(1)
  • Peek(): If stored at the front of the list, peek is O(1). If stored at the end of the List, Peek complexity is O(N), or add another pointer (Tail) to achieve O(1) Complexity.
  • Space complexity: O(N) N is the number of elements in the Stack.

Node.java

/**
 * Node Class
 *
 * @author CodingHelpLine
 * Website: https://codinghelpline.org
 */
public class Node<T> {
   
    // Data fields
    private T data;
    private Node<T> top;
   
    public Node(T data) {
        this.data = data;
        this.top = null;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getTop() {
        return top;
    }

    public void setTop(Node<T> top) {
        this.top = top;
    }
}

Stack.java

/**
 * Implementation of the Generic Linked Stack.
 *
 * @author CodingHelpLine
 * Website: https://codinghelpline.org
 */
public class Stack<T> {
   
    // top of the Stack
    private Node<T> top;
   
    // count of elements
    private int count;
   
    /**
     * Create Empty Stack.
     */
    public Stack() {
        this.top = null;
        this.count = 0;
    }
   
    /**
     * Function to push an element on top of the Stack.
     *
     * @param data
     */
    public void push(T data) {
       
        Node<T> node = new Node(data);
       
        // check if stack is empty
        if(this.isEmpty()) {
            top = node;
        } else {
            node.setTop(top);
            top = node;
        }
        count++;
    }
   
    /**
     * Remove the Top element and return it.
     *
     * @return top element
     */
    public T pop() {
       
        // first check if empty
        if(this.isEmpty()) {
            System.out.println("The Stack is empty");
            return null;
        }
       
        T data = top.getData();
        top = top.getTop();
        count--;
        return data;
    }
   
    /**
     * Peek the top element of the Stack
     *
     * @return top element
     */
    public T peek() {
        return top.getData();
    }
   
    /**
     * Check if the Stack is empty.
     *
     * @return indicate empty stack
     */
    public boolean isEmpty() {
        return this.top == null;
    }
   
    /**
     * The number of elements
     *
     * @return number of elements
     */
    public int size() {
        return count;
    }
   
    /**
     * Print the Stack to console screen.
     */
    public void print() {
       
        // if empty
        if(this.isEmpty()) {
            System.out.println("The Stack is empty");
            return;
        }
       
        // current node
        Node<T> current = top;
       
        System.out.printf("[%s", current.getData().toString());
       
        current = current.getTop();
       
        while(current != null) {
            System.out.printf(", %s", current.getData().toString());
            current = current.getTop();
        }
       
        System.out.println("]");
    }
}

GenericLinkedStackTest.java

/**
 * Test Class to test the functionality of
 * Generic Linked Stack.
 *
 * @author CodingHelpLine
 * Website: https://codinghelpline.org
 */
public class GenericLinkedStackTest {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
       
        // Integer stack
        Stack<Integer> intStack = new Stack<>();
       
        // Insert few elements
        intStack.push(2);           // [2]
        intStack.print();
        intStack.push(9);           // [9, 2]
        intStack.print();
        intStack.push(13);           // [13, 9, 2]
        intStack.print();
        intStack.push(7);           // [7, 13, 9, 2]
        intStack.print();
        intStack.push(19);           // [19, 7, 13, 9, 2]
        intStack.print();
       
        System.out.println("Test Pop()");
        while(!intStack.isEmpty()) {
            System.out.printf("Top Element Removed: %s%n", intStack.pop());
            intStack.print();
        }
       
    }
   
}
Views: 5

Leave a Reply

Your email address will not be published. Required fields are marked *