Circular queue implementation

Question

I've implemented a simple thread-safe circular queue. I'm looking for code review, optimizations and best practices.

public class CircularQueue {
    int[] queue; 
    int front;
    int rear; 
    int currentSize;
    int size;

    public CircularQueue(int size) { 
        this.queue = new int[size];
        this.front = 0;
        this.rear = 0;
        this.size = size;
        this.currentSize = 0;
    }

    public synchronized boolean add(int x) {

        if (currentSize == size) {
            throw new IllegalStateException("The queue is full: front size: " + rear);
        }

        queue[rear++] = x;
        rear = (rear + 1) % size;
        currentSize++;

        return true;
    }

    public synchronized int peek() {
        if (front == rear) {
            throw new IllegalStateException("The queue is empty");
        }
        return queue[front];
    }

    public synchronized int poll() {
        if (front > rear) {
            throw new IllegalStateException("The queue is empty");
        }
        currentSize--;
        return queue[front++];
    }
}

Answer 1

As pointed out by others, you have some bugs.

• add increments rear twice.
• poll should wrap front.
• poll and peek use different emptiness tests. Here's where isEmpty and isFull would come in handy.
• And neither test is correct. When front and rear are equal (once you wrap the former), the queue is either empty or full. You can compare currentSize to size instead.

Answer 2

Explicit visibility

I don't like relying on standard visibility; explicit declaring takes away all doubts. Instead have this:

private int[] queue; 
private int front;
private int rear; 
private int currentSize;
private int size;

Implicit this

Contrary to the above having explicit this is unneeded and takes away from the readability. You should only use it when there is ambiguity with a parameter name. This results in this:

queue = new int[size];
front = 0;
rear = 0;
this.size = size;
currentSize = 0;

Naming

What is currentSize and how does it differ from size? At first glance I would think they're the same. Some alternative names

size:

• size
• maxSize

currentSize:

• index
• offset

Iterator

If you want your class to be able to be used in a foreach loop, you could implement Iterator<T>.

Generics

Your datastructure is not generic so you're losing out on a lot of possibilities.

Kaput

Your code isn't working as it is. I'm not entirely sure why (it's 3:30 AM so I'm not going to debug it deeply anymore) but I followed a hunch and this small example demonstrates it:

public static void main(String[] args) {
    CircularQueue cq = new CircularQueue(3);
    cq.add(5);
    cq.add(10);
    System.out.println(cq.poll());
    cq.add(15);
    System.out.println(cq.poll());
}

You'll notice that the last call to poll() will throw you your self defined exception (aka front > rear evaluates to true).

Answer 3

It's cheating, but: if you are going to be looking at circular queues, you should really review the implementation of Disruptor.

Reviewing this implementation:

There's no particularly good reason to restrict it to ints, is there? CircularQueue<T> isn't much more work.

It's likely a cleaner design to treat the Queue as being backed by an infinite array, rather than wrapping your pointers over and over again. So front and rear should tell you which item in the queue history that they point at, and reserve the modulus function for accessing the array itself. This gives you some nice invariants to check, like rear >= front.

I definitely get tangled by the variable names. insertCursor and retrieveCursor might be clearer. Or writeTo and readFrom.

Why aren't you implementing java.util.Queue<T>? (Answered by rolfl - because that interface brings too much baggage along with it. It might still be a good idea to support offer(E), though.)

Throwing new exceptions each time you hit a problem condition can get expensive. java.util.Queue.add() does it, so I suppose you've got some prior art in your defense, but if you aren't going to implement that interface, then perhaps you can more cleanly support congestion control.

Because every method is synchronized here, lock contention may get to be a problem when you start using this from multiple threads.

There doesn't seem to be a need for currentSize, since you can always compute it from front and back.

Do you really intend to expose these member variables to other classes in your package? They should probably be private. And the array should likely be final as well.

Answer 4

I'm puzzled by this inconsistency in the way an empty queue is detected:

public synchronized int peek() {
    if (front == rear) {
        throw new IllegalStateException("The queue is empty");
    }
    …
}

public synchronized int poll() {
    if (front > rear) {
        throw new IllegalStateException("The queue is empty");
    }
    …
}

I believe peek() has it right, and poll() is wrong.

For that matter, why not check for currentSize == 0? That would be the clearest way.

Answer 5

Some random notes:

• I'd rename add and poll to push and pull.

• front shall be wrapped around when it reaches size, just like rear. I hope it is just a typo.

• I don't see the reason for peek and poll to test different conditions. As coded, poll will return garbage if called before the first add.

• All methods should have blocking counterparts.