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