Pilha que estende o LinkedList. Uma violação do princípio de substituição de Liskov?

13

Existe uma classe LinkedList com funções como add_first (), add_last (), add_after (), remove_first (), remove_last () e remove ()

Agora há uma classe Stack que fornece funcionalidades como push (), pop (), peek () ou top (), e para implementar esses métodos, ela estende os métodos da classe LinkedList. Isso é uma violação do princípio de substituição de Liskov?

Por exemplo, considere o caso add_after () para adicionar um nó na enésima posição de uma Lista vinculada. Isso pode ser feito na classe base, mas não na classe Stack. As pós-condições estão sendo enfraquecidas aqui ou você modifica o método add_after () para adicionar ao topo da pilha?

Além disso, se não for uma violação, esse design é ruim? E como você implementaria a funcionalidade Stack usando a classe LinkedList?

design object-oriented object-oriented-design solid liskov-substitution jxvmiranda
fonte
6
A pergunta Qual seria a desvantagem de definir uma classe como uma subclasse de uma lista própria? pergunta sobre um problema um pouco diferente, mas a maioria das respostas também se aplica aqui: é melhor criar uma pilha com uma lista como membro privado em vez de herdar da lista.
amon
7
Sim, este é um design ruim, pois impedirá que você altere a representação interna da pilha para algo diferente de uma lista vinculada (por exemplo, uma matriz). Você também está expondo operações que as pilhas geralmente não suportam. Use composição em vez de herança.
21417 Lee
2
Deseja estender LinkedList? Você pode querer seguir o conselho de um certo Joshua Bloch (que desempenhou um papel importante no design da estrutura de coleções Java) quando ele disse "Preferir composição sobre herança" - Talvez você tenha uma LinkedListclasse dentro de sua pilha, mas na verdade não a estende?
corsiKa
1
Eu diria que não pode satisfazer o princípio de substituição de Liskov, porque "uma pilha é um tipo de lista vinculada" não é uma afirmação verdadeira. "Stack" é realmente uma interface (quero dizer conceitualmente, não a construção Java). Uma pilha pode ser implementada com uma lista vinculada. Como outros já disseram, você usaria um membro de dados particulares do tipo LinkedListque faz o trabalho pesado nos bastidores (composição). Dessa forma, os usuários do seu código não podem usar acidentalmente uma pilha onde precisavam de uma lista ou vice-versa.
Jasmijn
1
Parece que o que seria mais saudável seria o contrário. Se eu estivesse fazendo isso, provavelmente teria uma classe de lista vinculada implementando uma interface de "pilha" como totalmente capaz de fazê-lo. Caso contrário, este é o caminho errado, pois uma pilha é um conceito, uma lista vinculada é uma implementação que pode atuar como uma pilha, entre outras coisas.
Validade

Respostas:

31

Agora há uma classe Stack que fornece funcionalidades como push (), pop (), peek () ou top (), e para implementar esses métodos, ela estende os métodos da classe LinkedList. Isso é uma violação do princípio de substituição de Liskov?

Não. É perfeitamente bom adicionar métodos em um subtipo.

Por exemplo, considere o caso add_after () para adicionar um nó na enésima posição de uma Lista vinculada. Isso pode ser feito na classe base, mas não na classe Stack.

Isso é uma violação do LSP. O LSP diz que instâncias de um subtipo devem ser substituíveis por instâncias de um supertipo sem alterar as propriedades desejáveis ​​de um programa. Se um subtipo remover um método, qualquer código que chamar esse método falhará (ou obterá uma NoMethodErrorexceção ou algo nesse sentido). Claramente, "não travar" é uma propriedade desejável.

As pós-condições estão sendo enfraquecidas aqui ou você modifica o método add_after () para adicionar ao topo da pilha?

Modificar o add_after()método dessa maneira é uma violação da regra de histórico (a mais importante das regras!) E, portanto, não ajuda a corrigir a violação do LSP.

E como você implementaria a funcionalidade Stack usando a classe LinkedList?

Usando composição.

NOTA: Tudo o que escrevi acima se aplica somente a idiomas que confundem subtipagem e subclasse! O LSP é sobre subtipagem , não subclassificação. Em um idioma que não confunda os dois, seria perfeitamente aceitável criar Stackuma subclasse de LinkedList, contanto que você não o torne um subtipo de LinkedList.

Jörg W Mittag
fonte
9
Qual é a regra da história? Não consegui encontrá-lo na internet.
Zapadlo
10
Ao manipular um objeto de um subtipo e observá-lo através de métodos do supertipo, deve ser impossível observar uma história que também não possa ser observada com um objeto do supertipo. Essa regra é a que torna o LSP aplicável a linguagens não funcionais. Todas as outras coisas já eram conhecidas muito antes disso. As regras pré e pós-condição são reformulações das regras de co e contravariância para tipos de funções. A regra do histórico torna tudo isso aplicável a dados mutáveis. Sem ele, o LSP seria útil apenas para linguagens puramente funcionais.
Jörg W Mittag
2
Eu acho que a explicação no artigo da Wikipedia é razoavelmente boa: wikipedia.org/wiki/Liskov_substitution_principle Mas, como sempre, você realmente deve ler a fonte original.
Jörg W Mittag
@ JörgWMittag: Embora eu ache razoável que os tipos incluam no contrato garantias sobre o que a "história" será ou não observada, não acho que seja necessário que todo supertipo seja capaz de produzir todas as seqüências de observações isso pode ser possível em um objeto do subtipo - apenas que o supertipo documenta a possibilidade de que os consumidores do supertipo possam observar essas seqüências.
Supercat
1

Como tudo já foi abordado por Jörg W Mittag, apenas elaborei um pouco a seguinte parte:

As pós-condições estão sendo enfraquecidas aqui ou você modifica o método add_after () para adicionar ao topo da pilha?

Basicamente, quando há uma dúvida sobre se alguma hierarquia viola o LSP, isso depende do contrato que você representa. Então, qual contrato add_aftertem? Se parecer, mesmo que louco, como "Adicionar um nó na n-ésima posição ou na parte superior", então você está bem, a pós-condição é atendida, o LSP não é violado. Caso contrário, é uma violação do LSP.

Zapadlo
fonte