Due Date: Monday, February 21, 2022.

In this homework we will implement a queue class extending the List class we've worked on in previous homeworks. Then we will implement an application for the queue to print out all the binary numbers between 1 and a given number.

a. List Class.

In Eclipse or Netbeans, create a project called hw6. In this project, create a class called Node in a package called hw6. Copy the code from homework 4 (lab 2) for the Node class into this class, but change the type of the datum attribute to String.

The same way, create a class called List and copy the code from homework 4 (lab 2) into it, except for all the methods using iterators. Change anything that requires an integer (matching the datum) into String. You can copy these classes from Homework 5 if it makes it easier.

b. Queue Class.

Add a new class to the project called Queue, declared as extending the class List. You can use the lecture slides for the code in this class. Declare the following functions:

• constructor calling the super constructor;
• functions clear, isEmpty, and print doing the same thing as for the Stack;
• function front returning the value of the front node, implemented similarly to the function top from the stack;
• function enqueue taking one parameter of type String and calling insertBack to insert it in the list;
• function dequeue doing something similar to the function pop;
• function concatenate taking one parameter of type Queue and concatenating its content to the end of the nodes in the target object. Make sure that the head, tail, and size of both queues are updated properly. Note that the second queue should be empty at the end of the operation, and all the nodes should now be in the first queue (target object). Please refer to the last slide in the lecture for this function.

c. Test.

Add another class called Interface containing the main function. Add a static function in this class called testQueue where you

• declare two queues,
• enqueue a few strings into them,
• print both of the queues,
• concatenate the second queue to the first one, then output the result,
• perform some dequeue operations and output the results.

Call this function in the main to test it. Run the program to make sure it works fine.

Implement a static function based on the following algorithm in the Interface class and add a call in the main to it. Note that the "number" below should be a String.

void outputBinary(int n) {
    Queue q = new Queue();
    q.enqueue("1");
    for i from 0 to n (including n) {
        number = q.dequeue();
        output(number);
        q.enqueue(number+"0");
        q.enqueue(number+"1");
    }
}

This function will output all the binary numbers between 1 and the parameter n. For example, for n=16, it should output
1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000.

For this, it uses a queue storing strings. It starts by enqueueuing "1" into this queue. Then it does n more steps where it removes a string from the queue, outputs it, then adds both "1" and "0" at the end of it, and enqueues them. That way, the binary numbers are output in ascending order.

Upload all four .java files to Canvas, Assignments, Homework 6.