Deques and Randomized Queues

Implementation of Deque using a two-way linked list If something tries to call it, throws UnsupportedOperationException. Component of the two-way linked list. Unit tester for Deque. * Checks for correctness by running each of the methods in * different scenarios (e.g. addFirst and addLast on both empty and * nonempty deques). * Iterator checked using a for each loop. * Correctness checked by outputting array, size, and emptyness status. Implementation of randomized queue using a generic, resizing array. Randomizatin occurs in dequeue and the iterator. Enqueues item at the next available index. * The search for an available index begins at the index immediately * after the previous location where an item was enqueued. Removes a random item. * Generates a random index until there is an item located at the * generated index Constructs a RandomIterator object. * Generate perm, a list of indices, and shuffle it. * Referenced constructor of Bag's RandomIterator in precept packet. Resizes the array, to better accommodate the number of items * in the randomized queue. * Referenced ResizingArrayStack.java for this method. /** * Unit tester for RandomizedQueue. * Checks for correctness by running each of the methods in * different scenarios (e.g. enqueuing that forces a resize, and * enqueuing when empty). * Iterator checked using a for each loop. * Correctness checked by outputting array, size, and emptyness status. */ Contains an item, and the nodes before and after it. Returns the current item, then moves to the next item. Throws NoSuchElementException if there is no next item. Client class that uses RandomizedQueue to output a given number of strings out of a given sequence of strings. Outputs a k strings out of a given sequence of strings. k is a command line argument. The sequence of strings is read from input. The sequence of strings is assumed to be separated by whitespace. /****************************************************************************** * Explain briefly how you implemented the randomized queue and deque. * Which data structure did you choose (array, linked list, etc.) * and why? *****************************************************************************/ /****************************************************************************** * How much memory (in bytes) do your data types use to store N items * in the worst case? Use the 64-bit memory cost model from Section * 1.4 of the textbook and use tilde notation to simplify your answer. * Briefly justify your answers and show your work. * * Do not include the memory for the items themselves (as this * memory is allocated by the client and depends on the item type) * or for any iterators, but do include the memory for the references * to the items (in the underlying array or linked list). *****************************************************************************/ /****************************************************************************** * Describe whatever help (if any) that you received. * Don't include readings, lectures, and precepts, but do * include any help from people (including course staff, lab TAs, * classmates, and friends) and attribute them by name. *****************************************************************************/ /****************************************************************************** * Describe any serious problems you encountered. *****************************************************************************/ /****************************************************************************** * List any other comments here. Feel free to provide any feedback * on how much you learned from doing the assignment, and whether * you enjoyed doing it. *****************************************************************************/