Recursive Queue

Table of Contents

This assignment is to be done individually. You can share ideas and thoughts with other people in the class, but you should code your own assignment.

We will use anonymous grading on Moodle, which means that the grader won't see your name until after the grading is done. This is an easy way to help add an extra element of fairness to the grading. Therefore, make sure your name doesn't appear on your actual submission. When you submit via Moodle, it will know you are. Thanks!

The task

Implement a queue recursively. Specifically, create a class called RQueue that implements the following interface: 

public interface CarlQueue<T>
{
    // Add item to the queue
    void enqueue(T item);

    // Return next item to come out of queue, without changing it.
    // If the queue is empty, return null
    T getFront();

    // Remove the next item from the queue. If the queue is empty, return null.
    T dequeue();

    // Print the entire contents of the queue to the screen to help you in
    // debugging and us in grading. If the integers 1, 2, 3, 4, 5 were enqueued
    // in that order, this method should print out "1 2 3 4 5".
    void display();

    // Display just the contents of this particular object for grading and
    // debugging purposes. (This is essentially a non-recursive version of the
    // display method.
    void showImmediateContents();

}

Your queue must be implemented as a recursive data structure. Here is a class definition to get you started: 

public class RQueue<T> implements CarlQueue<T>
{
    private T front;
    private RQueue<T> inside;
    private T rear;

    // This method is useful for us in testing your code. Do not modify it.
    public void showImmediateContents() {
        System.out.println("Front: " + front);
        System.out.println("Inside: " + inside);
        System.out.println("Rear: " + rear);
    }

    ...
}

The idea is that a queue can be thought of as a data structure containing a front, a back, and a queue within. For example, if my queue contained the Strings "first", "second", and "third" (offered in that order), I can think of that as a queue whose front is "first", whose rear is "third", and whose inside is another queue containing all of the inside values (which, in this case, is just "second").

You'll need to handle special cases regarding when your queue is empty, has only one item, and so on. You're free to do this as you wish, but I have hints here if you want to look. If you'd prefer the challenge of figuring it out yourself, don't look.

Two parts for asssignment

Part 1

Get enqueue and getFront working. When submitting your code, make sure to include all files you need to ensure that your code compiles and runs (such as your interface). Also make sure that none of your methods, with the exception of display, print anything to the screen. If you had any print statements in your code for debugging purposes, make sure to remove them before submitting.

Part 2

Resubmit part 1, with display and dequeue working as well. See above comments regarding which files to submit as well as print statements.

Author: Dave Musicant

Validate