栈、有界栈与Liskov代换性质

Question

有界堆栈数据结构(具有上限的堆栈)可以在不违反Liskov替换属性的情况下作为常规堆栈的子类型实现吗？

可以使用传统堆栈来代替有界堆栈，但是只有当有界堆栈具有足够大的限制时，才可以使用有界堆栈来代替传统堆栈。我的想法正确吗？

liskov属性反之成立吗？

谢谢。

Answer 1

Liskov替代原理被表述为

设q(x)是关于类型T的对象x的一个可证明的性质，则q(y)对于类型S的对象y应为真，其中S是T的子类型。

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

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

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

因此，这个原则是不成立的。

Answer 2

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

Answer 3

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