• While doing recursion we came across Stack, in which every function call was stacked over each other and after reaching base condition, it now popped up, the last function that entered will be the first to popped out.

• Stack uses this analogy of LAST IN FIRST OUT(LIFO).

• Some real life examples are Stacking of plates in wedding.

• When we remove something from stack is it is called popped out and when we add anything it is called pushed in or in simple words, it is push when we add something and pop when we remove something.

Custom Stack Implementation

// CustomStack class represents a simple stack implementation using an array.

public class CustomStack {

    // Array to store stack elements
    protected int[] data;

    // Default size for the stack
    private static final int Default_size = 10;

    // Pointer to keep track of the top element in the stack
    int pointer = -1;

    // Default constructor, creates a stack with default size
    public CustomStack() {
        this(Default_size);
    }

    // Parameterized constructor, creates a stack with a specified size
    public CustomStack(int size) {
        this.data = new int[size];
    }

    // Method to push an item onto the stack
    // Returns true if successful, false if the stack is full
    public boolean push(int item) {
        if (isFull()) {
            return false;
        }
        pointer++;
        data[pointer] = item;
        return true;
    }

    // Method to pop an item from the stack
    // Throws an exception if the stack is empty
    public int pop() throws Exception {
        if (isEmpty()) {
            throw new Exception("Cannot pop. Stack is empty.");
        }
        return data[pointer--];
    }

    // Method to peek at the top item of the stack without removing it
    // Throws an exception if the stack is empty
    public int peek() throws Exception {
        if (isEmpty()) {
            throw new Exception("Cannot peek. Stack is empty.");
        }
        return data[pointer];
    }

    // Method to check if the stack is full
    public boolean isFull() {
        return pointer == data.length - 1;
    }

    // Method to check if the stack is empty
    public boolean isEmpty() {
        return pointer == -1;
    }
}

Stack and It's common methods

1. push(E item):

   • Adds an item to the top of the stack.

    Stack<Integer> stack = new Stack<>();
    stack.push(10);
    stack.push(20);

1. pop():

   • Removes and returns the item from the top of the stack. It throws an EmptyStackException if the stack is empty.

    int topItem = stack.pop();

1. peek():

   • Returns the item from the top of the stack without removing it. It throws an EmptyStackException if the stack is empty.

    int topItem = stack.peek();

1. empty():

   • Returns true if the stack is empty; otherwise, returns false.

    boolean isEmpty = stack.empty();

1. search(Object o):

   • Searches for the specified object in the stack and returns its position. The position is returned as an offset from the top of the stack. If the object is not found, it returns -1.

    int position = stack.search(20);

1. Using Deque interface:

   • You can also use the Deque interface (e.g., LinkedList class) to implement stack operations. In this case, you would use push(), pop(), and peek() methods.

    Deque<Integer> stack = new LinkedList<>();
    stack.push(10);
    int topItem = stack.pop();

Dynamic Implementation of Stack

// Declaration of a class named DynamicStack, which extends the CustomStack class.
public class DynamicStack extends CustomStack {

    // Default constructor for the DynamicStack class.
    public DynamicStack() {
        super(); // Calls the default constructor of the superclass (CustomStack).
    }

    // Parameterized constructor for the DynamicStack class, taking an initial size.
    public DynamicStack(int size) {
        super(size); // Calls the parameterized constructor of the superclass (CustomStack) with the given size.
    }

    // Overriding the push method from the superclass (CustomStack).
    @Override
    public boolean push(int item) {
        // Check if the stack is full using the isFull method from the superclass.
        if (this.isFull()) {
            // If the stack is full, create a new array with double the size of the current one.
            int[] temp = new int[data.length * 2];

            // Copy all previous items from the current array to the new array.
            for (int i = 0; i < data.length; i++) {
                temp[i] = data[i];
            }

            // Update the reference of the 'data' variable to the new array.
            data = temp;
        }

        // At this point, the array is not full, so proceed to insert the item using the superclass push method.
        return super.push(item);
    }

Resources:

1. ChatGPT

2. https://youtu.be/rHQI4mrJ3cg?si=9VvI6VRZT7MjfZdG