Algorithms-I : 2-Randomized_Queues_Deques: add Deque.java

1 files changed, 118 insertions, 0 deletions

diff --git a/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java b/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java
new file mode 100644
index 0000000..e8a17de
--- /dev/null
+++ b/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java
@@ -0,0 +1,118 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+import java.util.Iterator;
+
+public class Deque<Item> implements Iterable<Item>
+{
+    private Node head;
+    private Node tail;
+    private int n;
+
+    private class Node
+    {
+        Item item;
+        Node next;
+        Node prev;
+    }
+
+    // construct an empty deque
+    public Deque()
+    {
+        head = null;
+        tail = null;
+        n = 0;
+    }
+
+    // is the deque empty?
+    public boolean isEmpty()
+    {
+        return (head == null);
+    }
+
+    // return the number of items on the deque
+    public int size()
+    {
+        return n;
+    }
+
+    // insert the item at the front
+    public void addFirst(Item item)
+    {
+        if (item == null) throw new java.lang.NullPointerException();
+        Node node = new Node();
+        node.item = item;
+        node.next = head;
+        node.prev = null;
+        head = node;
+        if (tail == null) tail = head;
+        n++;
+    }
+
+    // insert the item at the end
+    public void addLast(Item item)
+    {
+        if (item == null) throw new java.lang.NullPointerException();
+        Node node = new Node();
+        node.item = item;
+        node.next = null;
+        node.prev = tail;
+        if (tail == null)
+        {
+            head = tail = node;
+        }
+        else
+        {
+            tail.next = node;
+            tail = tail.next;
+        }
+        n++;
+    }
+
+    // delete and return the item at the front
+    public Item removeFirst()
+    {
+        if (head == null) throw new java.util.NoSuchElementException();
+        Item item = head.item;
+        if (tail == head) tail = tail.next;
+        head = head.next;
+        head.prev = null;
+        n--;
+        return item;
+    }
+
+    // delete and return the item at the end
+    public Item removeLast()
+    {
+        if (tail == null) throw new java.util.NoSuchElementException();
+        Item item = tail.item;
+        if (head == tail)
+        {
+            head = tail = null;
+        }
+        else
+        {
+            tail = tail.prev;
+            tail.next = null;
+        }
+        n--;
+        return item;
+    }
+
+    // return an iterator over items in order from front to end
+    public Iterator<Item> iterator() { return new DequeIterator(); }
+
+    private class DequeIterator implements Iterator<Item>
+    {
+        private Node current = head;
+
+        public boolean hasNext() { return current != null; }
+        public void remove() { throw new java.lang.UnsupportedOperationException(); }
+        public Item next()
+        {
+            if (current == null) throw new java.util.NoSuchElementException();
+            Item item = current.item;
+            current = current.next;
+            return item;
+        }
+    }
+}