1. Introduction

A Stack is a Last In First Out (LIFO) data structure. The primary operations associated with a stack are push (adding an item) and pop (removing the most recently added item). While arrays can be used to implement stacks, using a linked list can offer some benefits in terms of dynamic size adjustments. In this blog post, we will implement a stack using a linked list in Java.

2. Program Steps

1. Define a Node class that will represent each element in the linked list.

2. Create a Stack class that uses the Node class to store elements.

3. Implement the following primary stack operations:

– push: Add an element to the top of the stack.

– pop: Remove and return the top element from the stack.

– peek: View the top element without removing it.

– isEmpty: Check if the stack is empty.

4. Test the stack operations in the main function.

3. Code Program

class Stack<T> {

    private Node<T> top;

    private static class Node<T> {
        private T data;
        private Node<T> next;

        Node(T data) {
            this.data = data;
        }
    }

    public void push(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = top;
        top = newNode;
    }

    public T pop() {
        if (top == null) {
            System.out.println("Stack is empty. Cannot pop.");
            return null;
        }
        T item = top.data;
        top = top.next;
        return item;
    }

    public T peek() {
        if (top == null) {
            System.out.println("Stack is empty. Nothing to peek.");
            return null;
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("Top element: " + stack.peek());
        System.out.println("Popped element: " + stack.pop());
        System.out.println("Is stack empty? " + stack.isEmpty());
    }
}

Output:

Top element: 30
Popped element: 30
Is stack empty? false

4. Step By Step Explanation

1. We define a Node class that holds the data of the node and a reference to the next node.

2. The Stack class maintains a top reference, which always points to the topmost element in the stack.

3. In the push method, a new node is created and added to the top of the stack.

4. The pop method removes the top node and returns its data. It also updates the top reference to the next node.

5. The peek method allows us to see the data of the topmost element without removing it.

6. The isEmpty method checks if the stack has any nodes or not.

7. In the main function, we demonstrate the functionality of the Stack by pushing three integers, peeking the topmost one, popping it, and finally checking if the stack is empty.