As we mentioned in class, the LinkedList class implements the Queue interface efficiently, providing O(1) implementations of add, remove, and peek. Likewise, an array-based implementation (e.g., ArrayQueue) can provide O(1) add and peek, but O(N) remove. For the first part of this assignment, you will write a short driver program to experimentally verify these efficiencies.
Your program should prompt the user for four things: (1) the queue implementation, (2) the initial size queue to time, (3) the maximum size queue to time, and (4) the number of peek/remove/add operations to perform. It should generate and report timings for queues of increasing sizes. Each timing will measure the time it takes to conduct the three queue operations (e.g., peek, then remove, then add) the specified number of times. The size of the list should double each time, stopping when the maximum size is reached. To conduct the timings, use the StopWatch class, which has methods for starting and stopping a stopwatch, then getting the elapsed time between. Since this class measures elapsed time, you should minimize the number of programs running on your computer when conducting your trials.
For example, execution of your program might appear as follows (with the timings being purely fictional):
(A)rray or (L)inked implementation: A Starting queue size: 1000 Doubling size until: 100000 Number of peek/remove/add operations: 10000 1000: 1.0 2000: 1.0 4000: 5.0 8000: 9.0 16000: 16.0 32000: 30.0 64000: 50.0
For full credit, your program should verify that the user inputs are valid. In particular, the type of implementation should be a word that begins with either 'A' or 'L' (regardless of case). If the user enters something else, even a blank line, they should be reprompted until they finally enter a valid word. Similarly, the queue sizes and number of operations must be positive integers and the maximum size must be greater than the initial size.
In a separate document, describe the pattern you would expect to see in the timings for each of the implementations. Provide data generated from your program to support your expectations. Note: you will need to experimentally determine the number of operations needed to get reasonable timings. Also note that small lists may produce inconsistent timings as the overhead involved in executing the program may dominate. Likewise, extremely large lists may produce inconsistent results if memory is exhausted and results in excessive garbage collection.