Data Structures and Algorithms Java

Java 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

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.

Stack Complexity Analysis

  • 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
 * Web: https://codinghelpline.org
 */
public class Node {
   
    private int data;
    private Node next;      // this is reference to next node object
   
    public Node() {
        data = 0;
        next = null;
    }
   
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
   
    public int getData() {
        return this.data;
    }
   
    public void setData(int data) {
        this.data = data;
    }
   
    public void setNext(Node next) {
        this.next = next;
    }
   
    public Node getNext() {
        return this.next;
    }
}

LinkedStack.java

/**
 * Implementation of Linked Stack.
 *
  * @author CodingHelpLine
 * Web: https://codinghelpline.org
 */
public class LinkedStack {
   
    // top of stack
    private Node top;   // store linked nodes of data
    private int count; // count the elements in stack
   
    // Initialize Empty Stack with this Constructor
    public LinkedStack() {
        top = null;
        count = 0;
    }
   
    // Push an element on top of the Stack
    public void push(int val) {
       
        // we create new node
        Node node = new Node(val);
       
        // if it is empty stack
        if(this.isEmpty()) {
            top = node;
            count++;
        } else {
           
            // node->next = top
            // top = node
           
            node.setNext(top);
            top = node;
            count++;
        }
    }
   
    // Pop an element from top of the Stack
    public int pop() {
       
        if(this.isEmpty()) {
            System.out.println("Stack is Empty");
            return -1;
        }
       
        // assign next node to top
        int element = top.getData();
        top = top.getNext();
        count--;
       
        return element;
    }
   
    //  Peak Top element of the Stack.
    public int peek() {
        if(!this.isEmpty()) {
            return top.getData();
        }
       
        throw new IllegalArgumentException("Stack is Empty");
    }
   
    // Check if Stack is empty
    public boolean isEmpty() {
        return top == null;
    }
   
    // Get the Size of Stack
    public int size() {
        return count;
    }
   
    // Print the Stack to the Standard output
    public void print() {
       
        if(this.isEmpty()) {
            System.out.println("Stack is Empty");
            return;
        }
       
        // Print stack
        Node current = top;
       
        while(current != null) {
            System.out.printf("%-10d", current.getData());
            current = current.getNext();
        }
       
        System.out.println("");
    }
}

LinkedStackTest.java

import java.util.Random;

/**
 * Test the Stack Implementation.
 *
  * @author CodingHelpLine
 * Web: https://codinghelpline.org
 */
public class LinkedStackTest {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
       
        // Create Stack
        LinkedStack stack = new LinkedStack();
       
        // Random object
        Random random = new Random();
       
        // add new Elements
        System.out.println("Testing push Function:");
        for(int i=0; i<5; i++) {
            int x = random.nextInt(100);
            System.out.printf("Pushing %d on top of Stack%n", x);
            stack.push(x);
            System.out.printf("Stack Size is: %d%n", stack.size());
            System.out.printf("Top element of Stack: %d%n", stack.peek());
            System.out.println("Current Stack is:");
            stack.print();
            System.out.println("\n");
        }
       
        // Pop Elements from stack
        System.out.println("Testing Pop Function: ");
        while(!stack.isEmpty()) {
            System.out.printf("Stack Size is: %d%n", stack.size());
            System.out.printf("Top element of Stack: %d%n", stack.peek());
           
            int x = stack.pop();
            System.out.printf("%d removed from top of Stack%n", x);
            System.out.println("Current Stack is:");
            stack.print();
            System.out.println("\n");
        }
    }
   
}
Views: 19

Leave a Reply

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