stack - 堆栈、有界堆栈和 Liskov 替换属性

Question

有界堆栈数据结构（具有上限的堆栈）能否在不违反 Liskov 替换属性的情况下实现为传统堆栈的子类型？

可以使用常规堆栈来代替有界堆栈，但是如果有界堆栈具有足够大的限制，则只能使用有界堆栈来代替常规堆栈。我对这个想法正确吗？

liskov 属性是否相反？

谢谢。

Answer 1

Liskov 替换原理表示为

令 q(x) 是关于 T 类型的对象 x 的可证明性质。那么 q(y) 对于 S 类型的对象 y 应该为真，其中 S 是 T 的子类型。

假设 T 是 Stack 类型，S 是 BoundedStack 类型的 T 的子类型。

现在，让我们将 q(x) 定义为堆栈 x 的容量。

如果 x 是 T 的一个实例，则容量是无限的。如果 x 是 S 的一个实例，那么这不成立，因为容量现在是有界的。

所以原理不成立。

Answer 2

显然有界堆栈会为 push 方法生成一种新类型的异常。所以它不符合LSP。

Answer 3

如果真的有无界堆栈这样的东西，那么有界堆栈就不会是它的子类型。另一方面，“常规”堆栈的语义可能更像是“如果推送的对象数量不超过某个模糊、不可知和任意可变的限制，则推送该对象；否则在一些任意和未定义的情况下失败时尚。” 如果常规堆栈提供 Count 属性并承诺任何 Count 为 1,000 或更少的堆栈将能够接受另一个项目，则容量为 1,000 或更大的有界堆栈将完全替代“常规”堆栈。如果它没有对容量做出任何特别的承诺，那么具有任何容量的有界堆栈都是可以替代的。