3
\$\begingroup\$

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 < front && (!isEmpty())) {
            for (int i = front; i < maxSize; i++) {
                System.out.println(queArray[i]);
            }

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

        }

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

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

    }

}
\$\endgroup\$
0
1
\$\begingroup\$

The !isEmpty() check is duplicated. You can simplify the conditions a bit if you move the isEmpty() check before the others:

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

    if (isEmpty()) {
        System.out.println("Queue is Empty!");
    } else if (rear < front) {
        for (int i = front; i < maxSize; i++) {
            System.out.println(queArray[i]);
        }
        for (int i = 0; i <= rear; i++) {
            System.out.println(queArray[i]);
        }
    } else if (front >= rear) {
        for (int i = front; i <= rear; i++) {
            System.out.println(queArray[i]);
        }
    }
}

If you look at it this way, something looks a bit strange:

} else if (rear < front) {
    // ...
} else if (front >= rear) {
    // ...
}

If you flip the direction of the operands in the second else if:

} else if (rear < front) {
    // ...
} else if (rear <= front) {
    // ...
}

The <= can be changed to == because at that point we know that rear cannot be less than front.

The above transformations don't change the meaning of your code, it should work exactly the same way as before. So if there are problems with the original solution, they would still be there after these transformations.

Minor things

There are several redundant parentheses in many places in the code, for example:

return (nItems == 0);
// ...
return (nItems == maxSize);
// ...
if (rear < front && (!isEmpty())) {

Could have been simply:

return nItems == 0;
// ...
return nItems == maxSize;
// ...
if (rear < front && !isEmpty()) {
\$\endgroup\$
7
  • \$\begingroup\$ So for the display method other than isEmpty being a duplicate i can assume my solution is correct? \$\endgroup\$ – user2733436 Aug 3 '14 at 19:13
  • 1
    \$\begingroup\$ I updated my answer. I didn't change the logic of your code, so if the original has bugs, the transformed version will have the same bugs too. Not fully working code is considered off-topic on this site. \$\endgroup\$ – janos Aug 3 '14 at 19:43
  • \$\begingroup\$ It's not called brackets :) What you mean is parentheses. \$\endgroup\$ – Vogel612 Aug 4 '14 at 6:05
  • \$\begingroup\$ @Vogel612 do you have an authoritative source? How bad is it to call them brackets? You're the first to point this out, and I've been calling them this way since forever (sometimes round brackets to disambiguate). Judging by this wikipedia page, it's not so obviously wrong en.wikipedia.org/wiki/Bracket#Parentheses_.28_.29 \$\endgroup\$ – janos Aug 4 '14 at 7:10
  • \$\begingroup\$ @janos I was taught in class that brackets are those: [], braces are those: {}, and parentheses are those: (). I hope that this is true, because else I'd have to fear for the quality of german education... \$\endgroup\$ – Vogel612 Aug 4 '14 at 8:15
2
\$\begingroup\$

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 < 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 < nItems; i++) {
                System.out.println(queArray[adjust(front + i)]);
            }
        }
    }

}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.