CS 201: Data Structures (Spring 2018)
HW08: Queue recursor
Due: Wednesday, 05/09 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 ofString
s 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
String
s, 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 fromjava.util.Collection
. Pick ones that interest you. For example,equals
is a fine option.
5. Submission and grading
Submit to MoodleRecursiveQueue.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
, andback
. 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.