RootishArrayStack：高效节省空间的数组栈

### RootishArrayStack：高效节省空间的数组栈 #### 1. 引言 在数据存储和处理中，数据结构的选择至关重要。许多传统的数据结构在存储数据时，由于避免频繁调整数组大小，导致数组常常不能被充分利用，造成了空间的浪费。例如，在`ArrayStack`执行`resize()`操作后，底层数组`a`可能只有一半被使用，甚至有时只有三分之一的空间存储了数据。为了解决这个问题，我们引入了`RootishArrayStack`数据结构。 #### 2. DualArrayDeque的特性总结 在深入了解`RootishArrayStack`之前，先回顾一下`DualArrayDeque`的特性。`DualArrayDeque`实现了`List`接口，在忽略`resize()`和`balance()`操作的成本时，具有以下特性： - **`get(i)`和`set(i,x)`操作**：每次操作的时间复杂度为$O(1)$。 - **`add(i,x)`和`remove(i)`操作**：每次操作的时间复杂度为$O(1 + min{i,n - i})$。 并且，从一个空的`DualArrayDeque`开始，任何由$m$次`add(i,x)`和`remove(i)`操作组成的序列，在所有`resize()`和`balance()`调用中总共花费的时间为$O(m)$。 #### 3. RootishArrayStack的介绍 `RootishArrayStack`是一种用于解决空间浪费问题的数据结构。它使用$O(\sqrt{n})$个数组来存储$n$个元素，在这些数组中，任何时候最多只有$O(\sqrt{n})$个数组位置未被使用，其余位置都用于存储数据。因此，在存储$n$个元素时，该数据结构最多浪费$O(\sqrt{n})$的空间。 ##### 3.1 存储结构 `RootishArrayStack`将元素存储在一个名为`blocks`的数组列表中，这些数组被称为块，编号从$0$到$r - 1$。每个块`b`包含$b + 1$个元素，因此所有$r$个块总共包含的元素数量为： $1 + 2 + 3 + \cdots + r = \frac{r(r + 1)}{2}$ 元素在块内按顺序排列，索引为$0$的元素存储在块$0$中，索引为$1$和$2$的元素存储在块$1$中，索引为$3$、$4$和$5$的元素存储在块$2$中，依此类推。 ```mermaid graph LR classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; A(块0: 1个元素):::process --> B(块1: 2个元素):::process B --> C(块2: 3个元素):::process C --> D(块3: 4个元素):::process D --> E(块4: 5个元素):::process ``` ##### 3.2 索引计算 在`RootishArrayStack`中，一个关键问题是如何根据索引$i$确定元素所在的块以及该元素在块内的索引。 - **确定元素在块内的索引**：如果索引$i$位于块$b$中，那么块$0$到$b - 1$中的元素总数为$\frac{b(b + 1)}{2}$。因此，元素$i$在块$b$内的位置为： $j = i - \frac{b(b + 1)}{2}$ - **确定元素所在的块**：索引小于或等于$i$的元素数量为$i + 1$，而块$0$到$b$中的元素数量为$\frac{(b + 1)(b + 2)}{2}$。因此，$b$是满足$\frac{(b + 1)(b + 2)}{2} \geq i + 1$的最小整数。通过求解二次方程$b^2 + 3b - 2i = 0$，我们得到两个解$b = \frac{-3 + \sqrt{9 + 8i}}{2}$和$b = \frac{-3 - \sqrt{9 + 8i}}{2}$。由于第二个解总是为负数，不符合实际情况，所以我们取$b = \left\lceil\frac{-3 + \sqrt{9 + 8i}}{2}\right\rceil$。 以下是实现该计算的代码： ```java RootishArrayStack int i2b(int i) { double db = (-3.0 + Math.sqrt(9 + 8*i)) / 2.0; int b = (int)Math.ceil(db); return b; } ``` #### 4. RootishArrayStack的基本操作 ##### 4.1 `get(i)`和`set(i,x)`操作 在确定了元素所在的块和块内索引后，`get(i)`和`set(i,x)`操作就变得很简单。首先计算出合适的块$b$和块内索引$j$，然后执行相应的操作。 ```java RootishArrayStack T get(int i) { int b = i2b(i); int j = i - b*(b+1)/2; return blocks.get(b)[j]; } T set(int i, T x) { int b = i2b(i); int j = i - b*(b+1)/2; T y = blocks.get(b)[j]; blocks.get(b)[j] = x; return y; } ``` 如果使用本章中的任何数据结构来表示`blocks`列表，`get(i)`和`set(i,x)`操作都可以在常数时间内完成。 ##### 4.2 `add(i,x)`操作 `add(i,x)`操作的步骤如下： 1. 检查数据结构是否已满，即检查块的数量$r$是否满足$\frac{r(r + 1)}{2} = n$。如果是，则调用`grow()`方法添加一个新块。 2. 增加元素数量$n$。 3. 将索引为$i$到$n - 1$的元素向右移动一个位置，为新元素腾出空间。 4. 在索引$i$处插入新元素。 ```java RootishArrayStack void add(int i, T x) { int r = blocks.size(); if (r*(r+1)/2 < n + 1) grow(); n++; for (int j = n-1; j > i; j--) set(j, get(j-1)); set(i, x); } ``` `grow()`方法的实现如下： ```java RootishArrayStack void grow() { blocks.add(newArray(blocks.size()+1)); } ``` 忽略`grow()`操作的成本，`add(i,x)`操作的成本主要由元素移动决定，因此时间复杂度为$O(1 + n - i)$，与`ArrayStack`类似。 ##### 4.3 `remove(i)`操作 `remove(i)`操作与`add(i,x)`操作类似，步骤如下： 1. 获取索引为$i$的元素。 2. 将索引为$i + 1$到$n$的元素向左移动一个位置。 3. 减少元素数量$n$。 4. 如果有多个空块，则调用`shrink()`方法移除除一个空块之外的所有空块。 ```java RootishArrayStack T remove(int i) { T x = get(i); for (int j = i; j < n-1; j++) set(j, get(j+1)); n--; int r = blocks.size(); if ((r-2)*(r-1)/2 >= n) shrink(); return x; } ``` `shrink()`方法的实现如下： ```java RootishArrayStack void s ```