Find Max in Stack Using Another Stack

package org.wesome.dsalgo;

import java.util.Stack;

public class MaxInStack {
    //    this is main stack
    Stack<Integer> mainStack = new Stack<>();
    //    this is maxStack, with every put in mainStack, current max will be kept in sync
    Stack<Integer> maxStack = new Stack<>();

    public void insert(int push) {
        if (mainStack.isEmpty()) {
//            mainStack and maxStack is empty, so there is no max right now, so we will add push in both stack
            mainStack.add(push);
            maxStack.add(push);
        } else {
//            mainStack already have elements, so new maxStack top will be max of existing maxStack top and current push
            int maxStackTop = maxStack.peek();
            maxStack.add(Math.max(maxStackTop, push));
            mainStack.add(push);
        }
    }

    public int remove() {
        if (!mainStack.isEmpty()) {
//            if mainStack is not empty then we have to remove top of both mainStack and maxStack, to keep both stack in sync
            maxStack.pop();
            return mainStack.pop();
        }
        return 0;
    }

    public int getMax() {
        return maxStack.peek();
    }
}
package org.wesome.dsalgo;

import org.junit.jupiter.api.Test;

import java.util.EmptyStackException;

import static org.junit.jupiter.api.Assertions.*;

public class MaxInStackTest {
    @Test
    void maxInStack() {
        MaxInStack maxInStack = new MaxInStack();
        maxInStack.insert(4);
        assertEquals(4, maxInStack.getMax());

        maxInStack.insert(2);
        assertEquals(4, maxInStack.getMax());

        maxInStack.insert(14);
        assertEquals(14, maxInStack.getMax());

        maxInStack.insert(1);
        assertEquals(14, maxInStack.getMax());

        maxInStack.insert(18);
        assertEquals(18, maxInStack.getMax());


        assertAll(() -> assertEquals(18, maxInStack.remove()),
                () -> assertEquals(14, maxInStack.getMax()));

        assertAll(() -> assertEquals(1, maxInStack.remove()),
                () -> assertEquals(14, maxInStack.getMax()));

        assertAll(() -> assertEquals(14, maxInStack.remove()),
                () -> assertEquals(4, maxInStack.getMax()));

        assertAll(() -> assertEquals(2, maxInStack.remove()),
                () -> assertEquals(4, maxInStack.getMax()));

        assertAll(() -> assertEquals(4, maxInStack.remove()),
                () -> assertThrows(EmptyStackException.class, () -> maxInStack.getMax(), "stack is empty so will throw exception"));
    }
}
plugins {
    id 'org.springframework.boot' version '2.5.4'
    id 'io.spring.dependency-management' version '1.0.11.RELEASE'
    id 'java'
}

group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8

configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
}

repositories {
    mavenCentral()
}

dependencies {
    compileOnly 'org.projectlombok:lombok'
    annotationProcessor 'org.projectlombok:lombok'
    testImplementation 'org.springframework.boot:spring-boot-starter-test'
}

test {
    useJUnitPlatform()
}

 

follow us on