Find Max in Stack Without Using Another Stack

At the time of push, push will be 2 * push - max and at the time of pop the max = 2 * max - peek; we are multiplying it by 2 so that we can get actual no, if top element of stack is max and has been removed and new top is not next man, then we don't have any means to get the max integer from remaining stack elements, so at the time of pushing, we alter the push element in such a way so that at the time of pop we can get the next max .

package org.wesome.dsalgo;

import java.util.Stack;

public class MaxInStack {
    public static void main(String[] args) {
        MyStack s = new MyStack();
        s.push(4);
        s.push(3);
        s.push(9);
        s.push(2);
        s.push(8);
        s.getMax();
        s.peek();
        s.pop();
        s.pop();
        s.pop();
        s.pop();
        s.pop();
        s.getMax();
        s.peek();
    }

    static class MyStack {
        Stack<Integer> stack = new Stack();
        int max;

        void getMax() {
            if (stack.empty())
                System.out.println("Stack is empty");
                // variable maxEle stores the maximum element in the stack.
            else
                System.out.println("Maximum Element in the stack is: " + max);
        }

        // Prints top element of MyStack
        void peek() {
            if (stack.empty()) {
                System.out.print("Stack is empty ");
                return;
            }
            int peak = stack.peek(); // Top element.
            System.out.println("Top Most Element is: " + peak + " max is " + max);
        }

        // Remove the top element from MyStack
        void pop() {
            if (stack.empty()) {
                System.out.println("Stack is empty");
                return;
            }
            int peek = stack.peek();
            stack.pop();
            if (peek > max) {
                System.out.println("peak " + peek + " is greater then max " + max);
                max = 2 * max - peek;
            }
            System.out.println("Top Most Element " + peek + " is Removed, max is " + max);
            // Maximum will change as the maximum element of the stack is being removed.

        }

        // Removes top element from MyStack
        void push(int push) {
            // Insert new number into the stack
            if (stack.empty()) {
                max = push;
                System.out.println("stack is empty, Number Inserted: " + push + " new max is = " + max);
                stack.push(push);
                return;
            }
            // If new number is less than maxEle
            if (push > max) {
                int tempPush = 2 * push - max;
                System.out.println("push = " + push + " is greater then existing max = " + max);
                max = push;
                System.out.println("pushing = " + tempPush + " new max is = " + max);
                stack.push(tempPush);
            } else {
                System.out.println("push = " + push + " is less then existing max = " + max);
                stack.push(push);
            }
        }
    }
}

 

follow us on