Extending the implementation of a Queue using a circular array

Problem Detail: 

I'm doing some exam (Java-based algorithmics) revision and have been given the question:

Describe how you might extend your implementation [of a queue using a circular array] to support the expansion of the Queue to allow it to store more data items.

The Queue started off implemented as an array with a fixed maximum size. I've got two current answers to this, but I'm not sure either are correct:

1. Implement the Queue using the Java Vector class as the underlying array structure. The Vector class is similar to arrays, but a Vector can be resized at any time whereas an array's size is fixed when the array is created.

2. Copy all entries into a larger array.

Is there anything obvious I'm missing?

Asked By : Alex

Answered By : Gilles

Using the Vector class is certainly a possibility, as a practical matter. Other solutions will amount to implementing functionality that is similar to what the Vector class provides (possibly in a way that is more efficient given that the data structure stores a queue).

Some languages offer inherently resizable arrays. For example, in C, to allocate an array, you allocate a block of memory of the required size with the malloc function, and you can later resize this block without affecting the data in the remaining part (when shrinking) or the initial part (when extending). Under the hood, realloc may allocate a new region (at a different address in memory) then copy the data, but it'll try to extend or shrink the region in place for efficiency, in which case no copying is necessary.

Most high-level languages do not support resizing existing memory regions. This is because resizing might change the address of the object, which requires modifying all references to that object — C gets away with it by shifting the burden of updating references to the programmer. If you want a resizable array, you can achieve that manually: access the array through an indirect reference, and when you want to resize the array, allocate a new array, copy the data and assign the indirect reference to the new array.

As a simple optimization, if the array size shrinks by a small amount (say, because you take an element from the queue), do not shrink the array: you'll waste a bit of space, but avoid incessantly reallocating the array and moving the data around if successive elements are removed. And if the array size increases by a small amount (say, because you push an element onto the queue), increase the array size by a margin over the requested amount, so that the array will still be good for the next few increases. The Vector class in Java does this: it maintains an elementCount for the array that contains the data; array elements beyond this position are not used.

Asymptotically, you get good behavior by varying the array size exponentially, for example sticking to powers of 2: if you add an element to a 128-element queue, resize the array to 256; if you remove an element from a 65-element queue (in a 128-element array), resize the array down to 64. With array sizes of the form $a^n$, the wasted space is at most $(a-1)$ times the array size. The cost of reallocations, dominated by moving elements when crossing a size boundary is $\Theta(a^n)$. Amortized over a sequence of additions from an empty array or a sequence of removals until the array is empty, the cost of reallocations is $\Theta(a^n/a^n) = \Theta(1)$. In general the amortized cost of reallocations is $O(1)$.

There are other implementations of resizable arrays that avoid reallocation altogether, at the cost of having slower access time to elements. Avoiding reallocations is especially good to avoid long pauses when a reallocation happens and a lot of data needs to be moved around. A simple one is to maintain a list or array of arrays of exponentially increasing size. The element number $2^i + j$ with $j < 2^i$ is stored at position $j$ in array number $i$. No data ever needs to be copied when the array grows or shrinks (except for the bookkeeping data to maintain the collection of array, which grows logarithmically over the total size).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1336