Assignment #6:
1. Create a generic Queue class together with a driver program based on the dynamic
queue implementation shown on the class website. As part of the solution, include
examples that instantiate and demonstrate your Queue class for Strings, Points (used
in this course), and numeric values of type Integer. Be sure to meet the requirements
specified in a through e, below:
a. The enqueue() and dequeue() operations shall be O(1)
b. The Queue class shall be provided and shall be generic
c. Exception handling for Queue is empty and Queue is full conditions shall exist
d. Sample runs for the three types specified above shall be provided
e. Use of Java Containers is encouraged; however, your program must provide all of
the required methods, including enqueue() and dequeue()
2. What is the order of magnitude to insert a new node at the beginning and end of a
doubly linked list? Defend your answer.
3. What is the order of magnitude to search for a value in an unsorted array? In an
unsorted linked list? In a sorted array? In a sorted linked list?
4. What is the lowest order of magnitude to sort an array of integers? What is the name
of the sorting algorithm?
5. What is recursion? What limits exist using recursion? Name at least one algorithm
where the use of recursion is useful and unlikely to be impacted by limits of recursion.
6. What is a Red-Black Binary tree? What advantages does a binary tree offer over a
linear linked list?
7. What is a hash table, name at least one case where a hash table is advantages over
a binary tree; name one case where a binary tree would be preferable.
