Project 3: Queues using ring buffers
Due: Monday, 22 Aug 2011, at 23:59:59 PST
Overview
In P3 you will be implementing (in a class called QueueImpl12)
a queue using a ring buffer as the underlying storage. In particular,
you must implement the Queue12 interface (the Javadoc is here).
You may not implement the queue
using a linked list of nodes. The ring buffer should consist of a "generic" Java array of type T.
The ring buffer (and the queue it supports) should have a fixed capacity, which is the number of data that the queue can
store at any given time. An attempt to enqueue another object into the queue when the queue is at full capacity (i.e.,
queue.size() == queue.capacity()) should fail, and the enqueue(o) method should return false; otherwise
(i.e., the queue.size() < queue.capacity()), the enqueue(o) method should successfully enqueue o and
then return true.
The dequeue method must remove and return the data element stored at the front of the list. If the queue
is empty, then dequeue should throw a NoSuchElementException. Note that both enqueue and
dequeue must take time O(1) in the worst-case.
Your QueueImpl12 class must offer a public constructor that takes exactly one parameter,
capacity, that specifies the capacity of the ring buffer used as the queue's underlying storage.
The implementing class must also offer a default constructor that takes no parameters
and that initializes the queue to have some default capacity (whose magnitude may be decided by the implementor).
In your implementation you will need to use instance variables for the "underlying storage" (the Java array representing the
ring buffer) as well as "index" variables (e.g., _frontIdx and _backIdx) to keep track of where
in the ring buffer the front and back of the queue are currently located. These index variables will need to "loop around" the
capacity of the list (e.g., _ringBuffer.length) properly.
You are encouraged to employ unit testing to test your queue implementation, but it is not strictly required for this assignment.
Your assignment will be graded using automated testers and also through manual inspection.
Grading
The maximum score on P3 is 6 points.
Submission
Submit your work using the
bundleP3 script in the directory containing your QueueImpl12.java file.
Make sure you are logged on to ieng6.ucsd.edu using your CSE 12-specific account.
As always, make sure to submit before the
deadline -- the script will show you (or anyone else) no mercy!