Repository: TheAlgorithms/Java
Pull request #5623 (2024-10-07 09:29:22)

Add QueueByTwoStacks.java new algorithm
<!--
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/5623?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 `76.47059%` with `4 lines` in your changes missing coverage. Please review.
> Project coverage is 54.77%. Comparing base [(`f34fe4d`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/f34fe4d8408ac35cef900cfae022ffadfc007ea3?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`05359bc`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/05359bca5391cad7c5320576ac831e04411e0262?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).
> Report is 6 commits behind head on master.

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5623?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...rithms/datastructures/queues/QueueByTwoStacks.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5623?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Fqueues%2FQueueByTwoStacks.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9xdWV1ZXMvUXVldWVCeVR3b1N0YWNrcy5qYXZh) | 76.47% | [4 Missing :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5623?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    #5623      +/-   ##
============================================
+ Coverage     54.56%   54.77%   +0.21%     
- Complexity     3413     3461      +48     
============================================
  Files           535      539       +4     
  Lines         15383    15600     +217     
  Branches       2935     2964      +29     
============================================
+ Hits           8393     8545     +152     
- Misses         6637     6698      +61     
- Partials        353      357       +4     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5623?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).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 1cd30a33..228735aa 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -170,6 +170,7 @@
               * [LinkedQueue](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java)
               * [PriorityQueues](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/queues/PriorityQueues.java)
               * [Queue](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/queues/Queue.java)
+              * [QueueByTwoStacks](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/queues/QueueByTwoStacks.java)
             * stacks
               * [NodeStack](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/stacks/NodeStack.java)
               * [ReverseStack](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/stacks/ReverseStack.java)
@@ -477,6 +478,7 @@
           * searches
             * [BinarySearch](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/searches/BinarySearch.java)
             * [BinarySearch2dArray](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/searches/BinarySearch2dArray.java)
+            * [BM25InvertedIndex](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/searches/BM25InvertedIndex.java)
             * [BreadthFirstSearch](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/searches/BreadthFirstSearch.java)
             * [DepthFirstSearch](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/searches/DepthFirstSearch.java)
             * [ExponentalSearch](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/searches/ExponentalSearch.java)
@@ -731,6 +733,7 @@
               * [GenericArrayListQueueTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/queues/GenericArrayListQueueTest.java)
               * [LinkedQueueTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/queues/LinkedQueueTest.java)
               * [PriorityQueuesTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/queues/PriorityQueuesTest.java)
+              * [QueueByTwoStacksTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/queues/QueueByTwoStacksTest.java)
               * [QueueTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/queues/QueueTest.java)
             * stacks
               * [LinkedListStackTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/stacks/LinkedListStackTest.java)
@@ -756,7 +759,7 @@
               * [SplayTreeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/SplayTreeTest.java)
               * [TreapTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/TreapTest.java)
               * [TreeTestUtils](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/TreeTestUtils.java)
-              * [TrieImpTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/TrieImpTest.java)
+              * [TrieTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/TrieTest.java)
               * [VerticalOrderTraversalTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/VerticalOrderTraversalTest.java)
               * [ZigzagTraversalTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/ZigzagTraversalTest.java)
           * divideandconquer
@@ -887,6 +890,7 @@
             * [PrimeFactorizationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PrimeFactorizationTest.java)
             * [PronicNumberTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PronicNumberTest.java)
             * [PythagoreanTripleTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PythagoreanTripleTest.java)
+            * [QuadraticEquationSolverTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/QuadraticEquationSolverTest.java)
             * [ReverseNumberTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/ReverseNumberTest.java)
             * [SecondMinMaxTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SecondMinMaxTest.java)
             * [SieveOfEratosthenesTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SieveOfEratosthenesTest.java)
@@ -952,6 +956,7 @@
             * [SRTFSchedulingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/scheduling/SRTFSchedulingTest.java)
           * searches
             * [BinarySearch2dArrayTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/BinarySearch2dArrayTest.java)
+            * [BM25InvertedIndexTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/BM25InvertedIndexTest.java)
             * [BreadthFirstSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/BreadthFirstSearchTest.java)
             * [DepthFirstSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/DepthFirstSearchTest.java)
             * [HowManyTimesRotatedTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/HowManyTimesRotatedTest.java)
diff --git a/src/main/java/com/thealgorithms/datastructures/queues/QueueByTwoStacks.java b/src/main/java/com/thealgorithms/datastructures/queues/QueueByTwoStacks.java
new file mode 100644
index 00000000..11e5e9b8
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/queues/QueueByTwoStacks.java
@@ -0,0 +1,87 @@
+package com.thealgorithms.datastructures.queues;
+
+import java.util.NoSuchElementException;
+import java.util.Stack;
+
+/**
+ * A queue implementation using two stacks. This class provides methods to
+ * enqueue (add) elements to the end of the queue and dequeue (remove)
+ * elements from the front, while utilizing two internal stacks to manage
+ * the order of elements.
+ *
+ * @param <T> The type of elements held in this queue.
+ */
+public class QueueByTwoStacks<T> {
+
+    private final Stack<T> enqueueStk;
+    private final Stack<T> dequeueStk;
+
+    /**
+     * Constructor that initializes two empty stacks for the queue.
+     * The `enqueueStk` is used to push elements when enqueuing, and
+     * the `dequeueStk` is used to pop elements when dequeuing.
+     */
+    public QueueByTwoStacks() {
+        enqueueStk = new Stack<>();
+        dequeueStk = new Stack<>();
+    }
+
+    /**
+     * Adds an element to the end of the queue. This method pushes the element
+     * onto the `enqueueStk`.
+     *
+     * @param item The element to be added to the queue.
+     */
+    public void put(T item) {
+        enqueueStk.push(item);
+    }
+
+    /**
+     * Removes and returns the element at the front of the queue.
+     * If `dequeueStk` is empty, it transfers all elements from
+     * `enqueueStk` to `dequeueStk` to maintain the correct FIFO
+     * (First-In-First-Out) order before popping.
+     *
+     * @return The element at the front of the queue.
+     * @throws NoSuchElementException If the queue is empty.
+     */
+    public T get() {
+        if (dequeueStk.isEmpty()) {
+            while (!enqueueStk.isEmpty()) {
+                dequeueStk.push(enqueueStk.pop());
+            }
+        }
+        if (dequeueStk.isEmpty()) {
+            throw new NoSuchElementException("Queue is empty");
+        }
+        return dequeueStk.pop();
+    }
+
+    /**
+     * Returns the total number of elements currently in the queue.
+     * This is the sum of the sizes of both stacks.
+     *
+     * @return The number of elements in the queue.
+     */
+    public int size() {
+        return enqueueStk.size() + dequeueStk.size();
+    }
+
+    /**
+     * Returns a string representation of the queue, showing the elements
+     * in the correct order (from front to back).
+     * The `dequeueStk` is first cloned, and then all elements from the
+     * `enqueueStk` are added to the cloned stack in reverse order to
+     * represent the queue accurately.
+     *
+     * @return A string representation of the queue.
+     */
+    @Override
+    public String toString() {
+        Stack<T> tempStack = (Stack<T>) dequeueStk.clone();
+        while (!enqueueStk.isEmpty()) {
+            tempStack.push(enqueueStk.pop());
+        }
+        return "Queue(" + tempStack + ")";
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/queues/QueueByTwoStacksTest.java b/src/test/java/com/thealgorithms/datastructures/queues/QueueByTwoStacksTest.java
new file mode 100644
index 00000000..87f136a8
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/queues/QueueByTwoStacksTest.java
@@ -0,0 +1,69 @@
+package com.thealgorithms.datastructures.queues;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+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 QueueByTwoStacksTest {
+
+    private QueueByTwoStacks<Integer> queue;
+
+    @BeforeEach
+    public void setUp() {
+        queue = new QueueByTwoStacks<>();
+    }
+
+    @Test
+    public void testEmptyQueue() {
+        assertEquals(0, queue.size());
+    }
+
+    @Test
+    public void testEnqueue() {
+        queue.put(10);
+        queue.put(20);
+        assertEquals(2, queue.size());
+    }
+
+    @Test
+    public void testDequeue() {
+        queue.put(10);
+        queue.put(20);
+        queue.put(30);
+        assertEquals(10, queue.get()); // First item out
+        assertEquals(20, queue.get()); // Second item out
+        assertEquals(30, queue.get()); // Third item out
+    }
+
+    @Test
+    public void testInterleavedOperations() {
+        queue.put(10);
+        queue.put(20);
+        assertEquals(10, queue.get()); // Dequeue first item
+        queue.put(30);
+        assertEquals(20, queue.get()); // Dequeue second item
+        assertEquals(30, queue.get()); // Dequeue third item
+    }
+
+    @Test
+    public void testQueueSize() {
+        assertEquals(0, queue.size());
+        queue.put(1);
+        assertEquals(1, queue.size());
+        queue.put(2);
+        queue.put(3);
+        assertEquals(3, queue.size());
+        queue.get();
+        assertEquals(2, queue.size());
+    }
+
+    @Test
+    public void testEmptyQueueException() {
+        assertThrows(NoSuchElementException.class, () -> {
+            queue.get(); // Attempting to dequeue from empty queue
+        });
+    }
+}