Custom Stack

About

A stack follows the LIFO (Last In, First Out) principle. The main operations in a stack are:

• Push (Add an element)

• Pop (Remove the top element)

• Peek (View the top element)

• isEmpty (Check if the stack is empty)

There are 2 ways to implement Stack i.e.

1. LinkedList-based Stack (Dynamic size)

2. Array-based Stack (Fixed size)

1. LinkedList-based Stack

Stack Data Structure

Each node contains:

• A data value

• A reference to the next node

Here's the Node class:

class Node<E> {
    E data;
    Node<E> next;

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

Stack Class

The CustomStack class will maintain:

• A top node (points to the last added element)

• The size of the stack

public class CustomStack<E> {
    private Node<E> top;
    private int size;

    public CustomStack() {
        this.top = null;
        this.size = 0;
    }
}

Core Operations

Below are the essential operations for a stack.

Push (Add Element)

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

Pop (Remove and Return the Top Element)

public E pop() {
    if (isEmpty()) throw new RuntimeException("Stack is empty");

    E data = top.data;
    top = top.next;
    size--;
    return data;
}

Peek (View Top Element Without Removing)

public E peek() {
    if (isEmpty()) throw new RuntimeException("Stack is empty");
    return top.data;
}

Check if Stack is Empty

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

Get Stack Size

public int size() {
    return size;
}

Print Stack

public void printStack() {
    Node<E> temp = top;
    while (temp != null) {
        System.out.print(temp.data + " -> ");
        temp = temp.next;
    }
    System.out.println("null");
}

Complete Custom Stack Implementation

public class CustomStack<E> {
    private Node<E> top;
    private int size;

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

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

    public CustomStack() {
        this.top = null;
        this.size = 0;
    }

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

    public E pop() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");

        E data = top.data;
        top = top.next;
        size--;
        return data;
    }

    public E peek() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return top.data;
    }

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

    public int size() {
        return size;
    }

    public void printStack() {
        Node<E> temp = top;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        CustomStack<Integer> stack = new CustomStack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.printStack(); // Output: 30 -> 20 -> 10 -> null

        System.out.println("Top element: " + stack.peek()); // Output: 30
        System.out.println("Popped: " + stack.pop()); // Output: 30
        stack.printStack(); // Output: 20 -> 10 -> null

        System.out.println("Stack size: " + stack.size()); // Output: 2
    }
}

Time Complexity Analysis

Operation	Complexity
Push (push)	O(1)
Pop (pop)	O(1)
Peek (peek)	O(1)
Is Empty (isEmpty)	O(1)
Get Size (size)	O(1)
Print Stack (printStack)	O(n)

2. Array-based Stack

Stack Data Structure

For an array-based stack, we maintain:

• An array to store elements

• A top pointer to track the topmost element

• A size to track the number of elements

Stack Class

public class CustomArrayStack<E> {
    private E[] stack;
    private int top;
    private int capacity;

    public CustomArrayStack(int capacity) {
        this.capacity = capacity;
        this.stack = (E[]) new Object[capacity]; // Generic array creation
        this.top = -1; // Stack is empty initially
    }
}

Core Operations

Push (Add Element)

public void push(E data) {
    if (top == capacity - 1) throw new RuntimeException("Stack Overflow");

    stack[++top] = data;
}

Pop (Remove and Return the Top Element)

public E pop() {
    if (isEmpty()) throw new RuntimeException("Stack is empty");

    E data = stack[top];
    stack[top--] = null; // Prevent memory leak
    return data;
}

Peek (View Top Element Without Removing)

public E peek() {
    if (isEmpty()) throw new RuntimeException("Stack is empty");
    return stack[top];
}

Check if Stack is Empty

public boolean isEmpty() {
    return top == -1;
}

Get Stack Size

public int size() {
    return top + 1;
}

Print Stack

public void printStack() {
    for (int i = top; i >= 0; i--) {
        System.out.print(stack[i] + " -> ");
    }
    System.out.println("null");
}

Complete Custom Stack Implementation

public class CustomArrayStack<E> {
    private E[] stack;
    private int top;
    private int capacity;

    @SuppressWarnings("unchecked")
    public CustomArrayStack(int capacity) {
        this.capacity = capacity;
        this.stack = (E[]) new Object[capacity];
        this.top = -1;
    }

    public void push(E data) {
        if (top == capacity - 1) throw new RuntimeException("Stack Overflow");
        stack[++top] = data;
    }

    public E pop() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");

        E data = stack[top];
        stack[top--] = null; // Avoid memory leak
        return data;
    }

    public E peek() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return stack[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public int size() {
        return top + 1;
    }

    public void printStack() {
        for (int i = top; i >= 0; i--) {
            System.out.print(stack[i] + " -> ");
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        CustomArrayStack<Integer> stack = new CustomArrayStack<>(5);
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.printStack(); // Output: 30 -> 20 -> 10 -> null

        System.out.println("Top element: " + stack.peek()); // Output: 30
        System.out.println("Popped: " + stack.pop()); // Output: 30
        stack.printStack(); // Output: 20 -> 10 -> null

        System.out.println("Stack size: " + stack.size()); // Output: 2
    }
}

Time Complexity Analysis

Operation	Complexity
Push (push)	O(1)
Pop (pop)	O(1)
Peek (peek)	O(1)
Is Empty (isEmpty)	O(1)
Get Size (size)	O(1)
Print Stack (printStack)	O(n)