enqueue operation in queue

Question

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?

laune · Accepted Answer · 2014-07-28 11:26:47Z

"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.

Collectives™ on Stack Overflow

enqueue operation in queue

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related