Use Java

1. Implement a queue on the singly linked list of Item #1, with the following operations: enqueue, dequeue, front, size, isEmpty. Note: both operations, enqueue and dequeue, must run in O(1).

2. Practical application 2:

The merge problem. Given two sorted lists of integers, A and B, the aim is to merge A and B, producing a sorted list S.

(a) Write an algorithm that stores A and B in two queues (one in each queue), merges A and B, and outputs a sorted list S in O(n) worst-case time. Note: your algorithm must use queues for A, B and S.

(b) Implement your algorithm in your favorite programming language.

(c) Explain how your algorithm runs in O(n), where n is the length of S.

(d) [2 bonus marks*] Run your algorithm on randomly generated sorted lists A and B of different sizes: 100, 200, 300, , 2000 and record the CPU time taken by the algorithm. Create a table (or a plot) and explain how your algorithm runs in O(n) by inspecting your results.