Problem
Doing some exercises on basic data structures, I learned about queues, and decided to roll my own to better understand how a basic queue can function. As the name indicates, this Queue is made from a finite (i.e. regular) array. The JavaDoc gives more details throughout.
All this is pretty new to me, so I’m hoping to receive criticism on any and all aspects that can be improved.
Interface & Exceptions:
public interface Queue {
public int getSize();
public boolean isEmpty();
public boolean isFull();
public void enqueue(Object obj) throws QueueFullException;
public Object dequeue() throws QueueEmptyException;
}
public class QueueEmptyException extends RuntimeException {
public QueueEmptyException() {
super();
}
public QueueEmptyException(String message) {
super(message);
}
public QueueEmptyException(String message, Throwable cause) {
super(message, cause);
}
}
public class QueueFullException extends RuntimeException {
public QueueFullException() {
super();
}
public QueueFullException(String message) {
super(message);
}
public QueueFullException(String message, Throwable cause) {
super(message, cause);
}
}
FiniteArrayQueue
/**
* A FiniteArrayQueue can enqueue 0..N Objects, after which it must dequeue Objects to make room to enqueue
* more Objects. Objects may be dequeued from it until the queue is empty. The size of the queue cannot be changed
* after instantiation.
*/
public class FiniteArrayQueue implements Queue {
private Object[] queue;
private int capacity;
private int head;
private int tail;
/**
* Constructor.
* <p>
* Note that in order for a FiniteArrayQueue to have a "true" capacity of N items,
* its array size must be of (N + 1) to account for not being able to overlap
* the head and tail pointers of the queue (unless the queue is empty).
* @param desiredCapacity : The maximum number of items that can be in the queue
*/
public FiniteArrayQueue(int desiredCapacity) {
capacity = desiredCapacity + 1;
queue = new Object[capacity];
head = tail = 0;
}
/**
* Indicates whether the queue is empty.
* <p>
* Note that when the head and tail are at same index, the queue is empty.
* @return boolean : true if queue is empty
*/
public boolean isEmpty() {
return(tail == head) ? true : false;
}
/**
* If the head is one index higher than the tail, the queue is full.
* <p>
* Note that the 2nd condition is added to "wrap around" the array in case
* the tail is at the last index and the head is at index 0.
* @return boolean : true if queue is full
*/
public boolean isFull() {
int diff = tail - head;
if(diff == -1 || diff == (capacity - 1)) {
return true;
}
return false;
}
/**
* The current size of the queue, i.e. the number of items present in it.
* @return int : the size of the queue
*/
public int getSize() {
if(isEmpty()) {
return 0;
} else {
if (tail > head) {
return tail - head;
}
return capacity - head + tail;
}
}
/**
* Add/insert an Object at the tail index (or "back") of the queue, if the queue is not full.
* <p>
* Note modulo operator is used to "wrap around" the array.
* @param obj : The object to add/insert at the tail index
*/
public void enqueue(Object obj) throws QueueFullException {
if(isFull()) {
throw new QueueFullException("Queue is full.");
} else {
queue[tail] = obj;
tail = (tail + 1) % capacity;
}
}
/**
* Removes the Object at the head index (or "front") of the queue, if the queue is not empty.
* <p>
* Note modulo operator is used to "wrap around" the array.
* @return obj : the object at the head index
*/
public Object dequeue() throws QueueEmptyException {
Object item;
if(isEmpty()) {
throw new QueueEmptyException("Queue is empty.");
} else {
item = queue[head];
queue[head] = null;
head = (head + 1) % capacity;
}
return item;
}
}
FiniteArrayQueueTest
import junit.framework.TestCase;
/**
* Unit tests for FiniteArrayQueue.
*/
public class FiniteArrayQueueTest extends TestCase {
private static final int CAPACITY = 4;
private Queue testQueue;
public FiniteArrayQueueTest(String testName) {
super(testName);
testQueue = new FiniteArrayQueue(CAPACITY);
}
public void testIsEmpty() throws Exception {
assertTrue(testQueue.isEmpty());
}
public void testNotIsEmpty() throws Exception {
testQueue.enqueue("Hello");
assertFalse(testQueue.isEmpty());
}
public void testIsFull() throws Exception {
for(int i = 0; i < CAPACITY; i++) {
testQueue.enqueue(i);
}
assertTrue(testQueue.isFull());
}
public void testNotIsFull() throws Exception {
for(int i = 0; i < 2; i++) {
testQueue.enqueue(i);
}
assertFalse(testQueue.isFull());
}
public void testGetSize() throws Exception {
for(int i = 0; i < 3; i++) {
testQueue.enqueue(i);
}
assertEquals(testQueue.getSize(), 3);
}
public void testEnqueue() throws Exception {
testQueue.enqueue("A");
assertEquals(testQueue.getSize(), 1);
}
public void testDequeue() throws Exception {
testQueue.enqueue("Foo");
assertSame(testQueue.dequeue(), "Foo");
assertTrue(testQueue.isEmpty());
}
public void testGetSizeWithWrapAround() throws Exception {
for(int i = 0; i < CAPACITY; i++) {
testQueue.enqueue(i);
}
for(int i = 0; i < 3; i++) {
testQueue.dequeue();
}
assertEquals(testQueue.getSize(), 1);
testQueue.enqueue(4);
assertEquals(testQueue.getSize(), 2);
testQueue.enqueue(5);
assertEquals(testQueue.getSize(), 3);
testQueue.enqueue(6);
assertEquals(testQueue.getSize(), 4);
}
}
Solution
On testing…
Your tests are incomplete, certainly.
Your test on isEmpty only tests two conditions: a newly instantiated queue which has never had anything added to it should return true, and after adding just one thing, it should return false.
- How does
isEmptydo when the queue is full? - How does
isEmptydo when the queue has had two items added and then one removed? - How does
isEmptydo when the queue has had two items added and then two removed? - How does
isEmptydo when it has been filled, emptied, then filled again? - How does
isEmptydo when our queue is instantiated with a max size of zero?
We can ask a lot of the same questions for isFull.
- How does
isFulldo with a newly instantiated queue that has never had any objects added to it? - How does
isFulldo when we’ve filled it and then removed one or more objects? - How does
isFulldo when we’ve filled it, removed some objects, then filled it back to capacity? - How does
isFulldo when we create a queue with max size zero?
We can ask some questions of getSize too. You’ve only tested on very specific and weird case.
- Does
getSizereturn the proper value of a newly instantiated array before we’ve added anything to it? - For every call to
enqueue, doesgetSizereturn the correct value? (Hint: You canassertin a loop) - If we have a full queue, try to enqueue, catch the exception, does
getSizestill return the expected value? - For every call to
dequeue, doesgetSizereturn the correct value? - When we’ve filled, then emptied to zero, does
getSizereturn the correct value? - If we have an empty queue, try to dequeue, catch the exception, does
getSizestill return the expected value (zero)?
How about enqueuing and dequeuing?
Your testEnqueue is testing the wrong thing. That’s asserting that getSize works.
The first assertion in testDequeue has the right idea, but the second assertion is testing that isEmpty works.
Neither of these tests test that the proper exception is thrown in the proper conditions.
I would write something called testFirstInFirstOut that runs through lots of iterations and combinations of enqueuing and dequeuing and making sure things are coming out in the order we’d expect them to come out in.
I’d also write a test called testEnqueueException to verify that when we try to enqueue into a full queue, we get an exception.
I’d also write a test called testDequeueException to verify that when we try to dequeue from a full queue, we get an exception.
And most importantly, I’d spend a LOT of time on THIS answer before you even begin to start trying to implement any of the advice from my other answer (or any other answer that addresses anything but testing).
Refactoring has a tendency to introduce regressions. Unit tests prevent regressions. Beefing up your test suite before you start refactoring is a good way to make sure you’re introducing as few regressions as possible.
First, a minor nitpick.
public boolean isEmpty() {
return(tail == head) ? true : false;
}
public boolean isFull() {
int diff = tail - head;
if(diff == -1 || diff == (capacity - 1)) {
return true;
}
return false;
}
Twice we’re using returning true or false based on the result of a conditional. Why not just directly return the result of that conditional?
return (tail == head)return (diff == -1 || diff == (capacity - 1))
Typically, queues are implemented by being backed by a linked list. The fact that you’ve used an array here is what has limited you to a particular size. With a linked list, the only limiting factor would be how much RAM is available to the program.
Moreover, with a linked list backing your queue, items in the queue don’t need to be located in a contiguous block of memory. With your implementation, by storing them in array, it requires finding a contiguous block of memory in the system large enough to hold all of the items you’d ever want to hold.
Having enqueue and dequeue methods that throw exceptions quickly makes any code written to use this queue very verbose. Essentially, all of the primary usage of the queue must be done within try–catch blocks.
By using the aforementioned linked list backing strategy that eliminates the need to put a limit on how many items, the queue never has to be full (until the program runs out of RAM, but that’s an all together different problem), so we should never run into an exception when enqueuing objects.
On dequeuing objects, I feel like null should be the appropriate return value from an empty queue. Whoever dequeued can be responsible for checking whether or not it got null out, and if not, risk getting a null exception.
You should make use of generics.
Object works decent enough for putting in anything… but it also means you can get anything out. And you cannot limit what can be put in. So, on the dequeue end of things, you can quickly get into a mess casting things about.
As long as your queue has a finite size or is backed by an array, you should probably expose a getCapacity method.
You should be using generics. Forcing the caller to cast dequeued results from Object isn’t really acceptable.
The QueueEmptyException should probably just be NoSuchElementException, just like in other java.util classes.
The off-by-one definition of capacity is awkward. I would just drop that member altogether and use queue.length instead.
The isEmpty() and isFull() methods should just be implemented in terms of getSize(). All of those methods have too many cases.
public boolean isEmpty() {
return getSize() == 0;
}
public boolean isFull() {
return getSize() + 1 >= queue.length;
}
public int getSize() {
return (tail >= head) ? tail - head
: tail - head + queue.length;
}
In dequeue(), the code outside the if-else is awkward. I’d write it this way:
@SuppressWarnings("unchecked")
public T dequeue() throws NoSuchElementException {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
} else {
T item = (T)queue[head];
queue[head] = null;
head = (head + 1) % queue.length;
return item;
}
}
I don’t understand why all of your unit tests have throws Exception declared. That just squelches possible compiler errors that might be informative to you.
Just a few nitpicks that hasn’t been mentioned:
- Your
FiniteArrayQueueTestdoes not need toextends TestCase, that was the old way of using JUnit. Remove thatextends. - Annotate your methods with
@Testand you don’t have to explicitly havetestin their name. - Use
import static org.junit.Assert.*;
Also, your interface specification does not need to mark methods as public, all interface methods are public already. So public int getSize(); can be just int getSize();
On Fixed Size:
I don’t think I have ever backed a queue with a fixed sized array apart from code written for university exams. However it is easy to extend what you have done to allocate a new array of double the size and copy the item over if the queue gets filled. Doing so tends to be faster than using linked lists on modem CPUs (due to the processor cache) and also creates lets garbage so helps the garbage collector. See Strategy: Stop Using Linked-Lists
On Naming:
Lets take this code for example:
public FiniteArrayQueue(int desiredCapacity) {
capacity = desiredCapacity + 1;
queue = new Object[capacity];
head = tail = 0;
}
You have written nice small methods with clear names that greatly helps with understanding the code. However it is very easy to mix up parameters that are passed into the method and fields of the object when reading the code. Therefore it is better to prefix all your fields with “_”, so making the code read like:
public FiniteArrayQueue(int desiredCapacity) {
_capacity = desiredCapacity + 1;
_queue = new Object[_capacity];
_head = _tail = 0;
}
(Some people will disagree with the above, but every programming job I have done in over 20 years of programming, we had had some naming convention for members of a object.)