Displaying items in a circular queue I am dealing with the following problem:


  Write a method for the Queue class in the queue.java program (Listing 4.4) that displays the contents of the queue.  Note that this does not mean simply displaying the contents of the underlying array.  You should show the queue contents from the first item inserted to the last, without indicating to the viewer whether the sequence is broken by wrapping around the end of the array.  be careful that one item and no items display properly, no matter where front and rear are.


I have managed to solve it, however, I am not sure if my solution is efficient or the best possible solution. I am always willing to learn from my mistakes.  I have posted the code below and in particular please take a look at my display() method and let me know if it's correct and also if I could have written a better solution. I am open to all suggestions and criticism.

public class Queue {

    private int maxSize;
    private int[] queArray;
    private int front;
    private int rear;
    private int nItems;

    public Queue(int s) {
        maxSize = s;
        queArray = new int[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    public void insert(int j) {
        if (rear == maxSize - 1)
            rear = -1;

        queArray[++rear] = j;
        nItems++;

    }

    public int remove() {
        int removed = queArray[front++];
        if (front == maxSize)
            front = 0;

        nItems--;

        return removed;
    }

    public int peek() {
        return queArray[front];
    }

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

    public boolean isFull() {
        return (nItems == maxSize);
    }

    public int size() {
        return nItems;
    }

    public void display() {
        System.out.println("First Inserted Item to Last Inserted Item");

        if (rear &lt; front &amp;&amp; (!isEmpty())) {
            for (int i = front; i &lt; maxSize; i++) {
                System.out.println(queArray[i]);
            }

            for (int i = 0; i &lt;= rear; i++) {
                System.out.println(queArray[i]);
            }

        }

        else if (front &gt;= rear &amp;&amp; (!isEmpty())) {
            for (int i = front; i &lt;= rear; i++) {
                System.out.println(queArray[i]);
            }
        }

        else {
            System.out.println("Queue is Empty!");
        }

    }

}
I realize that you were only supposed to implement the display method, but, the rest of the queue is code that can be significantly improved too.

Your queue is a fixed-capacity queue. There is nothing wrong with that (except that the array should be declared as final ... ), and, it actually makes some things easier.

Like, one of the most complicated things with a circular buffer/queue is to manage whether the queue is full, or empty. at both times, the rear and front cursor are the same. There is a really nice way to solve that problem, which is to not use a rear pointer at all, and to only use the front, and size.

Now, your code has the front, rear, and size variables, and it sometimes uses the rear variable, and other times uses the size... and this leads to confusing code. The thing is, that you can easily calculate the rear from the front and size... or, alternatively, you can calculate any one of those three variables from the other two. Bottom line, is you only need two of them, and keeping the size makes other things easy.

Here's your code, stripping out the entire 'rear' variable.... Other things I did are:


removed the maxSize variable since the queArray's length is the same.
added validation to the insert/remove methods.
some formatting changes
use modulo % operator to 'wrap' indexes nicely in the new adjust() method.


Notice how the display method is now really simple:

public void display() {
    System.out.println("First Inserted Item to Last Inserted Item");

    if (isEmpty()) {
        System.out.println("Queue is Empty!");
    } else {
        for (int i = 0; i &lt; nItems; i++) {
            System.out.println(queArray[adjust(front + i)]);
        }
    }
}


The full code is:

import java.util.NoSuchElementException;

public class Queue {

    private final int[] queArray;
    private int front;
    private int nItems;

    public Queue(int s) {
        queArray = new int[s];
        front = 0;
        nItems = 0;
    }

    /*
     * Simple method converts an un-wrapped index to a wrapped index.
     */
    private final int adjust(int index) {
        // add the array length to make things like adjust(-1) work.
        return (index + queArray.length) % queArray.length;
    }

    public void insert(int j) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        queArray[adjust(front + nItems)] = j;
        nItems++;
    }

    public int remove() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        int removed = queArray[front];
        // for an object-based queue, this would
        // be the same as setting it to null
        queArray[front] = 0;
        front = adjust(front + 1);
        nItems--;
        return removed;
    }

    public int peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return queArray[front];
    }

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

    public boolean isFull() {
        return nItems == queArray.length;
    }

    public int size() {
        return nItems;
    }

    public void display() {
        System.out.println("First Inserted Item to Last Inserted Item");

        if (isEmpty()) {
            System.out.println("Queue is Empty!");
        } else {
            for (int i = 0; i &lt; nItems; i++) {
                System.out.println(queArray[adjust(front + i)]);
            }
        }
    }

}