1. Introduction

A stack is a data structure that supports Last-In-First-Out (LIFO) semantics. The primary operations associated with a stack are push, which adds an element to the top, and pop, which removes the top element. While stacks can be implemented using arrays, doing so with linked lists provides dynamic sizing. In this blog post, we will implement a stack using a singly linked list in Java.

2. Program Steps

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

2. Implement the Stack class, which will contain the primary stack operations: push, pop, peek, and isEmpty.

3. The push operation will insert an element at the beginning (head) of the linked list.

4. The pop operation will remove and return the element at the beginning (head) of the linked list.

5. The peek operation will return the element at the beginning (head) without removing it.

6. The isEmpty operation will check if the stack (linked list) is empty.

3. Code Program

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class Stack {
    Node top;

    // Constructor
    public Stack() {
        this.top = null;
    }

    // Push operation
    public void push(int value) {
        Node newNode = new Node(value);
        if (top == null) {
            top = newNode;
        } else {
            newNode.next = top;
            top = newNode;
        }
    }

    // Pop operation
    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return -1;
        }
        int value = top.data;
        top = top.next;
        return value;
    }

    // Peek operation
    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return -1;
        }
        return top.data;
    }

    // Check if stack is empty
    public boolean isEmpty() {
        return top == null;
    }
}

public class StackDemo {
    public static void main(String[] args) {
        Stack 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("Top element after pop: " + stack.peek());
    }
}

Output:

Top element: 30
Popped element: 30
Top element after pop: 20

4. Step By Step Explanation

1. The Node class represents each element in our singly linked list. It contains data (an integer in this case) and a reference to the next node.

2. The Stack class contains the main logic for our stack operations.

– The push operation creates a new node with the given value and adds it to the top (beginning) of our linked list.

– The pop operation removes the top element and adjusts the top pointer accordingly. It also returns the data of the removed node.

– The peek operation simply returns the data of the top element without removing it.

– The isEmpty function checks if our stack is empty by seeing if the top pointer is null.

3. In the StackDemo class, we demonstrate the usage of our stack by pushing some values, peeking the top value, popping a value, and then peeking again.