Stack

The Stack looks more like a container which holds the element, will insert element from the top and remove from the top only. It follows the Last in First out(LIFO) or First In Last out (FILO) approach. Java uses the method stack area to hold the state of the method if some method calls another method inside it.  

public class Demo {
    public static void main(String[] args) {
        new Demo().firstCall();
        System.out.println("Main");
    }
    public void firstCall() {
        secondCall();
        System.out.println("First");
    }
    private void secondCall() {
        thirdCall();
        System.out.println("Second");
    }
    private void thirdCall() {
        System.out.println("Third");
    }
}

This is how it maintains the method call in the method stack area. It will remove from the top every time and complete its method execution and remove next's top from the stack. This process will continue until the stack is empty.

We can implement a stack using Array as well as Linked List. In the Singly Linked List, we will add and remove the element from the starting position only. Linked List will give us the capability to add n number of elements without defining the constant size of the list.

NOTE: -Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it as an Object.

Stack Implementation using Array

#1 Initialization of Custom Stack

public class CustomStack<T> {
    T[] stack;
    int length = 0;

    public CustomStack(T[] stack) {
        this.stack = stack;
    }

}

#2 Push an element - O(1)

public T push(T item) {
    if (stack.length > length) {
        stack[length++] = item;
        return item;
    } else
        throw new StackOverflowError();
}

If the stack is full then throw an overflow error otherwise it will add an element into the stack.

#3 Pop an element - O(1)

public T pop() {
    if (length > 0) {
        T val = stack[length--];
        return val;
    } else
        throw new EmptyStackException();
}

Remove the object at the top and return it, if the stack is empty then throw an EmptyStackException.

#4 Peek an element - O(1)

public T peek() {
    if (length > 0)
        return stack[length-1];
    throw new EmptyStackException();
}

Return the object at the top without removing it, if the stack is empty then throw an EmptyStackException.

#5 Setting element in a particular index - O(1)

public T set(int index, T val) {
    if (index >= 0 && index < length){
        stack[index] = val;
        return stack[index];
    }else
        throw new ArrayIndexOutOfBoundsException(index);
}

Setting an object into the particular index, if the index is greater than the number of elements in the stack then throw an ArrayIndexOutOfBoundsException.

#6 Searching an element - O(n)

public int search(T val) {
    for (int i = length-1; i >= 0; i--) {
        if (stack[i] == val)
            return length - i;
    }
    return -1;
}

Searching an element from the top to bottom in the stack. If the stack doesn't contain the value then it will return -1 otherwise the index from the top.

#7 Check Stack is Empty - O(1)

public boolean empty() {
    return length == 0;
}

# Get Stack Size - O(1)

public int size() {
    return length;
}

#8 Remove Element in a particular index - O(n)

public void removeElementAt(int index) {
    if (index > 0 && index <= length) {
        while (index < length) {
            stack[index] = stack[index+1];
            index++;
        }
        length--;
    }else
        throw new ArrayIndexOutOfBoundsException(index);
}

#9 Get the first stack element - O(1)

public T firstElement() {
    if (length > 0)
        return stack[0];
    throw new NoSuchElementException();
}

#10 Get the last stack element - O(1)

public T lastElement() {
    if (length > 0)
        return stack[length-1];
    throw new NoSuchElementException();
}

#11 Printing Stack Element - O(n)

public void print() {
    for (int i = 0; i < length; i++) {
        System.out.print(stack[i] + " ");
    }
}

Stack Implementation using Singly Linked List

#1 Create Custom Singly Linked List Class

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

    public Node() {
    }

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

    public Node(T data, Node next) {
        this.data = data;
        this.next = next;
    }
}

#2 Initialization of Custom Stack

public class CustomStack<T> {
    Node<T> head, tail;
    int length = 0;
}

#3 Push an element - O(1)

public T push(T val) {
    Node<T> node = new Node<>(val);
    if (head == null) {
        head = tail = node;
    } else {
        node.next = head;
        head = node;
    }
    length++;
    return val;
}

In the Linked list, we are considering head as a top and tail as a bottom of the stack. Whenever push method calls then it will add a new node in a starting position of the linked list.

#4 Pop an element - O(1)

public T pop() {
    if (length > 0) {
        T val = head.data;
        head = head.next;
        length--;
        return val;
    } else 
        throw new EmptyStackException();
}

#5 Peek an element - O(1)

public T peek() {
    if (length > 0) {
        return head.data;
    }
    throw new EmptyStackException();
}

#6 Setting element in a particular index - O(n) 

public T set(int index, T val) {
    if (index >= 0 && index < length) {
        Node<T> ref = head, fastRef = head;
        while (index-- > 0) {
            fastRef = fastRef.next;
        }
        while (fastRef.next != null) {
            fastRef = fastRef.next;
            ref = ref.next;
        }
        ref.data = val;
        return ref.data;
    }
    throw new ArrayIndexOutOfBoundsException(index);
}

#7 Searching an element - O(n)

public int search(T val) {
    Node ref = head;
    int index = -1;
    while (ref != null) {
        index++;
        if (ref.data == val)
            return index;
        ref = ref.next;
    }
    return -1;
}

#8 Get the first stack element - O(1)

public T firstElement() {
    if (tail != null)
        return tail.data;
    throw new NoSuchElementException();
}

#9 Get the last stack element- O(1)

public T lastElement() {
    if (head != null)
        return head.data;
    throw new NoSuchElementException();
}