Array-based queue implementation

Question

Here I have implemented a queue. Is this a correct, efficient queue implementation? what issues are there if any and what can be done to make it better?

import java.util.*;

public class Queue2{
    private int amountInQueue;
    private int[] queue;
    private int rearIndex;
    private int frontIndex;

    public Queue2(){
        amountInQueue = 0;
        queue = new int[10];
        rearIndex = 0;
        frontIndex = 0;
    }

    public Queue2(int queueCapacity){
        amountInQueue = 0;
        queue = new int[queueCapacity];
        rearIndex = 0;
        frontIndex = 0;
    }

    public void enqueue(int valueToAdd){
        if(amountInQueue == queue.length){
            throw new FullQueueException();
        }
        else if(rearIndex == queue.length -1){
            rearIndex = 0;
            queue[rearIndex] = valueToAdd;
            amountInQueue++;
        }
        else if(amountInQueue == 0){
            queue[rearIndex] = valueToAdd;
            amountInQueue++;
        }
        else{
            rearIndex++;
            queue[rearIndex] = valueToAdd;
            amountInQueue++;
        }
    }

    public int dequeue(){
        int frontValue = frontIndex;
        if(amountInQueue == 0){
            throw new EmptyQueueException();
        }
        if(frontIndex == queue.length -1){
            frontValue = queue[frontIndex];
            frontIndex = 0;
            amountInQueue--;
        }
        else{
            frontValue = queue[frontIndex];
            frontIndex++;
            amountInQueue--;
        }
        return frontValue;
    }

    public boolean isEmpty(){
        return amountInQueue == 0;
    }

    public int valueAtRear(){
        return queue[rearIndex];
    }

    public int valueAtFront(){
        return queue[frontIndex];
    }

    public int currentSize(){
      return amountInQueue;
    }

  class FullQueueException extends RuntimeException{
      public FullQueueException(){
          super("You cannot add values to a queue that is full");
      }
  }

  class EmptyQueueException extends RuntimeException{
      public EmptyQueueException(){
          super("You cannot remove values from a queue that is empty");
      }
  }
}

Answer 1

Don't Repeat Yourself (DRY)

    public void enqueue(int valueToAdd){
        if(amountInQueue == queue.length){
            throw new FullQueueException();
        }
        else if(rearIndex == queue.length -1){
            rearIndex = 0;
            queue[rearIndex] = valueToAdd;
            amountInQueue++;
        }
        else if(amountInQueue == 0){
            queue[rearIndex] = valueToAdd;
            amountInQueue++;
        }
        else{
            rearIndex++;
            queue[rearIndex] = valueToAdd;
            amountInQueue++;
        }
    }

There's some duplicate code here. Consider

    public void enqueue(int valueToAdd) {
        if(amountInQueue == queue.length) {
            throw new FullQueueException();
        }

        if (rearIndex == queue.length -1) {
            rearIndex = 0;
        }
        else if (amountInQueue == 0) {
            frontIndex = 0;
            rearIndex = 0;
        }
        else{
            rearIndex++;
        }

        queue[rearIndex] = valueToAdd;
        amountInQueue++;
    }

You don't need to use an else after you throw an exception, as it will leave the function immediately.

More importantly, other than the exceptional case, all the cases have the same two lines. So take them out of the if/else construct. In the empty queue case, there's nothing left. You can clear the front and rear indexes if you want. Or you can remove that case entirely.

    public int dequeue(){
        int frontValue = frontIndex;
        if(amountInQueue == 0){
            throw new EmptyQueueException();
        }
        if(frontIndex == queue.length -1){
            frontValue = queue[frontIndex];
            frontIndex = 0;
            amountInQueue--;
        }
        else{
            frontValue = queue[frontIndex];
            frontIndex++;
            amountInQueue--;
        }
        return frontValue;
    }

Similarly, this could just be

    public int dequeue(){
        if (amountInQueue == 0) {
            throw new EmptyQueueException();
        }

        frontValue = queue[frontIndex];
        amountInQueue--;
        frontIndex++;
        if (frontIndex == queue.length) {
            frontIndex = 0;
        }

        return frontValue;
    }

You don't have to set the return value before the exceptional case, as it won't be used if the exception is thrown.

Only the modifications of frontIndex need to be in the if/else.

If you always increment, then you don't have to subtract in the comparison. Saving one math operation in the common case and using the same number in the uncommon case.

Interfaces

There is a Queue interface. You might consider having this code implement that interface. That will force you to name the operations as expected.

public class Queue2 implements Queue {

As is, someone used to the other queue might have trouble finding the equivalents of add, remove, and peek.

Bug?

In your valueAtFront and valueAtRear methods, you don't verify that there are elements in the queue. So these may return garbage. They should either throw an exception or return something like null when the queue is empty.

Resize

It's pretty common to allow queues to resize. Something to consider for future development.

Answer 2

Bug 1

Starting from an empty queue, if you enqueue and dequeue a single element it will advance frontIndex but not rearIndex. This causes the queue to get out of sync. For example, this snippet:

  Queue2 q = new Queue2(3);
  for (int i=0;i<4;i++) {
      q.enqueue(i);
      System.out.println(q.dequeue());
  }

should output 0 1 2 3 but instead outputs 0 0 0 3.

Bug 2

If you enqueue capacity-1 elements, then dequeue them all, and then enqueue one more element, there will be a bug. You will move rearIndex back to 0 and put the new element there, but frontIndex will still be at capacity-1. Therefore the next element you dequeue will be from the wrong spot.

No need for special case

The common problem for both of the bugs is that you have a special case in enqueue() that is unnecessary. If instead of handling an empty queue in a special way, you simply did:

    queue[rearIndex++] = valueToAdd;
    if (rearIndex >= queue.length)
        rearIndex = 0;

then it would fix both of the bugs.