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()
}