Add Queue implementations

Lord-of-Algorithms · Lord-of-Algorithms · commit 84ca022172b9 · 2024-07-23T13:56:25.000+03:00
diff --git a/src/lineards/queue/DynamicArrayQueue.java b/src/lineards/queue/DynamicArrayQueue.java
@@ -0,0 +1,95 @@
+package lineards.queue;
+
+import java.util.NoSuchElementException;
+
+/**
+ * Implements a queue that automatically adjusts its capacity based on the number of elements.
+ */
+public class DynamicArrayQueue implements Queue {
+    private char[] data;
+    private int front;
+    private int rear;
+    private int size;
+
+    public DynamicArrayQueue(int capacity) {
+        if (capacity < 1) {
+            throw new IllegalArgumentException("Capacity must be at least 1");
+        }
+        data = new char[capacity];
+        front = 0;
+        rear = -1;
+        size = 0;
+    }
+
+    /**
+     * Checks if the queue is empty.
+     *
+     * @return true if the queue has no elements, false otherwise.
+     */
+    public boolean isEmpty() {
+        return size == 0;
+    }
+
+    /**
+     * Adds a character to the rear of the queue. Resizes if full.
+     *
+     * @param value The character to add.
+     */
+    public void enqueue(char value) {
+        if (size == data.length) {
+            // Double the size of the array when
+            // the queue is full
+            resize(2 * data.length);
+        }
+        rear = (rear + 1) % data.length;
+        data[rear] = value;
+        size++;
+    }
+
+    /**
+     * Removes and returns the character at the front of the queue.
+     *
+     * @return The character at the front of the queue.
+     * @throws NoSuchElementException if the queue is empty.
+     */
+    public char dequeue() {
+        if (isEmpty()) {
+            throw new NoSuchElementException("Queue is empty");
+        }
+        char value = data[front];
+        front = (front + 1) % data.length;
+        size--;
+
+        // Reduce the size of the array when the queue is 1/4 full
+        if (size > 0 && size == data.length / 4) {
+            resize(Math.max(data.length / 2, 10)); // Ensure the capacity doesn't get too small
+        }
+
+        return value;
+    }
+
+    /**
+     * Returns the character at the front of the queue without removing it.
+     */
+    public char peek() {
+        if (isEmpty()) {
+            throw new NoSuchElementException("Queue is empty");
+        }
+        return data[front];
+    }
+
+    /**
+     * Resizes the underlying array holding the elements of the queue.
+     *
+     * @param newCapacity The new capacity for the queue.
+     */
+    private void resize(int newCapacity) {
+        char[] newData = new char[newCapacity];
+        for (int i = 0; i < size; i++) {
+            newData[i] = data[(front + i) % data.length];
+        }
+        data = newData;
+        front = 0;
+        rear = size - 1;
+    }
+}
diff --git a/src/lineards/queue/LinkedListQueue.java b/src/lineards/queue/LinkedListQueue.java
@@ -0,0 +1,77 @@
+package lineards.queue;
+
+import java.util.NoSuchElementException;
+
+/**
+ * A queue implementation using a singly linked list. This implementation allows for dynamic
+ * memory allocation, growing as needed based on the queue's usage. It does not impose a fixed capacity.
+ */
+public class LinkedListQueue implements Queue {
+
+    /**
+     * Node in a linked list, holding a character and a reference to the next node.
+     */
+    private static class Node {
+        final char data;
+        Node next;
+
+        Node(char data) {
+            this.data = data;
+        }
+    }
+
+    private Node front;
+    private Node rear;
+
+    /**
+     * Checks if the queue is empty.
+     *
+     * @return true if the queue has no elements, false otherwise.
+     */
+    public boolean isEmpty() {
+        return front == null;
+    }
+
+    /**
+     * Adds a character to the rear of the queue.
+     *
+     * @param value The character to add.
+     */
+    public void enqueue(char value) {
+        Node newNode = new Node(value);
+        if (isEmpty()) {
+            front = newNode;
+        } else {
+            rear.next = newNode;
+        }
+        rear = newNode;
+    }
+
+    /**
+     * Removes and returns the character at the front of the queue.
+     *
+     * @return The character at the front of the queue.
+     * @throws NoSuchElementException if the queue is empty.
+     */
+    public char dequeue() {
+        if (isEmpty()) {
+            throw new NoSuchElementException("Queue is empty");
+        }
+        char data = front.data;
+        front = front.next;
+        if (front == null) {
+            rear = null;
+        }
+        return data;
+    }
+
+    /**
+     * Returns the character at the front of the queue without removing it.
+     */
+    public char peek() {
+        if (isEmpty()) {
+            throw new NoSuchElementException("Queue is empty");
+        }
+        return front.data;
+    }
+}
diff --git a/src/lineards/queue/Queue.java b/src/lineards/queue/Queue.java
@@ -0,0 +1,35 @@
+package lineards.queue;
+
+import java.util.NoSuchElementException;
+
+/**
+ * Defines the interface for a queue.
+ */
+interface Queue {
+    /**
+     * Checks if the queue is empty.
+     *
+     * @return true if the queue has no elements, false otherwise.
+     */
+    boolean isEmpty();
+
+    /**
+     * Adds a character to the rear of the queue.
+     *
+     * @param value The character to add.
+     */
+    void enqueue(char value);
+
+    /**
+     * Removes and returns the character at the front of the queue.
+     *
+     * @return The character at the front of the queue.
+     * @throws NoSuchElementException if the queue is empty.
+     */
+    char dequeue();
+
+    /**
+     * Returns the character at the front of the queue without removing it.
+     */
+    char peek();
+}
diff --git a/src/lineards/queue/QueueMain.java b/src/lineards/queue/QueueMain.java
@@ -0,0 +1,49 @@
+package lineards.queue;
+
+/**
+ * Demonstrates the functionalities of different queue implementations.
+ */
+public class QueueMain {
+
+    public static void main(String[] args) {
+        // Demo for StaticArrayQueue
+        System.out.println("Static Array Queue Demo:");
+        StaticArrayQueue staticQueue = new StaticArrayQueue(5);
+        demoQueue(staticQueue);
+
+        // Demo for DynamicArrayQueue
+        System.out.println("\nDynamic Array Queue Demo:");
+        DynamicArrayQueue dynamicQueue = new DynamicArrayQueue(5);
+        demoQueue(dynamicQueue);
+
+        // Demo for LinkedListQueue
+        System.out.println("\nLinked List Queue Demo:");
+        LinkedListQueue linkedListQueue = new LinkedListQueue();
+        demoQueue(linkedListQueue);
+    }
+
+    /**
+     * Demonstrates basic queue operations like enqueue, dequeue, and peek on a queue.
+     *
+     * @param queue The queue to demonstrate.
+     */
+    private static void demoQueue(Queue queue) {
+        try {
+            queue.enqueue('A');
+            queue.enqueue('B');
+            queue.enqueue('C');
+            System.out.println("Enqueuing A, B, and C...");
+            System.out.println("Peek: " + queue.peek());
+            System.out.println("Dequeue: " + queue.dequeue());
+            System.out.println("Peek: " + queue.peek());
+            System.out.println("Dequeue: " + queue.dequeue());
+            System.out.println("Peek: " + queue.peek());
+            System.out.println("Empty: " + queue.isEmpty());
+            System.out.println("Dequeue: " + queue.dequeue());
+            System.out.println("Empty: " + queue.isEmpty());
+
+        } catch (Exception e) {
+            System.out.println(e.getMessage());
+        }
+    }
+}
diff --git a/src/lineards/queue/StaticArrayQueue.java b/src/lineards/queue/StaticArrayQueue.java
@@ -0,0 +1,87 @@
+package lineards.queue;
+
+import java.util.NoSuchElementException;
+
+/**
+ * Represents a fixed-size queue implemented using a static array.
+ * The queue uses a circular array mechanism to manage elements without
+ * shifting them physically in the array. This allows for O(1) complexity for enqueue
+ * and dequeue operations.
+ */
+public class StaticArrayQueue implements Queue {
+    private final char[] data; // Array to store queue elements.
+    private int front;
+    private int rear;
+    private int size;
+
+    /**
+     * Constructs a new Queue with a specified capacity.
+     */
+    public StaticArrayQueue(int capacity) {
+        if (capacity < 1) {
+            throw new IllegalArgumentException("Capacity must be at least 1");
+        }
+        data = new char[capacity];
+        front = 0;
+        rear = -1;
+        size = 0;
+    }
+
+    /**
+     * Checks if the queue is empty.
+     *
+     * @return true if the queue has no elements, false otherwise.
+     */
+    public boolean isEmpty() {
+        return size == 0;
+    }
+
+    /**
+     * Checks if the queue is full.
+     *
+     * @return true if the queue has reached its current capacity, false otherwise.
+     */
+    public boolean isFull() {
+        return size == data.length;
+    }
+
+    /**
+     * Adds a character to the rear of the queue.
+     *
+     * @param value The character to add.
+     */
+    public void enqueue(char value) {
+        if (isFull()) {
+            throw new IllegalStateException("Queue is full");
+        }
+        rear = (rear + 1) % data.length;
+        data[rear] = value;
+        size++;
+    }
+
+    /**
+     * Removes and returns the character at the front of the queue.
+     *
+     * @return The character at the front of the queue.
+     * @throws NoSuchElementException if the queue is empty.
+     */
+    public char dequeue() {
+        if (isEmpty()) {
+            throw new NoSuchElementException("Queue is empty");
+        }
+        char value = data[front];
+        front = (front + 1) % data.length;
+        size--;
+        return value;
+    }
+
+    /**
+     * Returns the character at the front of the queue without removing it.
+     */
+    public char peek() {
+        if (isEmpty()) {
+            throw new NoSuchElementException("Queue is empty");
+        }
+        return data[front];
+    }
+}
