CS 201: Data Structures (Spring 2017)

HW08: Queue recursor

Due: Wednesday, 05/10 at 22:00

1. Goals

To implement a recursion-based structure (and take a break from larger projects).

2. Setup

This is a solo programming assignment. You can share ideas and thoughts with other people in the class, but the code that you submit should be your own. You are also welcome to talk to me, the prefect, or the CS lab assistants for help.

Please remember that you should not be searching the internet for code: you might look up some small point of syntax, and javadocs are always fine to read. However, it is a violation of this course's academic honesty policy to seek out larger code examples, even if you do not copy those examples directly. You should also not look at your classmates' code. If you use code from the book, you should cite your source; you should not directly copy code out of the book, although you are welcome to look at it, and then try to produce the code yourself. You are welcome to look back at worksheets and notes from class, and to cite them in your code as well.

Download Queue.java.

3. Specification

Implement a queue of Strings recursively. Specifically, create a class called RecursiveQueue that implements the queue interface Queue.java.

Your queue must be implemented as a recursive data structure. The idea is that a queue can be thought of as a data structure containing a front element, a middle queue, and a back element. For example, if I added aardvark, be, cause, delta, and epsilon to the queue (in that order), the queue's front would be aardvark (first item added), back would be epsilon (last item added), and middle would be a queue containing be, cause, and delta (the remaining items, in the same order).

4. Code notes

• You will need to handle special cases when your queue is empty, has only one element, and so on. You are free to do this as you wish as long as your setup matches the description in the previous paragraph.
• If you are stuck, click here for hints on how to set things up. If you would prefer the challenge of figuring it out yourself, don't look.
• As the interface specifies, your queue should reject null values.
• Optional extra challenge: Implement your queue as a generic class, i.e., one that doesn't just work for Strings, but instead takes a type parameter. (You will be required to implement a generic class in the next homework assignment.)
• Another extra challenge: If you want even more work to do, look at java.util.Queue and implement some methods inherited from java.util.Collection. Pick ones that interest you. For example, equals is a fine option.

5. Submission and grading

Submit to Moodle RecursiveQueue.java. There is no need to zip this time, yay!

Assignment requirements

This is a partial list of the things that we'll be looking for when evaluating your work (in addition to style):

• Correctly implements a recursive queue.
• The correct exceptions are thrown as specified in the interface.
• Please name your instance variables front, middle, and back. This will help the grader.
• Note that style is proportionally worth more this assignment.

Grading

• Assignment requirements [15 points]
• Comments, style, and design [5 points]

Start early, have fun, and discuss questions on Moodle.