JAVA

1. (50 points) The Queue class works as the line at Starbucks R , that is, each arriving customer joins the line at the end, and the first cus- tomer to order is standing at the front. This ordering is called First-In First-Out (FIFO). Implement a generic class QueueT that maintains a collection of items of generic type T in FIFO order. Use the class LinkedListT in the Java API to implement Queue. That is, your Queue must store the items in a LinkedList, and the methods of your Queue must use methods of LinkedList. Your Queue class must pro- vide the following instance methods: enqueue: that adds a new item to the back of the queue. dequeue: that removes an item from the front of the queue. inQueue?: that returns true if a given item is in the queue, or false otherwise. isEmpty?: that returns true if the queue is empty, or false other- wise.

2. (20 points) Write a testQueue class with a main() method that tests all four operations of the Queue class designed. Override the toString() method of the class Object, and use it to display all the items in the queue after each method is called.

3. (30 points) Compute the big-O running time of each of the four in- stance methods, explaining the running time (basic operation counted, number of iterations in loops, etc.)

4. (Extra credit) Repeat point 1 implementing the queue with a circular array (as we did in class), expanding the array when it is full and shrinking it when it is half empty.