Merge pull request TheAlgorithms#712 from AnkitAtBrillio/local

yanglbme · web-flow · commit 7f523ffee8df · 2019-03-06T09:00:04.000+08:00
Adding Linked List based General queue implementation
diff --git a/src/main/java/com/dataStructures/GeneralQueue.java b/src/main/java/com/dataStructures/GeneralQueue.java
@@ -0,0 +1,136 @@
+package src.main.java.com.dataStructures;
+
+import src.main.java.com.types.Queue;
+
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.NoSuchElementException;
+
+/**
+ * linkedList based implementation of queue.
+ * This implementation is not thread safe and need exclusive thread safety measures from the client.
+ *
+ * @param <T>
+ */
+public class GeneralQueue<T> implements Queue<T> {
+
+    private LinkedList<T> queue;
+    private Iterator<T> itr;
+
+    /**
+     * Overloaded constructor to create queue of specific size
+     */
+    public GeneralQueue() {
+        queue = new LinkedList<>();
+    }
+
+    @Override
+    public boolean add(T t) {
+
+        if (queue == null) {
+            throw new IllegalStateException();
+        }
+        if (t == null) {
+            throw new NullPointerException();
+        }
+        queue.add(t);
+        return true;
+    }
+
+    @Override
+    public boolean remove(T t) {
+        if (null == queue) {
+            throw new NullPointerException();
+        }
+        if (queue.isEmpty()) {
+            throw new NoSuchElementException();
+        }
+        queue.remove(t);
+        return true;
+    }
+
+    @Override
+    public boolean isEmpty() {
+        return null == queue || queue.size() == 0;
+    }
+
+    @Override
+    public Iterator<T> iterator() {
+        if (queue == null) {
+            return null;
+        }
+        itr = queue.iterator();
+        return itr;
+    }
+
+    @Override
+    public boolean offer(T t) {
+        if (null == queue) {
+            return false;
+        }
+        if (t == null) {
+            throw new NullPointerException();
+        }
+        queue.add(t);
+        return true;
+    }
+
+    @Override
+    public T poll() {
+        if (queue == null || queue.isEmpty()) {
+            return null;
+        }
+
+        return queue.pollFirst();
+    }
+
+    @Override
+    public T element() {
+        if (queue == null || queue.isEmpty()) {
+            throw new NoSuchElementException();
+        }
+
+        return queue.peekFirst();
+    }
+
+    @Override
+    public T peek() {
+        if (null == queue || queue.size() == 0) {
+            return null;
+        }
+
+        return queue.peekFirst();
+    }
+
+    @Override
+    public boolean hasNext() {
+        return itr.hasNext();
+    }
+
+    @Override
+    public T next() {
+        return itr.next();
+    }
+
+    @Override
+    public Object[] toArray() {
+        Object[] elements = {};
+        if (null == queue || queue.isEmpty()) {
+            return elements;
+        }
+        elements = new Object[queue.size()];
+        for (int i = 0; i < queue.size(); i++) {
+            elements[i] = queue.get(i);
+        }
+
+        return elements;
+    }
+
+    @Override
+    public int size() {
+        if (null == queue || queue.isEmpty()) {
+            return 0;
+        }
+        return queue.size();
+    }
+}
diff --git a/src/main/java/com/types/DataStructure.java b/src/main/java/com/types/DataStructure.java
@@ -0,0 +1,57 @@
+package src.main.java.com.types;
+
+import java.util.Iterator;
+
+/**
+ * This interface is to define bacis functionality expected out of any implementation class
+ * Since this is a data structure it should have the flexibility to contain any kind of object hence it has been made generic
+ * Any implementation class need not to be thread safe or it could be depending on the implementation class how does it want to behave.
+ *
+ * @param <T>
+ */
+public interface DataStructure<T> extends Iterator<T> {
+
+    /**
+     * Method to add element in the structure
+     *
+     * @param t element
+     * @return boolean
+     */
+    boolean add(T t);
+
+    /**
+     * Method to remove the given object from structure
+     *
+     * @param o element
+     * @return boolean
+     */
+    boolean remove(T o);
+
+    /**
+     * Method to get Iterator to parse on the given structure
+     *
+     * @return iterator
+     */
+    Iterator<T> iterator();
+
+    /**
+     * Method to check if structure is empty
+     *
+     * @return boolean
+     */
+    boolean isEmpty();
+
+    /**
+     * Method to get all the elements of data structure in array
+     *
+     * @return arr
+     */
+    Object[] toArray();
+
+    /**
+     * Method to get the size or number of elements in structure
+     *
+     * @return size
+     */
+    int size();
+}
diff --git a/src/main/java/com/types/Queue.java b/src/main/java/com/types/Queue.java
@@ -0,0 +1,45 @@
+package src.main.java.com.types;
+
+
+import java.util.NoSuchElementException;
+
+/**
+ * Interface to provide queue specific functionality to the implementing class
+ * This interface only defines the functionality which the queue implementing classes require.
+ * Any class having queue behaviour should implement this interface and override all of its methods
+ *
+ * @param <T>
+ */
+public interface Queue<T> extends DataStructure<T> {
+
+    /**
+     * Method to add element
+     *
+     * @param t element
+     * @return boolean
+     * @throws NullPointerException
+     */
+    boolean offer(T t) throws NullPointerException;
+
+    /**
+     * Method to remove element
+     *
+     * @return element
+     */
+    T poll();
+
+    /**
+     * Method to check element on head
+     *
+     * @return element
+     */
+    T peek();
+
+    /**
+     * Method to check element on head. This throws exception on runtime if the queue is empty
+     *
+     * @return element
+     * @throws NoSuchElementException
+     */
+    T element() throws NoSuchElementException;
+}
diff --git a/src/test/java/com/dataStructures/GeneralQueueTest.java b/src/test/java/com/dataStructures/GeneralQueueTest.java
@@ -0,0 +1,45 @@
+package src.test.java.com.dataStructures;
+
+
+import org.junit.Assert;
+import org.junit.Test;
+import src.main.java.com.dataStructures.GeneralQueue;
+import src.main.java.com.types.Queue;
+
+public class GeneralQueueTest {
+
+    @Test
+    public void testGeneralQueue() {
+
+        Queue<Integer> myQueue = new GeneralQueue<>();
+        myQueue.add(10);
+        myQueue.add(20);
+        myQueue.add(30);
+        myQueue.add(40);
+        myQueue.add(50);
+
+
+        Object[] myArray =  myQueue.toArray();
+        Assert.assertEquals(myArray.length, myQueue.size());
+
+        myQueue.remove(20);
+        Assert.assertEquals(myQueue.size(), 4);
+
+        Boolean isEmpty = myQueue.isEmpty();
+        Assert.assertEquals(Boolean.valueOf("false"), Boolean.valueOf(isEmpty));
+
+        myQueue.offer(60);
+        Assert.assertEquals(5, myQueue.size());
+
+        int polledElement = myQueue.poll();
+        Assert.assertEquals(10, polledElement);
+
+        int element = myQueue.element();
+        Assert.assertEquals(30, element);
+
+        myQueue.poll();
+        int peekedElement = myQueue.peek();
+        Assert.assertEquals(40, peekedElement);
+
+    }
+}
