In class we studied how an ArrayList is implemented by creating an underlying array (e.g., [])...

 

Transcribed Image Text:

In class we studied how an ArrayList<E> is implemented by creating an underlying array (e.g., []) and storing the data in that array. The set, get, add, remove, etc. methods were implemented by manipulating the data in the underlying array. Note that the ArrayList<E> is a generic class. The type of data stored in the array can be any kind of Object. The type-parameter E is a placeholder for the actual type of data to be stored in the data structure (e.g., String, or Car, or Bank Account). For this assignment you must implement a generic FIFO Queue. This data structure (aka Collection) represents a "waiting line", such as a line at the grocery store. People join the line at the end (no cutting in line!) and the person at the front of the line is the one to leave the line and get service. A FIFO Queue is "first in, first out". This data structure is much more limited than a general List, such as ArrayList or LinkedList. For this assignment you must write a class called FloatingQueue<T>. You must implement the following operations specified in the given LucasQueue<T> interface. This is a subset of the operations specified in the Queue<T> interface in the Java API, which is part of the Java Collections Framework. FloatingQueue() FloatingQueue(n) offer (newData) poll() peek()) size() isEmpty() clear() Constructor method that will allocate memory for an array of size 5. Constructor method that will allocate memory for an array of size maximum(5,n) Add the parameter value to the end of the Queue. If the array does not have any more capacity, then create a new array with twice as much room. It is illegal for the added value to be the null pointer Remove the data from the head (or front) of the Queue, and return that object. Return null, if the Queue is empty. If the size of the Queue falls below 25% of capacity, then reallocate an array that is half the size of the current array (so memory is not wasted), but do not allow the array to have fewer than 5 slots. Return the data from the head (or front) of the Queue. Return null, if the Queue is empty Return the number of items currently in the Queue Return true if-and-only-if the Queue has no elements in it. The Queue should be empty after this operation is performed, and the allocated memory for the Queue should be the minimum value (.c.. 5) toString() Return a String representing the current contents of the Queue, listed from left-to-right in the same order as the front-to-rear of the Queue. For example, the String might be: “[alice,bob,chad]” You must implement these methods directly, without using any built-in Collection classes. Your FloatingQueue class will be generic. So, your class definition will be similar to that shown below. public class FloatingQueue<T> implements LucasQueue<T> { private T[] theData; // The underlying data array public FloatingQueue(int initialCapacity) { theData = (T[]) new Object[ initialCapacity ]; The FloatingQueue class contains an array to hold the data in the queue. You must not use an ArrayList, or any other class to store these elements. The point of this exercise is to directly manipulate the array. The constructor methods for the FloatingQueue class allocate memory for the underlying array, and use casting. The following, seemingly more direct, code will not compile: theData = new T[ initialCapacity ]; Your FloatingQueue class must also have a default (aka “no parameter") constructor that initializes the size of the underlying array to be five (5). As with any data structure, there are many different ways you can go about storing the data and implementing the operations. One possibility is to use a "left justified" array. The following example illustrates how the contents of the array change as data is inserted and deleted, assuming that the array is initially empty and has length five. Every poll() operation causes all the data in the array to shift one position to the left. This is a costly, O(n) time operation. operation offer(al) offer(bob) offer(chad) poll() poll() offer(dan) offer(ed) offer (fran) poll()) poll() offer (gian) operation offer(al) offer(bob) offer(chad) poll() poll() offer(dan) offer(ed) al al al offer (fran) poll() poll() offer(gian) 0 bob chad chad chad chad dan ed fran al al al 0 fran fran fran fran 1 bob bob chad dan dan dan ed fran gian A more efficient implementation of the FIFO Queue would be to use a "floating array". Instead of left-justifying the data, the sequence of consecutive elements in the queue are allowed to be anywhere in the array. The following example illustrates how the contents of the array change as data is inserted and deleted, assuming that the array is initially empty and has length five. bob bob bob array contents 2 1 chad ed ed fran 3 fran array contents 2 chad chad chad chad chad chad 3 dan dan dan dan 4 ed ed ed ed ed 4 gian In other words, the sequence of elements that form the queue data are in consecutive array positions, but the front of the queue (i.e., the head of the line) need not be located in position 0. The sequence of consecutive elements "floats" in the array. Notice that the consecutive queue elements can "wrap around" from the end of the array to the start of the array, as needed. In this implementation, every poll() operation takes only O(1) time. Your FloatingQueue class should be efficient with respect to memory space, as well as to time. When the number of items in the array drops below 14 of the capacity of the array, then your FloatingQueue class should reallocate the array to be an array only 1/2 of the current capacity of the array. Each of the Lucas Queue operations in your FloatingQueue class should require only a small amount of code (less than ½ page for each method). You are given a Tester class. If you have implemented the FloatingQueue<T> correctly, then the main method in Tester should execute without any errors. Your code must work for the given Tester. You can add extra code to the Tester, if you wish, to do more thorough error checking, but you must not alter the given Tester code in any way. To submit your work, upload a zipfile containing your FloatingQueue.java file to the Program 1 Assignment drop box in Canvas. Yes, you only need to submit one file, but you must still "zip up" that file and submit the zipfile. You should be sure to include YOUR NAME in a comment at the top of your source code file. Your source code must use proper style, i.e., variables should be well named (name is not too short, not too long, and is meaningful), and bodies of loops, if's, etc. should be properly indented. In class we studied how an ArrayList<E> is implemented by creating an underlying array (e.g., []) and storing the data in that array. The set, get, add, remove, etc. methods were implemented by manipulating the data in the underlying array. Note that the ArrayList<E> is a generic class. The type of data stored in the array can be any kind of Object. The type-parameter E is a placeholder for the actual type of data to be stored in the data structure (e.g., String, or Car, or Bank Account). For this assignment you must implement a generic FIFO Queue. This data structure (aka Collection) represents a "waiting line", such as a line at the grocery store. People join the line at the end (no cutting in line!) and the person at the front of the line is the one to leave the line and get service. A FIFO Queue is "first in, first out". This data structure is much more limited than a general List, such as ArrayList or LinkedList. For this assignment you must write a class called FloatingQueue<T>. You must implement the following operations specified in the given LucasQueue<T> interface. This is a subset of the operations specified in the Queue<T> interface in the Java API, which is part of the Java Collections Framework. FloatingQueue() FloatingQueue(n) offer (newData) poll() peek()) size() isEmpty() clear() Constructor method that will allocate memory for an array of size 5. Constructor method that will allocate memory for an array of size maximum(5,n) Add the parameter value to the end of the Queue. If the array does not have any more capacity, then create a new array with twice as much room. It is illegal for the added value to be the null pointer Remove the data from the head (or front) of the Queue, and return that object. Return null, if the Queue is empty. If the size of the Queue falls below 25% of capacity, then reallocate an array that is half the size of the current array (so memory is not wasted), but do not allow the array to have fewer than 5 slots. Return the data from the head (or front) of the Queue. Return null, if the Queue is empty Return the number of items currently in the Queue Return true if-and-only-if the Queue has no elements in it. The Queue should be empty after this operation is performed, and the allocated memory for the Queue should be the minimum value (.c.. 5) toString() Return a String representing the current contents of the Queue, listed from left-to-right in the same order as the front-to-rear of the Queue. For example, the String might be: “[alice,bob,chad]” You must implement these methods directly, without using any built-in Collection classes. Your FloatingQueue class will be generic. So, your class definition will be similar to that shown below. public class FloatingQueue<T> implements LucasQueue<T> { private T[] theData; // The underlying data array public FloatingQueue(int initialCapacity) { theData = (T[]) new Object[ initialCapacity ]; The FloatingQueue class contains an array to hold the data in the queue. You must not use an ArrayList, or any other class to store these elements. The point of this exercise is to directly manipulate the array. The constructor methods for the FloatingQueue class allocate memory for the underlying array, and use casting. The following, seemingly more direct, code will not compile: theData = new T[ initialCapacity ]; Your FloatingQueue class must also have a default (aka “no parameter") constructor that initializes the size of the underlying array to be five (5). As with any data structure, there are many different ways you can go about storing the data and implementing the operations. One possibility is to use a "left justified" array. The following example illustrates how the contents of the array change as data is inserted and deleted, assuming that the array is initially empty and has length five. Every poll() operation causes all the data in the array to shift one position to the left. This is a costly, O(n) time operation. operation offer(al) offer(bob) offer(chad) poll() poll() offer(dan) offer(ed) offer (fran) poll()) poll() offer (gian) operation offer(al) offer(bob) offer(chad) poll() poll() offer(dan) offer(ed) al al al offer (fran) poll() poll() offer(gian) 0 bob chad chad chad chad dan ed fran al al al 0 fran fran fran fran 1 bob bob chad dan dan dan ed fran gian A more efficient implementation of the FIFO Queue would be to use a "floating array". Instead of left-justifying the data, the sequence of consecutive elements in the queue are allowed to be anywhere in the array. The following example illustrates how the contents of the array change as data is inserted and deleted, assuming that the array is initially empty and has length five. bob bob bob array contents 2 1 chad ed ed fran 3 fran array contents 2 chad chad chad chad chad chad 3 dan dan dan dan 4 ed ed ed ed ed 4 gian In other words, the sequence of elements that form the queue data are in consecutive array positions, but the front of the queue (i.e., the head of the line) need not be located in position 0. The sequence of consecutive elements "floats" in the array. Notice that the consecutive queue elements can "wrap around" from the end of the array to the start of the array, as needed. In this implementation, every poll() operation takes only O(1) time. Your FloatingQueue class should be efficient with respect to memory space, as well as to time. When the number of items in the array drops below 14 of the capacity of the array, then your FloatingQueue class should reallocate the array to be an array only 1/2 of the current capacity of the array. Each of the Lucas Queue operations in your FloatingQueue class should require only a small amount of code (less than ½ page for each method). You are given a Tester class. If you have implemented the FloatingQueue<T> correctly, then the main method in Tester should execute without any errors. Your code must work for the given Tester. You can add extra code to the Tester, if you wish, to do more thorough error checking, but you must not alter the given Tester code in any way. To submit your work, upload a zipfile containing your FloatingQueue.java file to the Program 1 Assignment drop box in Canvas. Yes, you only need to submit one file, but you must still "zip up" that file and submit the zipfile. You should be sure to include YOUR NAME in a comment at the top of your source code file. Your source code must use proper style, i.e., variables should be well named (name is not too short, not too long, and is meaningful), and bodies of loops, if's, etc. should be properly indented.

Answer rating: 100% (QA)

Below is a simple implementation of the FloatingQueue class in Java based on the specifications you ... View the full answer