stack - スタック、有界スタック、Liskov 置換プロパティ

Question

Liskov置換プロパティに違反することなく、境界付きスタックデータ構造(上限のあるスタック)を従来のスタックのサブタイプとして実装できますか?

従来のスタックは制限付きスタックの代わりに使用できますが、制限付きスタックは、制限が十分に大きい場合にのみ、従来のスタックの代わりに使用できます。私はこの考えで正しいですか？

liskov プロパティは逆に真ですか?

ありがとう。

Answer 1

リスコフの置換原則は次のように述べられています

q（x）をタイプTのオブジェクトxについて証明可能なプロパティとします。次に、タイプSのオブジェクトyに対してq（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 以上の制限付きスタックは、「従来の」スタックの代わりに完全に使用できます。容量について特に約束しない場合は、任意の容量の制限付きスタックが代用可能です。