java - 我的教授所说的 "Implementing a static Abstract Data Type"是什么意思？

Question

在我的类作业中，我们制作了两种不同的抽象数据类型，Double Stack 和 Leaky Stack。我创建这些没有问题，但我的教授在这两个 ADT 的分配细节中添加了“提供 ADT 的高效静态实现”。但这到底是什么意思？我可以明天问他，但我想今天完成这项任务。有人知道他的意思吗？

Answer 1

一种可能的解释是，解决方案是使用固定大小的“静态”底层结构(例如数组)，而不是使用动态增长的数量。因此，每个堆栈都会有一个预先分配的最大容量。因此，我希望在超过堆栈容量的 push(...) 操作上抛出异常(就像 pop() 操作一样)扔到一个空堆栈上)。

静态实现的示例(尽管它允许设置总容量)可能如下所示。这里的访问总是O(1)，因为直接使用索引，没有遍历数据结构，也没有重新分配内存。请注意，代码是示例，尚未经过测试。如果所讨论的方法指定了特定类型的堆栈(例如 int 或 char)，则可以删除 Generic 的使用。

public class AnotherStack<T>
{
  private final T[] values;
  private int loc = 0;

  // must use the suppress, as we are using a raw Object array
  //   which is necessitated as cannot make a generic array  
  // See Effective Java
  @SuppressWarnings("unchecked")
  public AnotherStack(int size)
  {
    values = (T[])new Object[size];
  }


  public void push(T val)
  {
      if (loc < values.length) {
          values[loc++] = val;
      }
      else {
          throw new IllegalStateException("Stack full");
      }
  }

  public T pop()
  {
      if (loc == 0) {
          throw new IllegalStateException("Stack empty");
      }
      return (values[--loc]);
  }

  // other methods
}