JAVA

Array-Based Circular Queue Data Structures | Circular Queue Implementation Create a class called CircularQueue with the following instance variables: queue: a reference to an array holding elements in the queue front: the index directly before the front (first element) of the queue rear: the index of the last element that was added to the queue DEFAULT_CAPACITY: the default capacity of the queue public class CircularQueue { private E[] queue; private int front = 0, rear = 0; private static final int DEFAULT_CAPACITY = 5; } Add a constructor that will initialize the internal array to a specified capacity. Recall that one location in the array stays empty, and so the size of the array will need to be 1 element larger than the specified capacity. public CircularQueue(int capacity) { queue = (E[]) new Object[capacity + 1]; } Another constructor takes no parameters and sets the capacity of the data array to the default value: public CircularQueue() { this(DEFAULT_CAPACITY); } Add a method that will determine if the queue is empty. Recall that the queue is empty if the front and rear index the same location in the array: public boolean isEmpty() { return __________ == __________; } Add a method that will determine if the queue is full. This method will be used internally to determine if the array needs to be expanded. The queue is full if moving the rear forward (enqueue) will result in the rear and front indexing the same location in the array. private boolean isFull() { return ((rear + 1) % queue.length) == front; } Data Structures Array-Based Circular Queue Data Structures | Circular Queue 6 When elements are added (enqueue), they are added to the the rear of the queue and the rear index is moved forward. Add an enqueue method to add an element to the queue: public void enqueue(E newElement) { } First, you'll have to expand the internal array if the queue is full. Because there is not yet an expand method, comment the line out for now: if (isFull()) { // this.expand(); } To add an element to the rear of the queue, move the rear index up and add the element to the rear location in the queue: rear = (rear + 1) % queue.length; queue[__________] = newElement; Answer the following questions and then use the interactions pane and viewer to verify your answers. If the initial capacity is set to 5, what will be the size of the internal array? Suppose that 2 elements 87 & 44 are added to the queue. Where will they be placed in the array? What will be the value of front and rear after the above 2 enqueue operations? What about after 3 enqueue operations? In the interactions pane, add 4 elements to q1. Open a viewer on q1 after the first line is executed. CircularQueue q1 = new CircularQueue(); q1.enqueue(87); q1.enqueue(44); q1.enqueue(15); q1.enqueue(9); Create a dequeue method that will remove and return an element from the queue. public E dequeue() { } The method should throw an NoSuchElementException (you'll need to import the java.util package) if the queue is empty. if (isEmpty()) { throw new NoSuchElementException("Queue is empty."); } Data Structures Array-Based Circular Queue Data Structures | Circular Queue 7 If not, move the front index forward to the front element and create a reference to the element at that location: front = (front + 1) % queue.length; E frontElement = queue[front]; Delete the reference at the front index (1 before the next front element) and return the previous front element: queue[front] = null; return frontElement; Answer the following questions and then use the interactions pane and viewer to verify your answers. Suppose that 2 elements 13, 65, and 34 are added to the queue. Where will they be placed in the array? What will be the value of front and rear after one dequeue operation? Which number will the dequeue operation return? In the interactions pane, add 4 elements to q1. Open a viewer on q1 after the first line is executed. CircularQueue q1 = new CircularQueue(); q1.enqueue(87); q1.enqueue(44); q1.enqueue(15); q1.enqueue(9); Create an expand method to expand the internal array's size. private void expand() { } Create a new array with increased size. E[] newQueue = (E[]) new Object[(queue.length * 3) / 2 + 1]; Dequeue all of the current elements add them to the new array beginning at index 1. int newIndex = 1; while (!this.isEmpty()) { newQueue[__________] = this.dequeue(); newIndex++; } Set queue to reference the new array and update the front and rear pointers. Data Structures Array-Based Circular Queue Data Structures | Circular Queue 8 queue = newQueue; front = _____; rear = newIndex - 1; Important: Find your enqueue method and make sure to uncomment the expand method invocation before continuing. public void enqueue(E newElement) { if (isFull()) { this.expand(); } Create the following main method with the break point at the specified location. Answer the following questions and then use the viewer to confirm your answers: When does the queue first become full (does not need to expand, but has the max number of elements)? During which line of code will the array exceed the capacity and need to expand? What is the placement of elements in the old array and the new array once the queue has expanded? HINT: you'll have to step into the expand method and look at both the current queue and newQueue. What will be printed to standard output once the program is complete? Ensure that your output is as follows when you run your program: Data Structures Array-Based Circular Queue Data Structures | Circular Queue 9 The array initially becomes full after "c" is added. One element is then taken out, but the queue becomes full again when "d" is added: Your array should have expanded when the string "e" was added to the queue Deliverable: Create a new program called QueueTest with a main method that performs the following steps: 1. Create a CircularQueue object with an initial capacity of 4. 2. Add the following String objects to the queue: Red, Yellow, Green, Blue, Purple, Orange, White 3. Remove 2 elements from the queue. 4. Add the following element to the queue Grey. 5. Create a loop that removes and prints all elements from the queue. Answer the following questions: What is the difference between the contents of the queue and the contents of the internal data array? After which step did the two differ? If you wanted to create a size() method to return the number of elements in the queue, what would you return? If you had used a linked list implementation of the queue, how would your queue differ from the array implementation? Submit both the CircularQueue class and the QueueTest class