Repository: TheAlgorithms/Java
Pull request #5353 (2024-08-20 22:02:26)

refactor: `Deque`
Make Deque generic.
Readability improvements.
Added tests.

<!--
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/5353?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 `87.50000%` with `3 lines` in your changes missing coverage. Please review.
> Project coverage is 44.72%. Comparing base [(`f5c0314`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/f5c0314111f5973748862e21d6e7ccbb9e53a3ee?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`630f377`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/630f377a9d00699ea63667618025bad0b51d52e9?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5353?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...com/thealgorithms/datastructures/queues/Deque.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5353?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Fqueues%2FDeque.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9xdWV1ZXMvRGVxdWUuamF2YQ==) | 87.50% | [3 Missing :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5353?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    #5353      +/-   ##
============================================
+ Coverage     44.38%   44.72%   +0.34%     
- Complexity     2752     2771      +19     
============================================
  Files           522      522              
  Lines         15419    15412       -7     
  Branches       2942     2942              
============================================
+ Hits           6843     6893      +50     
+ Misses         8282     8222      -60     
- Partials        294      297       +3     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5353?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/src/main/java/com/thealgorithms/datastructures/queues/Deques.java b/src/main/java/com/thealgorithms/datastructures/queues/Deque.java
similarity index 61%
rename from src/main/java/com/thealgorithms/datastructures/queues/Deques.java
rename to src/main/java/com/thealgorithms/datastructures/queues/Deque.java
index 5c4e9b64..4cfa2b44 100644
--- a/src/main/java/com/thealgorithms/datastructures/queues/Deques.java
+++ b/src/main/java/com/thealgorithms/datastructures/queues/Deque.java
@@ -1,5 +1,7 @@
 package com.thealgorithms.datastructures.queues;
 
+import java.util.NoSuchElementException;
+
 /**
  * A [deque](https://en.wikipedia.org/wiki/Double-ended_queue) is short for a
  * double ended queue pronounced "deck" and sometimes referred to as a head-tail
@@ -9,50 +11,24 @@ package com.thealgorithms.datastructures.queues;
  *
  * @author [Ian Cowan](https://github.com/iccowan)
  */
-public class Deques<T> {
+public class Deque<T> {
 
     /**
      * Node for the deque
      */
-    class DequeNode<S> {
-
-        /**
-         * Value of the node
-         */
+    private static class DequeNode<S> {
         S val;
-
-        /**
-         * Next node in the deque from this node
-         */
         DequeNode<S> next = null;
-
-        /**
-         * Previous node in the deque from this node
-         */
         DequeNode<S> prev = null;
 
-        /**
-         * Constructor
-         */
         DequeNode(S val) {
             this.val = val;
         }
     }
 
-    /**
-     * Head of the deque
-     */
-    DequeNode<T> head = null;
-
-    /**
-     * Tail of the deque
-     */
-    DequeNode<T> tail = null;
-
-    /**
-     * Size of the deque
-     */
-    int size = 0;
+    private DequeNode<T> head = null;
+    private DequeNode<T> tail = null;
+    private int size = 0;
 
     /**
      * Adds the specified value to the head of the deque
@@ -60,16 +36,12 @@ public class Deques<T> {
      * @param val Value to add to the deque
      */
     public void addFirst(T val) {
-        // Create a new node with the given value
-        DequeNode<T> newNode = new DequeNode<T>(val);
+        DequeNode<T> newNode = new DequeNode<>(val);
 
-        // Add the node
-        if (head == null) {
-            // If the deque is empty, add the node as the head and tail
+        if (isEmpty()) {
             head = newNode;
             tail = newNode;
         } else {
-            // If the deque is not empty, insert the node as the new head
             newNode.next = head;
             head.prev = newNode;
             head = newNode;
@@ -84,20 +56,15 @@ public class Deques<T> {
      * @param val Value to add to the deque
      */
     public void addLast(T val) {
-        // Create a new node with the given value
-        DequeNode<T> newNode = new DequeNode<T>(val);
-
-        // Add the node
+        DequeNode<T> newNode = new DequeNode<>(val);
         if (tail == null) {
-            // If the deque is empty, add the node as the head and tail
             head = newNode;
+            tail = newNode;
         } else {
-            // If the deque is not empty, insert the node as the new tail
             newNode.prev = tail;
             tail.next = newNode;
+            tail = newNode;
         }
-        tail = newNode;
-
         size++;
     }
 
@@ -105,33 +72,21 @@ public class Deques<T> {
      * Removes and returns the first (head) value in the deque
      *
      * @return the value of the head of the deque
+     * @throws NoSuchElementException if the deque is empty
      */
     public T pollFirst() {
-        // If the head is null, return null
         if (head == null) {
-            return null;
+            throw new NoSuchElementException("Deque is empty");
         }
 
-        // First, let's get the value of the old head
         T oldHeadVal = head.val;
-
-        // Now, let's remove the head
         if (head == tail) {
-            // If there is only one node, remove it
             head = null;
             tail = null;
         } else {
-            // If there is more than one node, fix the references
-            head.next.prev = null;
-            DequeNode<T> oldHead = head;
             head = head.next;
-
-            // Can be considered unnecessary...
-            // Unlinking the old head to make sure there are no random
-            // references possibly affecting garbage collection
-            oldHead.next = null;
+            head.prev = null;
         }
-
         size--;
         return oldHeadVal;
     }
@@ -140,32 +95,21 @@ public class Deques<T> {
      * Removes and returns the last (tail) value in the deque
      *
      * @return the value of the tail of the deque
+     * @throws NoSuchElementException if the deque is empty
      */
     public T pollLast() {
-        // If the tail is null, return null
         if (tail == null) {
-            return null;
+            throw new NoSuchElementException("Deque is empty");
         }
 
-        // Let's get the value of the old tail
         T oldTailVal = tail.val;
-
-        // Now, remove the tail
         if (head == tail) {
-            // If there is only one node, remove it
             head = null;
             tail = null;
         } else {
-            // If there is more than one node, fix the references
-            tail.prev.next = null;
-            DequeNode<T> oldTail = tail;
             tail = tail.prev;
-
-            // Similarly to above, can be considered unnecessary
-            // See `pollFirst()` for explanation
-            oldTail.prev = null;
+            tail.next = null;
         }
-
         size--;
         return oldTailVal;
     }
@@ -173,19 +117,19 @@ public class Deques<T> {
     /**
      * Returns the first (head) value of the deque WITHOUT removing
      *
-     * @return the value of the head of the deque
+     * @return the value of the head of the deque, or null if empty
      */
     public T peekFirst() {
-        return head.val;
+        return head != null ? head.val : null;
     }
 
     /**
      * Returns the last (tail) value of the deque WITHOUT removing
      *
-     * @return the value of the tail of the deque
+     * @return the value of the tail of the deque, or null if empty
      */
     public T peekLast() {
-        return tail.val;
+        return tail != null ? tail.val : null;
     }
 
     /**
@@ -203,7 +147,7 @@ public class Deques<T> {
      * @return whether or not the deque is empty
      */
     public boolean isEmpty() {
-        return head == null;
+        return size == 0;
     }
 
     /**
@@ -216,25 +160,21 @@ public class Deques<T> {
      */
     @Override
     public String toString() {
-        String dequeString = "Head -> ";
+        StringBuilder dequeString = new StringBuilder("Head -> ");
         DequeNode<T> currNode = head;
         while (currNode != null) {
-            dequeString += currNode.val;
-
+            dequeString.append(currNode.val);
             if (currNode.next != null) {
-                dequeString += " <-> ";
+                dequeString.append(" <-> ");
             }
-
             currNode = currNode.next;
         }
-
-        dequeString += " <- Tail";
-
-        return dequeString;
+        dequeString.append(" <- Tail");
+        return dequeString.toString();
     }
 
     public static void main(String[] args) {
-        Deques<Integer> myDeque = new Deques<Integer>();
+        Deque<Integer> myDeque = new Deque<>();
         for (int i = 0; i < 42; i++) {
             if (i / 42.0 < 0.5) {
                 myDeque.addFirst(i);


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/queues/DequeTest.java b/src/test/java/com/thealgorithms/datastructures/queues/DequeTest.java
new file mode 100644
index 00000000..1244a2e2
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/queues/DequeTest.java
@@ -0,0 +1,90 @@
+package com.thealgorithms.datastructures.queues;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertNull;
+
+import java.util.NoSuchElementException;
+import org.junit.jupiter.api.Test;
+
+class DequeTest {
+
+    @Test
+    void testAddFirst() {
+        Deque<Integer> deque = new Deque<>();
+        deque.addFirst(10);
+        assertEquals(10, deque.peekFirst());
+        assertEquals(10, deque.peekLast());
+        assertEquals(1, deque.size());
+    }
+
+    @Test
+    void testAddLast() {
+        Deque<Integer> deque = new Deque<>();
+        deque.addLast(20);
+        assertEquals(20, deque.peekFirst());
+        assertEquals(20, deque.peekLast());
+        assertEquals(1, deque.size());
+    }
+
+    @Test
+    void testPollFirst() {
+        Deque<Integer> deque = new Deque<>();
+        deque.addFirst(10);
+        deque.addLast(20);
+        assertEquals(10, deque.pollFirst());
+        assertEquals(20, deque.peekFirst());
+        assertEquals(1, deque.size());
+    }
+
+    @Test
+    void testPollLast() {
+        Deque<Integer> deque = new Deque<>();
+        deque.addFirst(10);
+        deque.addLast(20);
+        assertEquals(20, deque.pollLast());
+        assertEquals(10, deque.peekLast());
+        assertEquals(1, deque.size());
+    }
+
+    @Test
+    void testIsEmpty() {
+        Deque<Integer> deque = new Deque<>();
+        org.junit.jupiter.api.Assertions.assertTrue(deque.isEmpty());
+        deque.addFirst(10);
+        assertFalse(deque.isEmpty());
+    }
+
+    @Test
+    void testPeekFirstEmpty() {
+        Deque<Integer> deque = new Deque<>();
+        assertNull(deque.peekFirst());
+    }
+
+    @Test
+    void testPeekLastEmpty() {
+        Deque<Integer> deque = new Deque<>();
+        assertNull(deque.peekLast());
+    }
+
+    @Test
+    void testPollFirstEmpty() {
+        Deque<Integer> deque = new Deque<>();
+        org.junit.jupiter.api.Assertions.assertThrows(NoSuchElementException.class, deque::pollFirst);
+    }
+
+    @Test
+    void testPollLastEmpty() {
+        Deque<Integer> deque = new Deque<>();
+        org.junit.jupiter.api.Assertions.assertThrows(NoSuchElementException.class, deque::pollLast);
+    }
+
+    @Test
+    void testToString() {
+        Deque<Integer> deque = new Deque<>();
+        deque.addFirst(10);
+        deque.addLast(20);
+        deque.addFirst(5);
+        assertEquals("Head -> 5 <-> 10 <-> 20 <- Tail", deque.toString());
+    }
+}