Question

This is a java problem. Complete and only modify ArrayQueue.java and CircularLinkedQueue.java.

Use Homework3Driver.java to test correctness of implementation of both.

This package includes Homework3Driver.java, QueueInterface.java, QueueOverflowException.java, QueueUnderflowException.java, and LLNode.java Do NOT modify any of those files.

The final output should be:

"For ArrayQueue.java, you get 30/30
For CircularLinkedQueue.java, you get 20/20
Your final score is 50/50"

This is ArrayQueue.java (the one that should be modified):

public class ArrayQueue<T> implements QueueInterface<T> {
   private static int CAPACITY = 100;
   private T[] elements;
   private int rearIndex = -1;

   // Default constructor to initialize array capacity with CAPACITY
   public ArrayQueue() {
   }

   // Constructor to initialize array capacity with 'size'
   @SuppressWarnings("unchecked")
   public ArrayQueue(int size) {
   }

   // Dequeue info from array. Throw QueueUnderflowException if array is empty
   public T dequeue() {
   }

   // Enqueue info into array. Throw QueueOverflowException if array is full
   public void enqueue(T info) {
   }

   // Return true if the array is empty; otherwise return false
   public boolean isEmpty() {
   }

   // Return true if the array is full; otherwise return false
   public boolean isFull() {
   }

   // Return number of elements
   public int size() {
   }
  
   // Adjust elements array capacity with 'size'
   public void resize(int size) {
   }
  
   // Return array capacity
   public int getQueueCapacity() {
   }
}

This is CircularLinkedQueue.java (The one that should also be modified):

// Note: It is important to implement this file as a circular queue without 'front' pointer

public class CircularLinkedQueue<T> implements QueueInterface<T> {
   protected LLNode<T> rear; // reference to the rear of this queue
   protected int numElements = 0; // number of elements in this queue

   public CircularLinkedQueue() {
   }

   public void enqueue(T element)
   // Adds element to the rear of this queue.
   {
   }

   public T dequeue()
   // Throws QueueUnderflowException if this queue is empty;
   // otherwise, removes front element from this queue and returns it.
   {
   }

   public String toString() {
       String result = "";

       return result;
   }

   public boolean isEmpty()
   // Returns true if this queue is empty; otherwise, returns false.
   {
   }

   public boolean isFull()
   // Returns false - a linked queue is never full.
   {
   }

   public int size()
   // Returns the number of elements in this queue.
   {
   }

}

This is Homework3Driver.java (the one to use to test the implementation of ArrayQueue.java and CircularLinkedQueue.java. Do not modify this file):

public class Homework3Driver {
  
   public static void main(String[] args) {
       int score = 0;

       // Part 1: Array Based queue
       score += testArrayQueue();
       System.out.printf("For ArrayQueue.java, you get %d/30\n", testArrayQueue());
      
       // Part 2: Circular Queue
       score += testCircularLinkedQueue();
       System.out.printf("For CircularLinkedQueue.java, you get %d/20\n", testCircularLinkedQueue());

       System.out.printf("Your final score is %d/50 \n", score);
   }
  
   private static int testArrayQueue() {
       int score = 0;

       ArrayQueue<Character> c = new ArrayQueue<Character>();
       if (c.getQueueCapacity() == 100)
           score += 1;

       ArrayQueue<String> q = new ArrayQueue<String>(2);
       if (q.getQueueCapacity() == 2)
           score += 1;

       try {
           q.dequeue(); // Note: Underflow exception should occur
       } catch (Exception e) {
           score += 3;
       }

       if (q.isEmpty() && !q.isFull() && q.size() == 0)
           score += 5;

       q.enqueue("Orange");
       q.enqueue("Mango");

       try {
           q.enqueue("Guava"); // Note: with Queue size 2, this won't get into the queue.
       } catch (Exception e) {
           score += 3;
       }

       if (q.isFull())
           score += 2;

       if (q.dequeue().equals("Orange") && q.size() == 1 && !q.isEmpty())
           score += 3;

       if (q.dequeue().equals("Mango") && q.size() == 0 && q.isEmpty())
           score += 2;

       q.enqueue("Strawberry");
       q.enqueue("Lemon");
       q.resize(2); // Increase the array size by 2
       q.enqueue("Banana");
       if (q.getQueueCapacity() == 4 && q.size() == 3 && !q.isEmpty() && !q.isFull())
           score += 5;

       q.resize(-1); // Decrease the array size by 1.
       if (q.getQueueCapacity() == 3 && q.size() == 3 && !q.isEmpty() && q.isFull())
           score += 5;

       return score;
   }
  
   private static int testCircularLinkedQueue() {
       int score = 0;
      
       CircularLinkedQueue<String> cq = new CircularLinkedQueue<String>();
      
       try {
           System.out.println(cq.dequeue());
       } catch (Exception e) {
           if (cq.size() == 0 && cq.isEmpty() && !cq.isFull())
           score += 5;
       }
      
       cq.enqueue("Tomato");
       cq.enqueue("Grape");
       if (cq.size() == 2 && !cq.isEmpty() && !cq.isFull())
           score += 5;

       cq.dequeue();      
       cq.dequeue();
       if (cq.size() == 0 && cq.isEmpty() && !cq.isFull())
           score += 5;
      
       cq.enqueue("Pineapple");
       cq.enqueue("Lime");
      
//       System.out.println(cq);
       // Note: Implement toString() method to match this output.
       if (cq.toString().equals("Pineapple\nLime\n"))
           score += 5;

       return score;
   }
}

This is QueueInterface.java (Do not modify):

public interface QueueInterface<T> {
   void enqueue(T element) throws QueueOverflowException;
   // Throws QueueOverflowException if this queue is full;
   // otherwise, adds element to the rear of this queue.

   T dequeue() throws QueueUnderflowException;
   // Throws QueueUnderflowException if this queue is empty;
   // otherwise, removes front element from this queue and returns it.

   boolean isFull();
   // Returns true if this queue is full; otherwise, returns false.

   boolean isEmpty();
   // Returns true if this queue is empty; otherwise, returns false.

   int size();
   // Returns the number of elements in this queue.
}

This is LLNode.java (do not modify):

public class LLNode<T> {
   protected LLNode<T> link;
   protected T info;

   public LLNode(T info) {
       this.info = info;
       link = null;
   }

   public void setInfo(T info) {
       this.info = info;
   }

   public T getInfo() {
       return info;
   }

   public void setLink(LLNode<T> link) {
       this.link = link;
   }

   public LLNode<T> getLink() {
       return link;
   }
}

This is QueueOverflowException.java (do not modify):

public class QueueOverflowException extends RuntimeException {
   private static final long serialVersionUID = 1L;

   public QueueOverflowException() {
       super();
   }

   public QueueOverflowException(String message) {
       super(message);
   }
}

This is QueueUnderflowException.java (do not modify):

public class QueueUnderflowException extends RuntimeException {
   private static final long serialVersionUID = 1L;

   public QueueUnderflowException() {
       super();
   }

   public QueueUnderflowException(String message) {
       super(message);
   }
}

Answer 1

Here is the complete code,

ArrayQueue.java

public class ArrayQueue<T> implements QueueInterface<T> {
    private static int CAPACITY = 100;
    private T[] elements;
    private int rearIndex = -1;

    // Default constructor to initialize array capacity with CAPACITY
    public ArrayQueue() {
        CAPACITY = 100;
        elements = (T[]) new Object[CAPACITY];
    }

    // Constructor to initialize array capacity with 'size'
    @SuppressWarnings("unchecked")
    public ArrayQueue(int size) {
        CAPACITY = size;
        elements = (T[]) new Object[size];
    }

    // Dequeue info from array. Throw QueueUnderflowException if array is empty
    public T dequeue() {
        if(isEmpty()) throw new QueueUnderflowException("Queue is Empty");
        T value;
        if(size() == 1){
            value = elements[rearIndex];
            elements[rearIndex] = null;
        }
        else{
            value = elements[0];
            for(int i=0; i<size()-1; i++){
                elements[i] = elements[i+1];
            }
            elements[size()-1] = null;
        }
        rearIndex--;
        return value;
    }

    // Enqueue info into array. Throw QueueOverflowException if array is full
    public void enqueue(T info) {
        if(isFull()) throw new QueueOverflowException("Queue is Full");
        rearIndex++;
        elements[rearIndex] = info;
    }

    // Return true if the array is empty; otherwise return false
    public boolean isEmpty() {
        return rearIndex == -1;
    }

    // Return true if the array is full; otherwise return false
    public boolean isFull() {
        return rearIndex+1 == CAPACITY;
    }

    // Return number of elements
    public int size() {
        return rearIndex+1;
    }

    // Adjust elements array capacity with 'size'
    public void resize(int size) {
        int newCapacity = getQueueCapacity() + size;
        T[] newElements = (T[]) new Object[newCapacity];
        if (size() >= 0) System.arraycopy(elements, 0, newElements, 0, size());
        CAPACITY = newCapacity;
        elements = newElements;
    }

    // Return array capacity
    public int getQueueCapacity() {
        return CAPACITY;
    }
}

CircularLinkedQueue.java

// Note: It is important to implement this file as a circular queue without 'front' pointer

public class CircularLinkedQueue<T> implements QueueInterface<T> {
    protected LLNode<T> rear; // reference to the rear of this queue
    protected int numElements = 0; // number of elements in this queue

    public CircularLinkedQueue() {
        rear = null;
    }

    public void enqueue(T element)
    // Adds element to the rear of this queue.
    {
        if(rear == null){
            rear = new LLNode<>(element);
            rear.link = rear;
        }
        else{
            LLNode<T> temp = rear;
            LLNode<T> end = rear.getLink();
            rear = new LLNode<>(element);
            temp.link = rear;
            rear.link = end;
        }
        numElements++;
    }

    public T dequeue()
    // Throws QueueUnderflowException if this queue is empty;
    // otherwise, removes front element from this queue and returns it.
    {
        if(isEmpty()) throw new QueueOverflowException("Queue is Empty.");
        LLNode<T> removedNode;
        if(size() == 1){
            removedNode = rear;
            rear = null;
        }
        else{
            removedNode = rear.getLink();
            rear.link = removedNode.getLink();
        }
        numElements--;
        return removedNode.getInfo();
    }

    public String toString() {
        StringBuilder result = new StringBuilder();
        if(isEmpty()) return result.toString();
        LLNode<T> front = rear.getLink();
        while(front != rear){
            result.append(front.getInfo()+"\n");
            front = front.getLink();
        }
        result.append(front.getInfo()+"\n");
        return result.toString();
    }

    public boolean isEmpty()
    // Returns true if this queue is empty; otherwise, returns false.
    {
        return rear == null;
    }

    public boolean isFull()
    // Returns false - a linked queue is never full.
    {
        return false;
    }

    public int size()
    // Returns the number of elements in this queue.
    {
        return numElements;
    }

}

Homework3Driver.java

public class Homework3Driver {

    public static void main(String[] args) {
        int score = 0;

        // Part 1: Array Based queue
        score += testArrayQueue();
        System.out.printf("For ArrayQueue.java, you get %d/30\n", testArrayQueue());

        // Part 2: Circular Queue
        score += testCircularLinkedQueue();
        System.out.printf("For CircularLinkedQueue.java, you get %d/20\n", testCircularLinkedQueue());

        System.out.printf("Your final score is %d/50 \n", score);
    }

    private static int testArrayQueue() {
        int score = 0;

        ArrayQueue<Character> c = new ArrayQueue<Character>();
        if (c.getQueueCapacity() == 100)
            score += 1;

        ArrayQueue<String> q = new ArrayQueue<String>(2);
        if (q.getQueueCapacity() == 2)
            score += 1;

        try {
            q.dequeue(); // Note: Underflow exception should occur
        } catch (Exception e) {
            score += 3;
        }

        if (q.isEmpty() && !q.isFull() && q.size() == 0)
            score += 5;

        q.enqueue("Orange");
        q.enqueue("Mango");

        try {
            q.enqueue("Guava"); // Note: with Queue size 2, this won't get into the queue.
        } catch (Exception e) {
            score += 3;
        }

        if (q.isFull())
            score += 2;

        if (q.dequeue().equals("Orange") && q.size() == 1 && !q.isEmpty())
            score += 3;

        if (q.dequeue().equals("Mango") && q.size() == 0 && q.isEmpty())
            score += 2;

        q.enqueue("Strawberry");
        q.enqueue("Lemon");
        q.resize(2); // Increase the array size by 2
        q.enqueue("Banana");
        if (q.getQueueCapacity() == 4 && q.size() == 3 && !q.isEmpty() && !q.isFull())
            score += 5;

        q.resize(-1); // Decrease the array size by 1.
        if (q.getQueueCapacity() == 3 && q.size() == 3 && !q.isEmpty() && q.isFull())
            score += 5;

        return score;
    }

    private static int testCircularLinkedQueue() {
        int score = 0;

        CircularLinkedQueue<String> cq = new CircularLinkedQueue<String>();

        try {
            System.out.println(cq.dequeue());
        } catch (Exception e) {
            if (cq.size() == 0 && cq.isEmpty() && !cq.isFull())
                score += 5;
        }

        cq.enqueue("Tomato");
        cq.enqueue("Grape");
        if (cq.size() == 2 && !cq.isEmpty() && !cq.isFull())
            score += 5;

        cq.dequeue();
        cq.dequeue();
        if (cq.size() == 0 && cq.isEmpty() && !cq.isFull())
            score += 5;

        cq.enqueue("Pineapple");
        cq.enqueue("Lime");

//       System.out.println(cq);
        // Note: Implement toString() method to match this output.
        if (cq.toString().equals("Pineapple\nLime\n"))
            score += 5;

        return score;
    }
}

LLNode.java

public class LLNode<T> {
    protected LLNode<T> link;
    protected T info;

    public LLNode(T info) {
        this.info = info;
        link = null;
    }

    public void setInfo(T info) {
        this.info = info;
    }

    public T getInfo() {
        return info;
    }

    public void setLink(LLNode<T> link) {
        this.link = link;
    }

    public LLNode<T> getLink() {
        return link;
    }
}

QueueInterface.java

public interface QueueInterface<T> {
    void enqueue(T element) throws QueueOverflowException;
    // Throws QueueOverflowException if this queue is full;
    // otherwise, adds element to the rear of this queue.

    T dequeue() throws QueueUnderflowException;
    // Throws QueueUnderflowException if this queue is empty;
    // otherwise, removes front element from this queue and returns it.

    boolean isFull();
    // Returns true if this queue is full; otherwise, returns false.

    boolean isEmpty();
    // Returns true if this queue is empty; otherwise, returns false.

    int size();
    // Returns the number of elements in this queue.
}

QueueOverflowException.java

public class QueueOverflowException extends RuntimeException {
    private static final long serialVersionUID = 1L;

    public QueueOverflowException() {
        super();
    }

    public QueueOverflowException(String message) {
        super(message);
    }
}

QueueUnderflowException.java

public class QueueUnderflowException extends RuntimeException {
    private static final long serialVersionUID = 1L;

    public QueueUnderflowException() {
        super();
    }

    public QueueUnderflowException(String message) {
        super(message);
    }
}

OUTPUT

If you have any doubts feel free to ask in comment section. Also please do upvote the solution.