CODEWITHSUNDEEP
javaalgorithm
lightning_missile
lightning_missile

Reputation: 2992

enqueue operation in queue

I come across this enqueue example from robert sedgewick's booksite http://algs4.cs.princeton.edu/13stacks/ResizingArrayQueue.java.html

public void enqueue(Item item) {
    // double size of array if necessary and recopy to front of array
    if (N == q.length) resize(2*q.length);   // double size of array if necessary
    q[last++] = item;                        // add item
    if (last == q.length) last = 0;          // wrap-around
    N++;
}

I don't know this code:

    if (last == q.length) last = 0;          // wrap-around

Rapp around? Does this mean when our array is full it will begin replacing the previous items? Why would we do this? Shouldn't we throw an exception if the next item cannot be added?

And this is the last lines from the resize method:

    q = temp; //now the array is doubled
    first = 0;
    last  = n; //n is the original array size before doubling

Since n and last will both be incremented in the enqueue method, and if n becomes equal to q.length the size of q will double, so it's like the if statement will never be true?

Upvotes: 0

Views: 904

Answers (1)

laune
laune

Reputation: 31290

"Wrap around" is the idiom for saying that something in limited room exceeds one end and is continued at the other end. Here, "busy" elements N < q.length will, after appending at the end and removals up front, eventually "wrap around".

This is resize in full; it takes care of first, last after moving; it removes a wrap around, if there is one.

// resize the underlying array
private void resize(int max) {
    assert max >= N;
    Item[] temp = (Item[]) new Object[max];
    for (int i = 0; i < N; i++) {
        temp[i] = q[(first + i) % q.length];   // <<< !!!
    }
    q = temp;
    first = 0;
    last  = N;
}

Note that what was previosly at array elements first,...last-1,0,...,last-1 has been copied to 0, 1, ... N-1.

if (last == q.length) last = 0;

This will only be executed when no resizing takes place; it handles the case that the new element would have to be placed at the array element just after the last array element.

Upvotes: 1

Related Questions