7

Existe uma vantagem na implementação do conceito LIFO (Last In, First Out) ou é só uma questão semântica para representar uma ordem na lógica do algoritmo?

6 Respostas 6

12

A pura aplicação desse conceito de UEPS (Último a Entrar, Primeiro a Sair) não traz uma vantagem óbvia inerente. A sua aplicação de uma forma específica pode ser bem vantajosa. O conceito em si é amplo demais para indicar uma vantagem.

O LIFO é quase sinônimo de pilha (stack) quando falamos de computação. Parte da vantagem de ter uma pilha já foi respondida em O que são e onde estão a "stack" e "heap"?. E há uma outra resposta sobre pilha que ajuda entender: Como funciona e se usa o Stack em C#?.

Sem uma forma de pilha pura pode não ter tanta vantagem assim. É possível implementar o LIFO como uma lista ligada, por exemplo, e assim fica bem ruim e não traz vantagens claras do ponto de vista de computação em geral.

É possível aplicar o LIFO em algo porque a semântica do problema exige isso, mas aí não podemos falar em vantagem computacionais, é um requisito do problema.

Para a computação a pilha geral ou a pilha de chamadas/alocação de memória local são os maiores exemplos do uso do conceito, mas o ganho se dá mesmo porque é uma pilha.

Então a pilha é vantajosa porque não tem que que manter nada sofisticado onde começa e acaba a coleção de dados, não é difícil percorrê-la, e principalmente é barato incluir e excluir novos elementos na coleção. Como só pode adicionar no topo da pilha (last in) não tem maiores processamentos necessários, desde que tenha espaço disponível, e como só pode remover o que está no topo da pilha (first out) é só mudar o que é o topo da pilha sem nenhum processamento extra, pegando o dado que está ali fácil e sempre de forma direta (O(1)).

Já a aplicação de pilhas, além dos domínios específicos que precisam da semântica específica que o que entra por último é o primeiro a sair (menores valores próximos ou o vizinho mais próximo, histórico de ações para fazer rollback), em computação tem muita aplicação, por exemplo backtrackings diversos (em geral analisando dados aninhados), parsing em vários níveis e modalidades, gerenciamento chunks de heap livres (em alguma implementações) e alguns gerenciamentos de agendamento de processador, Depth-first search, e as já citadas no começo da pergunta, além da mais óbvia que é a recursão.

Coloquei no GitHub para referência futura.

11

Não acredito que a aplicação do conceito de estrutura LIFO (ou a variante semântica FILO - First In, Last Out) seja uma questão de vantagem, mas sim de adequação ao requisito de um dado processo.

Como exemplo, considere o processo de transações aninhadas de um banco de dados. Certos comportamentos são esperados:

  • Alterações dos dados só serão disponibilizadas quando uma transação sofrer confirmação (via commit);
  • Transações subsequentes definem um escopo próprio, onde a transação-parente só terá acesso aos dados alterados na transação-filha quando esta for confirmada.

Agora imagine uma situação onde uma transação T1 é iniciada, seguida de uma nova transação T2. A estrutura de aninhamento pode ser descrita como uma fila LIFO, onde T2 foi o último membro a ser enfileirado.

Caso a confirmação da transação T1 seja requerida pelo usuário o banco de dados pode decidir entre duas opções:

  • Informar que a ação não é possível devido a outras transações pendentes (simplesmente verificando se T1 está no topo da pilha), ou
  • Realizar a confirmação de todas as transações listadas na estrutura LIFO, começando pelo último membro adicionado (T2).
0
6
+50

Não vou entrar no mérito tradicional, que creio que as respostas do Maniero e OnoSendai já respondem o núcleo da questão, mas vou entrar na real vantagem de se usar pilhas em algumas classes de problemas. Portanto, espere ver classes de complexidade nesta resposta e se, por acaso, o termo "classe de complexidade" não fizer sentido pra você, então essa resposta não acrescentará muito.

Em problemas de decisão, existem alguns problemas que é possível responder, em tempo finito, se a resposta para ele é sim. Em compensação, talvez não seja capaz de responder não. O exemplo mais típico desses problemas em que há resposta para sim porém talvez não haja resposta para não é o problema da parada. Esses problemas pertencem a classe RE. Todos os problemas dentro dessa classe podem ser resolvidos por uma máquina de Turing.

O nome RE significa recursivamente enumerável

Em compensação, temos uma outra classe de problemas: aqueles que se responde não em tempo finito, porém não necessariamente se responde sim em tempo finito. Esses problemas pertencem a co-RE.

O prefixo co significa "complemento", sendo o complemento entendido como sendo a operação de complemento da Teoria dos Conjuntos

E existem aqueles problemas que você consegue responder em tempo finito sim ou não. Esses problemas estão na interseção de RE e co-RE, a chamada classe R.

O nome R significa recursivo

Enquanto que para problemas RE você necessita de uma máquina de Turing com plena capacidade, para problemas R você consegue resolução com uma máquina de Turing com uma fita de tamanho finito dependente da entrada.

Tá, mas o que isso significa no final das contas?

Quando você está verificando para saber se é possível responder, você tem uma fita da máquina de Turing preenchida com a cabeça posicionada em um local arbitrário, e a máquina está em outro estado arbitrário. A partir daí, você tem uma quantidade finita de mudanças:

  • os estados que a máquina de Turing pode assumir são definidos por um conjunto finito S
  • os símbolos que a máquina de Turing pode preencher em uma célula da fita são limitados pelo conjunto finito Σ
  • a máquina de Turing pode ir pra esquerda na fita ou ir pra direita na fita
    • existem alguns autores que falam de uma terceira possibilidade: da máquina de Turing continuar na mesma posição

Logo, o próximo estado está em uma quantidade finita de opções para se buscar. Se o problema for R, isso significa que existe uma profundidade máxima de estados (no grafo de alteração de estado da máquina/fita) que se percorre até encontrar um beco com a resposta sim ou não, o que implica que, se tiver uma resposta positiva, ela está em outro percurso. Lembre-se também que, por conta da máquina de Turing que resolve estes problemas tem um tamanho de fita limitado, isso significa que ela não pode ir continuamente à direita, pois um dia ela irá esbarrar no limite da fita e estará em estado inválido e um Kuegelblitz surgirá e o universo será engolido por um buraco negro formado pela gravidade de fotóns em espaço compacto.

Porém, num problema RE, talvez não seja possível indicar que um caminho chegou ao final do processamento. A máquina de Turing continuará a se deslocar para a direita sem nunca chegar numa conclusão se a resposta para aquele caminho é não.

Na estrutura de resolução desses problemas, se você usar uma pilha (LIFO) para um problema RE, você pode entrar num poço infinito e jamais sairá de lá para investigar outro caminho. O jeito correto de se pesquisar por alguma resposta para problemas desta classe é usando uma fila (FIFO).

Em problemas de classe R, entretanto, usar uma pilha pode apresentar uma resposta mais rapidamente, pois você estará indo em profundidade no problema. Uma busca em largura exige verificar muitos caminhos intermediários que, talvez, não levem à resposta, sem falar que necessitam de uma memória sem limites.

Então, no final das contas:

  • a pilha oferece menor capacidade de busca em termos de classes de problemas que se resolve com buscas
  • a pilha oferece um limite menor de memória máxima usada para problemas que de fato ela consegue resolver
  • potencialmente a pilha responderá mais rapidamente um sim para o seu problema

Veja mais sobre busca em largura x busca em profundidade


Um outro ponto que eu gostaria de ressaltar aqui, sobre autômatos:

  • autômatos de pilha conseguem responder problemas que podem ser representados por uma linguagem livre de contexto
  • autômatos de fila são equivalentes em poder de resolução de problemas à máquinas de Turing
0

Quanto ao assunto Estruturas de Dados, temos 2 as Pilhas e Filas, cada qual com seu comportamento e propósito.

Na Fila, temos o comportamento FIFO (First Input, First Output), onde o Primeiro Elemento a Entrar deve ser o Primeiro Elemento a Sair.

Então, na Fila (FIFO), temos dois pontos, um de Entrada e outro de Saída.

Na Pilha, temos o comportamento LIFO (Last Input, First Output), onde o Último Elemento a Entrar deve ser o Primeiro a Sair.

Então, na Pilha (LIFO), temos um único ponto de Entrada e Saída.

3
  • 4
    Parece que você está misturando os conceitos
    – bfavaretto
    Commented 31/01/2020 às 20:40
  • Obrigado Favaretto, você estava certo! Acabei misturando os dois conceitos em minha explicação - agora já corrigido! Commented 2/02/2020 às 2:22
  • A confusão acabou, mas a resposta mão responde a pergunta, apenas repete o que já é conhecido.
    – Maniero
    Commented 6/02/2020 às 21:12
-1

O uso da estrutura de dados pilha é uma das maneiras de calcular o resultado de uma expressão algébrica utilizando a notação polonesa inversa para representar a expressão. Na prática utilizamos a notação infixa, quando o operador aparece entre os operandos aos quais se aplica, acrescido do uso de parênteses para definir a ordem de cálculo, o que não é nada prático para o uso em computadores. Na notação polonesa a ordem operandos - operador é alterada para a notação pós-fixada e os parênteses são eliminados, vide algoritmo shunting-yard

-3

Não existem vantagens, depende da necessidade de cada aplicação.

Um exemplo de uso de LIFO são funções recursivas, onde você precisa retornar as chamadas na ordem inversa, da última para a primeira.

Já em uma fila de integração de dados com uma Web API você precisa que a ordem de envio seja do mais antigo para o mais recente, ou seja, uma FILO.

3
  • 3
    O que essa resposta difere das outras já existentes aqui? Não estou vendo nenhuma informação a mais em comparação às demais que já existiam antes Commented 6/02/2020 às 21:00
  • Apenas um exemplo mais simplificado, não gosta é só pular. Commented 6/02/2020 às 21:24
  • 1
    a propósito, o conceito de LIFO e FILO são equivalentes. Uma fila é FIFO. E uma API web não precisa retornar em ordem crescente de datas, apesar de isso ser conveniente para muitas aplicações Commented 6/02/2020 às 21:46

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .