# Extending the implementation of a Queue using a circular array

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?

-
I'm guessing the question has more to do with how you adjust the indices and entries in the vector/array than with how you declare them. At least that's what I would focus on if I were marking this question, especially if the exam is on algorithmics. – Pedro Apr 18 '12 at 10:11
What's the cost of doing this (you nearly give it but aren't presenting it as such)? Can you find ways to avoid that cost? What are the drawbacks of the alternatives? – AProgrammer Apr 18 '12 at 11:10
Please try to state the question in a way that makes it applicable to other programming languages. In the meantime, voting to close as "too localized". – Raphael Apr 18 '12 at 18:36
@Raphael I've edited (I hope correctly) to explain the difference between an array (not resizable) and a vector (resizable). Now the question is essentially language-agnostic (applies to any language with mutable arrays). – Gilles Apr 18 '12 at 22:53
@Raphael It's certainly a possible implementation, I don't know whether it's mandated by the language definition. In any case I think only the semantic distinction between resizable and non-resizable arrays is useful to understand and answer the question, not the language-specific details. – Gilles Apr 19 '12 at 17:26

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

-
 Many thanks Gilles, its answers like this that keep me coming back to the stack community. – Alex Jun 4 '12 at 12:02

As explained by Guillaume13, Vector is deprecated and therefore the usage should be discouraged. There is the ArrayList class though, which basically does the same but is more up to date in the Java world.

Considering your the actual question, I think both answers are more or less equally good, as the term "extend" can be interpreted quite vast. Both design ideas would work and do their job, but not perfect (as already pointed out by Gilles), therefore they are, interpreting the task, as to program a flexible queue, not perfect.

Depending if you have to keep an "true" array (which is by design not flexible) the second might be the more fitting choice, though.

In my opinion a lisp-like list, where you just work with cells storing a value and a pointer to the next cell, would be the best answer if you are allowed to discard the old implementation. But I am not sure if such a revolutionizing design, considering your starting point, would still be within the reach of of the question.

-

In java, Response 2 because : in the Memory management logic : an array is an array and to expends it you have to copy it. The fact is in most of high level language the array_copy is a native fast function so it's extremly efficient. Java Vector is deprecated and strongly discouraged since many year.

-

Ummmm... isn't the point of a circular array to wrap around and store some of the data at the beginning? Isn't it just to simply overlap data to fill in bits not already filled, but can be filtered out by using the % operator? Or am I completely wrong?

-
 The question is what to when the array (or other data structure) is full and you want to add an element. – Gilles♦ Apr 21 '12 at 20:19