Search code examples
stackliskov-substitution-principle

Stack, bounded stack and Liskov substitution property

Could a bounded stack data structure (a stack with an upper limit) be implemented as a subtype of a conventional stack without violating the Liskov substitution property?

A conventional stack could be used in place of a bounded stack, but a bounded stack may only be used in place of a conventional stack if it has a large enough limit. Am I correct with this idea?

Is the liskov property inversely true?

Thanks.

Solution

  • Liskov substituion princple is stated as

    Let q(x) be a property provable about objects x of type T. Then q(y) should be true for objects y of type S where S is a subtype of T.

    Let us say T is type Stack and S is a subtype of T of type BoundedStack.

    Now, let us define q(x) as the capacity of stack x.

    If x is an instance of T then the capacity is infinite/boundless. If x is an instance of S then this does not hold as the capacity is now bounded.

    Therefore the principle does not hold.