Question

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:

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.

Copy all entries into a larger array.

Is there anything obvious I'm missing?

Answer 1

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