RootishArrayStack: A Space-Efficient Array Stack

Since the data structures that we have studied so far store their data in one or two arrays and avoid resizing these arrays too often, the arrays frequently are not very full. For example, immediately after a resize() operation on an ArrayStack, the backing array is only half full. Even worse, there are times when only one-third of it contains data.

Visual demonstration

A sequence of add(i, x) and remove(i) operations on a RootishArrayStack is illustrated below. Arrows denote elements being copied.

In this lesson, we discuss the RootishArrayStack data structure, that addresses the problem of wasted space. The RootishArrayStack stores $n$ elements using $O(\sqrt n)$ arrays. In these arrays, at most $O(\sqrt n)$ array locations are unused at any time. All remaining array locations are used to store data. Therefore, these data structures waste at most $O(\sqrt n)$ space when storing $n$ elements.

A RootishArrayStack stores its elements in a list of $r$ arrays called blocks that are numbered $0,1,...,r−1$. See the above slides. Block $b$ contains $b + 1$ elements. Therefore, all $r$ blocks contain a total of

$$1+2+3+\cdots +r=r$$ ...