1

My dequeue method currently does not delete the item I wish for it too, instead it deletes the last element from the collection. For example,

If I add in the elements: 1, 2, 3 My toString method will return 1, 2, 3 as expected.

Then when I use my driver to call dequeue, it should dequeue the 0th element, 1 in this case.

Although, the method says "Removed element 1 from the queue" prompting that the T result variable has embodied the correct value, although the method does not work as expected, as when calling the toString method after to print the contents, it will print: 1, 2

Then when I call the enqueue method again, on the same queue, if I enqueue the String 3, it will print this as the new queue: 3, 2, 3

I am confused as to where my logic error is, as I assume it is with the extreme case of the collection being filled, but I still run into errors with my dequeue method when the collection is not at max. I attached my code below.

public class QueueRA<T> implements QueueInterface<T> {

    protected T[] items;
    protected int front, back, numItems; 
    
    @SuppressWarnings("unchecked")
    public QueueRA() {
        front = 0;
        numItems = 0;
        back = 0;
        items = (T[]) new Object[3];    
    }
    
    @Override
    public boolean isEmpty() {
        return numItems == 0;
    }

    @Override
    public void enqueue(T newItem) throws QueueException {
        if(numItems == items.length) {
            resize();
            enqueue(newItem);
        }
        else {
            items[back] = newItem;
            back = (back + 1) % items.length;
            numItems++;
        }
    }

    @Override
    public T dequeue() throws QueueException {
        T result;
        if(numItems != 0) {
            result = items[front];
            items[front] = null;
            front = (front + 1) % items.length;
            numItems--;
        }
        else {
            throw new QueueException("The queue does not contain any elements.");
        }
        return result;
    }

    @SuppressWarnings("unchecked")
    @Override
    public void dequeueAll() {
        back = 0;
        front = 0;
        numItems = 0;
        items = (T[]) new Object[3];
    }

    @Override
    public T peek() throws QueueException {
        T result;
        if(numItems != 0) {
            result = items[front];
        }
        else {
            throw new QueueException("The queue does not contain any elements.");
        }
        
        return result;
    }
    
    /**
     * 
     */
    @SuppressWarnings("unchecked")
    protected void resize() {
        T[] newItems = (T[]) new Object[numItems+4];
        
        for(int i = 0; i < numItems; i++) {
            newItems[i] = items[i];
        }
        
        this.front = 0;
        this.back = numItems;
        this.items = newItems;
    }

    /**
     * 
     */
    public String toString() {
        String toReturn = "";
        for(int i = 0; i < numItems; i++) {
            if( (i+1) == numItems) {
                toReturn = toReturn.concat(items[i] + " ");
            }
            else {
                toReturn = toReturn.concat(items[i] + ", ");
            }
        }
        return toReturn;
    }
    
}
Improve this question
2
  • 1
    Obviously your resize is wrong... At the first look you are setting front to 0 but copy array as is(without reordering) Commented Oct 12, 2020 at 23:40
  • @Selvin The resize should not effect the dequeue method though, in the terms of only having the three elements in the queue, correct? I am not really following how fixing the resize would fix the other errors. Sorry for sounding dumb I just have been at this for a while and still can't nip it. Commented Oct 12, 2020 at 23:46

2 Answers 2

Reset to default
1

Your toString() and resize() methods are wrong.

In your example code, you created an arraySize of 3 initially and then added 1, 2, and 3. This occupies all the 3 slots in the array and your numItems is set to 3. The front is set to 0 and back is also set to 0 because after adding 3, your algorithm is:

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

back was initially 2. Now it is calculated as:

-> (2+1)%3
-> 3%3
-> 0

So your back is 0 at this moment.

Now, when you call dequeue(), the front pops 1 out. So now your array looks like this:
items[0] -> empty
items[1] -> 2
items[2] -> 3
back = 0
front = 1

So, when you enque next and add 3, your enqueue() method checks that number of items in the system is less than size of the array (2 < 3) and adds 3 to the location pointed by back (which is 0 now) and increments it to 1. So, your array looks like this now:
items[0] -> 3
items[1] -> 2
items[2] -> 3
back = 1
front = 1

Now, in your toString() method, without considering the values of front and back, you start from 0 to end:

for(int i = 0; i < numItems; i++) {
.
.
.
}

What you need to be doing is start at i = front. if front < back, that means that you travel lineraly from "front" to "back" and print everything. If front > back then you do two loops:

for(int i=front; i < arr.length; i++) {
// Code to print arr[i]
}

for(int i=0; i < back; i++) {
// Code to print arr[i]
}

This way, it will print from front to end and then from 0 to back.

Also, your resize method is wrong for the same reason. You cannot copy from 0 to numItems, you need to start the copy at "front" and then progress like how I wrote for the toString(). Doing this will ensure that your queue's order is preserved across multiple resizes.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Adding to @Arun Subramanian's answer.

Your resize() method was simply copying all of the elements sequentially from items to newItems, then setting front = 0 and back = numItems. Which would have been fine if you had implemented the queue sequentially. However, your implementation of a queue is not sequential, it's a circular / ring implementation. Therefor you have to copy the elements in a circular way.

One way to do this is mentioned in @ArunSubramanian's answer, "If front < back, that means that you travel linearly from front to back and print everything. If front > back then you do two loops." Another way is to use a do-while loop with modular arithmetic, as in the following:

@SuppressWarnings("unchecked")
protected void resize() {
    T[] newItems = (T[]) new Object[numItems + 4];
    
    int i = 0; // index used to copy items to newItems
    // do-while used in case the queue is full (i.e. front == back)
    do {
        newItems[i] = items[front];

        // modular arithmetic used to circle back on items
        front = (front + 1) % items.length;
        i += 1;
    } while(front != back);
    
    this.front = 0;
    this.back = numItems;
    this.items = newItems;
}

Similarly your toString() method can be implemented in the following way:

@Override
public String toString() {
    String toReturn = "";
    
    // need this check, otherwise do-while will illegally access items[0]
    if(!isEmpty()) {
        int len = items.length;
        int i = front;
        
        // do-while used in case front == back
        do {
            String delim = ((i+1) % len == back) ? " " : ", ";

            toReturn += items[i] + delim;
            
            i = (i+1) % len; // modular arithmetic used to circle back
        } while(i != back);
    }
    return toReturn;
}
Improve this answer

1 Comment

Thank you for the clarification, I was obviously getting stuck on the circular fashion using mod. Your answer helped me understand how its working/how to implement it

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.