Basic implementation of an array-based Queue

Question

After been taught about Queues in lecture I've tried to do my own implementation.

I like to mention: The ideas were shown in lecture on a blackboard using a pseudocode notation.

The following code has been figured out by myself based upon my lecture notes. I've avoided having a closer look upon a concrete Java-implementations. I hope to get more familiar with the Queue concept if I first try to do it by myself.

Queue class:

package playground;

public class Queue
{
    private int[] items;
    private int first;
    private int last;
    private int countItems;

    public Queue(int itemsLength) {
        items = new int[itemsLength];
        countItems = 0;
        first = 0;
        last = -1;
    }

    public void addToQueue(int item) {
        // If current count items is smaller then the 
        //  maximal size of the array ...
        if (countItems < items.length) {
            last = (last + 1) % items.length;
            items[last]  = item;
            countItems++;
        } else {
            throw new IndexOutOfBoundsException(
                    "Can not add another item. Queue is already full.");
        }
    }

    public int removeFromQueue() {
        if (countItems > 0) {
            int currentFirst = items[first];

            first = (first + 1) % items.length;
            countItems--;

            return currentFirst;
        } else {
            throw new IndexOutOfBoundsException(
                "There are no items to remove because the Queue is empty.");
        }
    }
}

The test-class I've made:

package playground;

import static java.lang.System.*;

public class Playground
{

    public static void main(String[] args) {
        Queue qu = new Queue(3);

        try {
            qu.addToQueue(2);
            qu.addToQueue(4);
            qu.addToQueue(8);
            qu.addToQueue(100);
        } catch (Exception e) {
            out.println(e.getMessage());
        }

        try {
            out.println("First remove: " + qu.removeFromQueue());
        } catch (Exception e) {
            out.println(e.getMessage());
        }

        try {
            qu.addToQueue(16);
        } catch (Exception e) {
            out.println(e.getMessage());
        }

        try {
            out.println("Second remove: " + qu.removeFromQueue());
            out.println("Second remove: " + qu.removeFromQueue());
            out.println("Second remove: " + qu.removeFromQueue());
        } catch (Exception e) {
            out.println(e.getMessage());
        }

        try {
            qu.addToQueue(32);
        } catch (Exception e) {
            out.println(e.getMessage());
        }

        try {
            out.println("Third remove: " + qu.removeFromQueue());
            out.println("Third remove: " + qu.removeFromQueue());
        } catch (Exception e) {
            out.println(e.getMessage());
        }

        try {
            qu.addToQueue(64);
            qu.addToQueue(128);

            // Only two items in t. queue. But trying to remove three items ...
            out.println("Fourth remove: " + qu.removeFromQueue());
            out.println("Fourth remove: " + qu.removeFromQueue());
            out.println("Fourth remove: " + qu.removeFromQueue()); 
        } catch (Exception e) {
            out.println(e.getMessage());
        }
    }

}

The output of the test-class:

Can not add another item. Queue is already full.
First remove: 2
Second remove: 4
Second remove: 8
Second remove: 16
Third remove: 32
There are no items to remove because the Queue is empty.
Fourth remove: 64
Fourth remove: 128
There are no items to remove because the Queue is empty.

The output of the test-class is what I've expected, so the Queue seems to work correctly to me. But there might be cases in which it produces errors, which I haven't thought about.

Is my implementation correct? Or does I have to improve it? Moreover, is my error handling done in an appropriate way?

I throw exceptions when someone tries to do a forbidden action (removing items from an empty queue, adding items to a full queue). But I'm not sure because throwing an exception might be to drastically.

In lecture a -1 was returned for showing that something has gone wrong. But I'm not convinced about that approach. -1 could be in the Queue just as a normal value. If I then write an error-handling routing which reacts to a return value of -1 then things could go wrong in an unforeseeable way.

How should the error-handling be done?

Answer 1

Great job overall writing organized code with nice test cases. I agree with using exceptions than returning a fixed arbitrary value. Also, good job trying to choose an appropriate exception type and writing meaningful messages.

Below are a few comments and slightly modified code.

Suggested Variable Naming Changes

• head and tail are more commonly used for queues rather than first and last.
• push and pop are also more common than addToQueue and removeFromQueue.
• itemsLength -> capacity
• countItems -> currentSize

Logic

• Starting last with -1 is kinda weird, I would start it with 0 and think about it as the first empty slot for a new element.
• It's probably better to handle any exceptions at the beginning of the method instead of if/else. This will reduce a level of indentation in the rest of your method, and also make it clear that if the execution reached that part, then the state is correct and doesn't have exceptions.
• Sometimes it's good to extract a part of the code to a method to make it more readable, better document it, and to reuse it in more than one place. I extracted the part which advances the pointers to a method (nextIndex) and reused it in push and pop. It's also probably good to put a comment on it.
• I think more appropriate exception types are IllegalStateException when pushing to a full queue, and NoSuchElementException when popping an empty queue. This is just based on their javadoc descriptions.

Testing

• Consider using a testing framework like junit. Among other things, it will help you organize your tests better, and provide helper functions to test your expected values.

Modified Code

package playground;

public class Queue
{
    private int[] items;
    private int capacity;
    private int head;
    private int tail;
    private int currentSize;

    public Queue(int capacity) {
        this.items = new int[capacity];
        this.capacity = capacity;
        this.currentSize = 0;
        this.first = 0;
        this.last = 0;
    }

    public void push(int item) {
        if (currentSize == capacity) {
            throw new IllegalStateException(
                    "Can not add another item. Queue is already full.");
        }
        items[last]  = item;
        last = nextIndex(last);
        currentSize++;
    }

    public int pop() {
        if (currentSize == 0) {
            throw new NoSuchElementException(
                "There are no items to remove because the Queue is empty.");
        }
        int element = items[head];
        head = nextIndex(head);
        currentSize--;
        return currentFirst;
    }

    private int nextIndex(int index) {
      return (index + 1) % capacity;
    }
}

Answer 2

Your error handling looks appropriate to me. You correctly throw Runtime Exceptions when programming errors occur, and provide good messages for these Exceptions.

I have some very small suggestions on your code.

1. Do not use comments for obvious logic i.e. //If current count items is smaller then the //maximal size of the array ...
2. Rename countItems to something more appropriate like "size". countItems is a verb and doesn't describe itself as clearly as size.
3. The function name addToQueue should be named add. The meaning of add is obvious in the context of the class and keeps the interface simple.

4. Use comments or methods to explain non-obvious operations. For example, the expression below could have used a comment explaining why the modulo is necessary.

   last = (last + 1) % items.length;