Não vou entrar no mérito tradicional, que creio que as respostas do [Maniero](https://pt.stackoverflow.com/a/433652/64969) e [OnoSendai](https://pt.stackoverflow.com/a/434618/64969) 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](https://pt.stackoverflow.com/q/276648/64969). Esses problemas pertencem a classe `RE`. Todos os problemas dentro dessa classe podem ser resolvidos por uma [máquina de Turing](https://pt.stackoverflow.com/q/158043/64969). > 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](https://pt.stackoverflow.com/q/354665/64969) ------ Um outro ponto que eu gostaria de ressaltar aqui, sobre [autômatos](https://pt.stackoverflow.com/q/260864/64969): - 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