Repository: TheAlgorithms/Java
Pull request #5714 (2024-10-11 05:05:05)

Added the retrieval of minimum and maximum element from stack at O(1)
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [X] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [X] This pull request is all my own work -- I have not plagiarized it.
- [X] All filenames are in PascalCase.
- [X] All functions and variable names follow Java naming conventions.
- [X] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [X] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5714?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `0%` with `42 lines` in your changes missing coverage. Please review.
> Project coverage is 62.59%. Comparing base [(`7326ab2`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/7326ab2c121ff7059bd17e5745afa7d70b98d0f0?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`b4e2d90`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/b4e2d90a73ce488ba34108133ac08e811ee1e1e3?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5714?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...algorithms/stacks/GreatestElementConstantTime.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5714?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fstacks%2FGreatestElementConstantTime.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9zdGFja3MvR3JlYXRlc3RFbGVtZW50Q29uc3RhbnRUaW1lLmphdmE=) | 0.00% | [21 Missing :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5714?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |
| [...algorithms/stacks/SmallestElementConstantTime.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5714?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fstacks%2FSmallestElementConstantTime.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9zdGFja3MvU21hbGxlc3RFbGVtZW50Q29uc3RhbnRUaW1lLmphdmE=) | 0.00% | [21 Missing :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5714?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5714      +/-   ##
============================================
- Coverage     62.77%   62.59%   -0.18%     
+ Complexity     4025     4024       -1     
============================================
  Files           565      567       +2     
  Lines         15939    15981      +42     
  Branches       3076     3080       +4     
============================================
- Hits          10006    10004       -2     
- Misses         5521     5564      +43     
- Partials        412      413       +1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5714?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

saahil-mahato: This is missing test case when the `maxStack` is empty and we attempt to `push` or `pop`. Please confirm. Thanks.
S-M-J-I: > This is missing test case when the `maxStack` is empty and we attempt to `push` or `pop`. Please confirm. Thanks.

Hi. Thanks for the comment. The test case when `maxStack` is empty and we attempt to `pop` from it is present as `testNullMax()`. As for the `push`, the `maxStack` will not be empty as long as the `mainStack` has at least one value. Thank you for bringing this to my attention, I will add a test case where we clear the stack and then try to push into it and try to retrive the max value. 
S-M-J-I: > We do not add leetcode problems, please add references to other sources if they exist

Hello @siriak, I added another ref for this algorithm.
S-M-J-I: Hello @siriak, I have made the reference changes as advised. Please let me know your reviews.

Patch:
diff --git a/src/main/java/com/thealgorithms/stacks/SmallestElementConstantTime.java b/src/main/java/com/thealgorithms/stacks/SmallestElementConstantTime.java
new file mode 100644
index 00000000..9864ef9b
--- /dev/null
+++ b/src/main/java/com/thealgorithms/stacks/SmallestElementConstantTime.java
@@ -0,0 +1,74 @@
+package com.thealgorithms.stacks;
+
+import java.util.NoSuchElementException;
+import java.util.Stack;
+
+/**
+ * A class that implements a stack that gives the minimum element in O(1) time.
+ * The mainStack is used to store the all the elements of the stack
+ * While the minStack stores the minimum elements
+ * When we want to get a minimum element, we call the top of the minimum stack
+ *
+ * Problem: https://www.baeldung.com/cs/stack-constant-time
+ */
+public class SmallestElementConstantTime {
+    private Stack<Integer> mainStack; // initialize a mainStack
+    private Stack<Integer> minStack; // initialize a minStack
+
+    /**
+     * Constructs two empty stacks
+     */
+    public SmallestElementConstantTime() {
+        mainStack = new Stack<>();
+        minStack = new Stack<>();
+    }
+
+    /**
+     * Pushes an element onto the top of the stack.
+     * Checks if the element is the minimum or not
+     * If so, then pushes to the minimum stack
+     * @param data The element to be pushed onto the stack.
+     */
+    public void push(int data) {
+        if (mainStack.isEmpty()) {
+            mainStack.push(data);
+            minStack.push(data);
+            return;
+        }
+
+        mainStack.push(data);
+        if (data < minStack.peek()) {
+            minStack.push(data);
+        }
+    }
+
+    /**
+     * Pops an element from the stack.
+     * Checks if the element to be popped is the minimum or not
+     * If so, then pop from the minStack
+     *
+     * @throws NoSuchElementException if the stack is empty.
+     */
+    public void pop() {
+        if (mainStack.isEmpty()) {
+            throw new NoSuchElementException("Stack is empty");
+        }
+
+        int ele = mainStack.pop();
+        if (ele == minStack.peek()) {
+            minStack.pop();
+        }
+    }
+
+    /**
+     * Returns the minimum element present in the stack
+     *
+     * @return The element at the top of the minStack, or null if the stack is empty.
+     */
+    public Integer getMinimumElement() {
+        if (minStack.isEmpty()) {
+            return null;
+        }
+        return minStack.peek();
+    }
+}


Test patch:
diff --git a/src/main/java/com/thealgorithms/stacks/GreatestElementConstantTime.java b/src/main/java/com/thealgorithms/stacks/GreatestElementConstantTime.java
new file mode 100644
index 00000000..be9d0099
--- /dev/null
+++ b/src/main/java/com/thealgorithms/stacks/GreatestElementConstantTime.java
@@ -0,0 +1,74 @@
+package com.thealgorithms.stacks;
+
+import java.util.NoSuchElementException;
+import java.util.Stack;
+
+/**
+ * A class that implements a stack that gives the maximum element in O(1) time.
+ * The mainStack is used to store the all the elements of the stack
+ * While the maxStack stores the maximum elements
+ * When we want to get a maximum element, we call the top of the maximum stack
+ *
+ * Problem: https://www.baeldung.com/cs/stack-constant-time
+ */
+public class GreatestElementConstantTime {
+    private Stack<Integer> mainStack; // initialize a mainStack
+    private Stack<Integer> maxStack; // initialize a maxStack
+
+    /**
+     * Constructs two empty stacks
+     */
+    public GreatestElementConstantTime() {
+        mainStack = new Stack<>();
+        maxStack = new Stack<>();
+    }
+
+    /**
+     * Pushes an element onto the top of the stack.
+     * Checks if the element is the maximum or not
+     * If so, then pushes to the maximum stack
+     * @param data The element to be pushed onto the stack.
+     */
+    public void push(int data) {
+        if (mainStack.isEmpty()) {
+            mainStack.push(data);
+            maxStack.push(data);
+            return;
+        }
+
+        mainStack.push(data);
+        if (data > maxStack.peek()) {
+            maxStack.push(data);
+        }
+    }
+
+    /**
+     * Pops an element from the stack.
+     * Checks if the element to be popped is the maximum or not
+     * If so, then pop from the minStack
+     *
+     * @throws NoSuchElementException if the stack is empty.
+     */
+    public void pop() {
+        if (mainStack.isEmpty()) {
+            throw new NoSuchElementException("Stack is empty");
+        }
+
+        int ele = mainStack.pop();
+        if (ele == maxStack.peek()) {
+            maxStack.pop();
+        }
+    }
+
+    /**
+     * Returns the maximum element present in the stack
+     *
+     * @return The element at the top of the maxStack, or null if the stack is empty.
+     */
+    public Integer getMaximumElement() {
+        if (maxStack.isEmpty()) {
+            return null;
+        }
+        return maxStack.peek();
+    }
+}
diff --git a/src/test/java/com/thealgorithms/stacks/GreatestElementConstantTimeTest.java b/src/test/java/com/thealgorithms/stacks/GreatestElementConstantTimeTest.java
new file mode 100644
index 00000000..080592dc
--- /dev/null
+++ b/src/test/java/com/thealgorithms/stacks/GreatestElementConstantTimeTest.java
@@ -0,0 +1,70 @@
+package com.thealgorithms.stacks;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import java.util.NoSuchElementException;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+public class GreatestElementConstantTimeTest {
+
+    private GreatestElementConstantTime constantTime;
+
+    @BeforeEach
+    public void setConstantTime() {
+        constantTime = new GreatestElementConstantTime();
+    }
+
+    @Test
+    public void testMaxAtFirst() {
+        constantTime.push(1);
+        constantTime.push(10);
+        constantTime.push(20);
+        constantTime.push(5);
+        assertEquals(20, constantTime.getMaximumElement());
+    }
+
+    @Test
+    public void testMinTwo() {
+        constantTime.push(5);
+        constantTime.push(10);
+        constantTime.push(20);
+        constantTime.push(1);
+        assertEquals(20, constantTime.getMaximumElement());
+        constantTime.pop();
+        constantTime.pop();
+        assertEquals(10, constantTime.getMaximumElement());
+    }
+
+    @Test
+    public void testNullMax() {
+        constantTime.push(10);
+        constantTime.push(20);
+        constantTime.pop();
+        constantTime.pop();
+        assertNull(constantTime.getMaximumElement());
+    }
+
+    @Test
+    public void testBlankHandle() {
+        constantTime.push(10);
+        constantTime.push(1);
+        constantTime.pop();
+        constantTime.pop();
+        assertThrows(NoSuchElementException.class, () -> constantTime.pop());
+    }
+
+    @Test
+    public void testPushPopAfterEmpty() {
+        constantTime.push(10);
+        constantTime.push(1);
+        constantTime.pop();
+        constantTime.pop();
+        constantTime.push(5);
+        assertEquals(5, constantTime.getMaximumElement());
+        constantTime.push(1);
+        assertEquals(5, constantTime.getMaximumElement());
+    }
+}
diff --git a/src/test/java/com/thealgorithms/stacks/SmallestElementConstantTimeTest.java b/src/test/java/com/thealgorithms/stacks/SmallestElementConstantTimeTest.java
new file mode 100644
index 00000000..b5eda9e8
--- /dev/null
+++ b/src/test/java/com/thealgorithms/stacks/SmallestElementConstantTimeTest.java
@@ -0,0 +1,69 @@
+package com.thealgorithms.stacks;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import java.util.NoSuchElementException;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+public class SmallestElementConstantTimeTest {
+
+    private SmallestElementConstantTime sect;
+
+    @BeforeEach
+    public void setSect() {
+        sect = new SmallestElementConstantTime();
+    }
+
+    @Test
+    public void testMinAtFirst() {
+        sect.push(1);
+        sect.push(10);
+        sect.push(20);
+        sect.push(5);
+        assertEquals(1, sect.getMinimumElement());
+    }
+
+    @Test
+    public void testMinTwo() {
+        sect.push(5);
+        sect.push(10);
+        sect.push(20);
+        sect.push(1);
+        assertEquals(1, sect.getMinimumElement());
+        sect.pop();
+        assertEquals(5, sect.getMinimumElement());
+    }
+
+    @Test
+    public void testNullMin() {
+        sect.push(10);
+        sect.push(20);
+        sect.pop();
+        sect.pop();
+        assertNull(sect.getMinimumElement());
+    }
+
+    @Test
+    public void testBlankHandle() {
+        sect.push(10);
+        sect.push(1);
+        sect.pop();
+        sect.pop();
+        assertThrows(NoSuchElementException.class, () -> sect.pop());
+    }
+
+    @Test
+    public void testPushPopAfterEmpty() {
+        sect.push(10);
+        sect.push(1);
+        sect.pop();
+        sect.pop();
+        sect.push(5);
+        assertEquals(5, sect.getMinimumElement());
+        sect.push(1);
+        assertEquals(1, sect.getMinimumElement());
+    }
+}