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!