我的教授说"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
}