<aside> 🔥

Reversing an string or array are easy with the help of stacks because Stack Uses LIFO Structure {means if you put 1,2,3 in stack and then take it from stack it gives you in reverse order 3,2,1}.

</aside>

1. Implement Stack with Help of ArrayLists

import java.util.ArrayList;

public class ArrayListInStack {
    static class Stack{
        static ArrayList<Integer> list = new ArrayList<>();
        //isEmpty
        public static boolean isEmpty() {
            return list.size() == 0;
        }
        //Push
        public static void Push(int data) {
            list.add(data);
        }
        //Pop
        public static int Pop() {
            if (isEmpty()) {
                return -1;//Jab Stack khali hoga mallum padh ajyega ki stack kahli hn
            }
            int top = list.get(list.size()-1);
            list.remove(list.size()-1);
            return top;
        }
        //Peek
        public static int Peek() {
            if (isEmpty()) {
                return -1;//Jab Stack khali hoga mallum padh ajyega ki stack kahli hn
            }
            return list.get(list.size()-1);
        }
    }
    public static void main(String[] args) {
        Stack s = new Stack();
        s.Push(1);
        s.Push(2);
        s.Push(3);

        
            // s.Pop();
        while (!s.isEmpty()) {
            System.out.println(s.Peek());
            s.Pop();
        }
        System.out.println(s.Peek());
    }
}

1. Implement Stack with Help of LinkedList

public class LinkedList{
    static class Node{
        int data;
        Node next;

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

    static class stack{
        static Node head = null;

        public static boolean isEmpty() {
            return head==null;
        }
        //Push
        public static void Push(int data) {
             Node newNode = new Node(data);
            //Agar LL khali hua tho newNode hi head hn
            if (isEmpty()) {
                head = newNode;
                return;
            }

            newNode.next = head;
            head = newNode;

        }
        //Pop
        public static int Pop() {
            if (isEmpty()) {
                return -1;
            }
            int top = head.data;
            head = head.next;
            return top;
        }
        //Peek
        public static int Peek() {
            if (isEmpty()) {
                return -1;
            }
            return head.data;
        }

    }
    public static void main(String[] args) {
        stack s = new stack();
        s.Push(1);
        s.Push(2);
        s.Push(3);

        while (!s.isEmpty()) {
            System.out.println(s.Peek());
            s.Pop();
        }
    }
}

1. Push at Bottom of the Stack

//Q-1 => Push at Buttom of Stack  {Amazon}
    public static void pushAtBottom(Stack<Integer> s , int data) {
        if (s.isEmpty()) {
            s.push(data);
            return;
        }
        int top = s.pop();
        pushAtBottom(s, data);  //Recursion Step
        s.push(top);
    }

1. Reverse a String Using Stack {Amazon, Microsoft, Adobe, Flipkart, Paytm}

public static String ReverseString(String str) {
        Stack<Character> s = new Stack<>();
        int index = 0;
        while (index < str.length()) {
            s.push(str.charAt(index));
            index++;
        }
        StringBuilder result =new StringBuilder();
        while (!s.isEmpty()) {
            char ch = s.pop();
            result.append(ch);
        }
        return result.toString();
        //Str => string & result =>String builder inh dono ka type alag hota hn isliye hum idhar .toString use kar rahe
    }

1. Reverse a Stack

//Q-3 => Reverse a Stack
    public static void reverseStack(Stack<Integer> s) {
        if (s.isEmpty()) {
            return;
        }
        int top = s.pop();
        reverseStack(s);
        pushAtBottom(s, top);
    }

1. Next Greater Element

public static int[] nextele(int arr[]) {
        int nex[] = new int[arr.length];
        Stack<Integer> s = new Stack<>();
        for (int i = arr.length-1; i >= 0; i--) {
            while (!s.empty() && arr[s.peek()] <= arr[i]) {
                s.pop();
            }
            if (s.isEmpty()) {
                nex[i] = -1;
            }else{
                nex[i] = arr[s.peek()];
            }
            s.push(i);
        }
        return nex;
    }

1. Valid Parentheses

public static boolean validcolumn(String s) {
        Stack<Character> st = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '['  ||  ch == '{') {
                st.push(ch);
            }else{
                if (st.isEmpty()) {
                    return false;
                }
                if ((st.peek() == '(' && ch == ')') || (st.peek() == '{' && ch == '}') || (st.peek() == '[' && ch == ']')) {
                    st.pop();
                }else{
                    return false;
                }
            }
        }
        if (st.isEmpty()) {
            return true;
        }
        return false;
    }

1. Duplicate Parentheses

public static boolean duplicateparenthises(String s) {
        Stack<Character> st = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ')') { //closing
                int c = 0;
                while (st.peek() != '(') {
                    st.pop();
                    c++;
                }
                if (c<1) {
                    return true;
                }else{
                    st.pop();
                }
            }else{
                st.push(ch);
            }
        }
        return false;
    }

1. Trapping Rainwater

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        //calculate left max boundary -array
        int leftMax[] = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(height[i], leftMax[i-1]);
            //i-1 kyuki previous element ka compare karna tha 
        }
        //calculate right max boundary -array
        int rightMax[] = new int[n];
        rightMax[n-1] = height[n-1];
        //n-2 se kyu kyuki n-1 ke liye allready count hogayi hn value
        for (int i = n-2; i >= 0; i--) {
            rightMax[i] = Math.max(height[i], rightMax[i+1]);
            //i+1 kyuki Aage wale element se compare karna tha  
        }
        //loop
        int trapedwater = 0;
        for (int i = 0; i < n ; i++) {
            //waterlevel = min(leftmax bound , rightmax bound)
            int waterlevel = Math.min(leftMax[i], rightMax[i]);
            //trapedwater = waterlevel - height[i]
            trapedwater += waterlevel - height[i];
        }
        return trapedwater;
    }
}