数组堆栈中的收缩方法（scala）

Question

我正在尝试实现一个调整大小函数，该函数根据元素数量和 Scala3 中的数组大小来缩小和增大数组堆栈。下面是我的代码：

package adt

import scala.reflect.ClassTag

class ArrayStack[A: ClassTag]:

  private var dataArray: Array[A] = Array.fill(10)(null.asInstanceOf[A])
  private var top: Int = 0
  private var sz: Int = 10

  def push(elem: A): Unit =
    if top == sz then resize(grow = true)
    dataArray(top) = elem
    top += 1

  def pop(): A =
    if top == (sz / 2) - 1 then resize(grow = false)
    top -= 1
    dataArray(top)

  def peek(): A =
    dataArray(top - 1)

  def isEmpty(): Boolean =
    top == 0

  def resize(grow: Boolean): Unit =
    val newSize = if grow then sz * 2 else sz / 2
    val newArray: Array[A] = Array.fill(newSize)(null.asInstanceOf[A])
    for (a <- 0 until dataArray.length) do newArray(a) = dataArray(a)
    dataArray = newArray
    sz = newSize

但是，在我的 JUnit 测试中，我得到一个数组索引越界异常。

  @Test def pushMultiple(): Unit =
    val stack = new ArrayStack[Int]
    val pushArr = Array.tabulate(100)(i => Math.round(i * 100))
    pushArr.foreach(stack.push(_))
    for (n <- pushArr.reverse) do assertEquals(n, stack.pop())

  @Test def popMultiple(): Unit =
    val stack = new ArrayStack[Int]
    val pushArr = Array.tabulate(100)(i => Math.round(i * 100))
    pushArr.foreach(stack.push(_))
    for (i <- 1 to 1000) do stack.pop()
    assertTrue(stack.isEmpty())

错误信息：

    Test arraystack_test.pushMultiple failed: java.lang.ArrayIndexOutOfBoundsException: Index 80 out of bounds for length 80, took 0.032 sec
    at scala.runtime.ScalaRunTime$.array_update(ScalaRunTime.scala:75)
ScalaRunTime.scala:75
    at adt.ArrayStack.resize$$anonfun(ArrayStack.scala:30)
ArrayStack.scala:30
    at scala.runtime.java8.JFunction1$mcVI$sp.apply(JFunction1$mcVI$sp.scala:18)
    at scala.collection.immutable.Range.foreach(Range.scala:190)
Range.scala:190
    at adt.ArrayStack.resize(ArrayStack.scala:30)
ArrayStack.scala:30
    at adt.ArrayStack.pop(ArrayStack.scala:17)
ArrayStack.scala:17
    at arraystack_test.pushMultiple$$anonfun(arraystack_test.scala:26)
    at scala.runtime.java8.JFunction1$mcVI$sp.apply(JFunction1$mcVI$sp.scala:18)
    at scala.collection.ArrayOps$.foreach$extension(ArrayOps.scala:1324)
ArrayOps.scala:1324
    at arraystack_test.pushMultiple(arraystack_test.scala:26)
    at jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
NativeMethodAccessorImpl.java:34
    at jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
NativeMethodAccessorImpl.java:62
    at jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
DelegatingMethodAccessorImpl.java:43
    at java.lang.reflect.Method.invoke(Method.java:566)
Method.java:566
    ...
Test arraystack_test.popMultiple failed: java.lang.ArrayIndexOutOfBoundsException: Index 80 out of bounds for length 80, took 0.0 sec
    at scala.runtime.ScalaRunTime$.array_update(ScalaRunTime.scala:75)
ScalaRunTime.scala:75
    at adt.ArrayStack.resize$$anonfun(ArrayStack.scala:30)
ArrayStack.scala:30
    at scala.runtime.java8.JFunction1$mcVI$sp.apply(JFunction1$mcVI$sp.scala:18)
    at scala.collection.immutable.Range.foreach(Range.scala:190)
Range.scala:190
    at adt.ArrayStack.resize(ArrayStack.scala:30)
ArrayStack.scala:30
    at adt.ArrayStack.pop(ArrayStack.scala:17)
ArrayStack.scala:17
    at arraystack_test.popMultiple$$anonfun(arraystack_test.scala:32)
    at scala.runtime.java8.JFunction1$mcII$sp.apply(JFunction1$mcII$sp.scala:17)
    at scala.collection.immutable.Range.foreach(Range.scala:190)
Range.scala:190
    at arraystack_test.popMultiple(arraystack_test.scala:32)
    at jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
NativeMethodAccessorImpl.java:34
    at jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
NativeMethodAccessorImpl.java:62
    at jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
DelegatingMethodAccessorImpl.java:43
    at java.lang.reflect.Method.invoke(Method.java:566)

谁能帮我弄清楚为什么我的调整大小收缩功能不起作用？

Answer 1

没关系，我想通了。

在调整大小方法中，这会导致索引越界异常

    for (a <- 0 until dataArray.length) do newArray(a) = dataArray(a)

当为增长调用该方法时，它工作正常。但是，调用shrink方法时，newArray的长度是dataArray的一半，所以会导致索引越界异常。

解决这个问题：

  def resize(grow: Boolean): Unit =
    val newSize = if grow then sz * 2 else sz / 2
    val endRange: Int = if grow then dataArray.length else newSize
    val newArray: Array[A] = Array.fill(newSize)(null.asInstanceOf[A])
    for (a <- 0 until endRange) do newArray(a) = dataArray(a)
    dataArray = newArray
    sz = newSize

数组堆栈中的收缩方法（scala）

Shrink method in array stack (scala)

scala

junit

stack