Pilhas (LIFO) e sua aplicação básica

Pilha.push(4)  // topo: [4]
Pilha.push(7)  // topo: [4, 7]
valor = Pilha.top()  // 7, topo permanece [4, 7]
valor = Pilha.pop()  // remove 7, topo agora [4]
            

class Pilha:
    def __init__(self):
        self._dados = []

    def push(self, x):
        self._dados.append(x)

    def pop(self):
        if self._dados:
            return self._dados.pop()
        raise IndexError("pop de pilha vazia")

    def top(self):
        if self._dados:
            return self._dados[-1]
        raise IndexError("top de pilha vazia")

    def is_empty(self):
        return len(self._dados) == 0
            

n = 13
p = Pilha()
while n > 0:
    p.push(n % 2)
    n = n // 2

binario = ""
while not p.is_empty():
    binario += str(p.pop())

print(binario)  # 1101
            

Texto original

O texto original pode conter falhas de gramática ou de concordância, isso ocorre porque ele foi obtido por um processo de extração de texto automático.

Texto extraído do video Algoritmos e Programação de Computadores II - Pilhas (LIBRAS)

O Lá pessoal, bem-vindos novamente a nossa disciplina de algoritmos e programação de computadores 2.
Essa é a nossa videoaula de número 7, onde a gente vai aprender nesta semana alguns conceitos básicos sobre algumas estruturas de dados que são bastante importantes e úteis para a área de computação.
A ideia é que vocês possam ter essa noção geral sobre elas, para que vocês tenham certa familiaridade, e que, principalmente para os alunos da computação, vocês vão aprender mais detalhes sobre essas estruturas, mas adiante no curso de vocês.
Então, vamos começar essa semana, nesta videoaula, aprendendo um pouquinho sobre as pilhas, que é uma das estruturas de dados que a gente vai ver nesse curso.
Então, a gente pode começar esse assunto com uma motivação.
Imagina que eu tenho um problema que estou começando a executar aqui a função A, e essa função A é implementada por meio de impressão, alguma mensagem, algum caracter na tela, e daí ela mesmo faz a chamada de outras funções.
Então, você começa lá imprimindo o caracquero A, depois ele faz uma chamada para a função C.
Neste caso, aqui, a partir desta linha, ele começa a executar a função C, imprimindo o caracquete C na tela.
Aí, ele continua a função C na linha 2 fazendo uma chamada A, a função D, a função D é, como inicia a execução dela, imprimindo o caracquete D, ele retorna, esse retorna aqui, ele retorna para a função anterior que ele estava antes, que chamou essa função D.
Neste caso, até que é fácil, a gente saber qual é a função anterior, que chamou ela, porque logo, a gente sabe que está logo aqui, mas em certa situações acaba sendo complicado de você lembrar qual foi a função que chamou uma outra função, porque isso pode ser feito de maneira recursiva, uma função chamada outra função, que chamou outra função, que retorna, depois chamou outra função.
Então, o resultado da execução da função A vai depender de você ter que fazer uma análise de todas essas execução, dessas quatro funções que estão aqui, e lembrando qual foi aquela função anterior que chamou ela que acabou de finalizar.
Então, a dificuldade de fazer esse cálculo é exatamente isso, lembrando qual foi essa função que estava antes, e como possíveis soluções, qual seria as soluções para poder resolver este tipo de problema? Então, a dificuldade é essa, o que estava sendo executado quando uma função foi interrompida, para onde voltar agora, que chegou ao fim de uma função, qual seria a solução? A solução é a cada chamada de função armazenar o endereço de retorno, que pode ser, por exemplo, o nome da função e o número da linha onde você estava, e aí como armazenar o endereço de retorno dessas chamadas sucessivas? Então, para isso é onde a gente pode utilizar o conceito de pilha.
Então, vamos entender o porquê disso? Qual é a definição de pilha? Então, uma pilha é uma estrutura para armazenar um conjunto de elementos que funciona da seguinte forma.
Então, novos elementos sempre entram no topo desta pilha, e o único elemento que se pode retirar de uma pilha em um dado momento é o elemento que está neste topo.
Então, imagina que uma pilha, exatamente como se fosse, por exemplo, uma pilha de pratos ou uma pilha de livros.
Então, você tem essa pilha, você começa a inserir esses elementos sempre no topo da pilha, e para você remover um elemento, você só pode remover o elemento que está lá no topo, porque se você remover algum elemento que está abaixo e tenha elementos acima dele, a pilha pode cair, pode desmoronar.
Então, é sempre a remoção desses elementos, é sempre do topo.
O último elemento que entrou nesta pilha vai ser o primeiro elemento a ser removido.
Principalizuz, modelar a gente de situações, onde é preciso guardar para mais tarde, vários elementos, e lembrar sempre do último elemento que foi armazenado.
Então, no caso daquele problema que a gente tinha no início, que é chamada de funções, a gente pode empilhar, e para empilhar a gente tem um nome específico para isso, que é o PUSH.
Então, a gente empilha o endereço para retornar depois e passa a execução para aquela nova função que foi chamada.
E acaba com o mano de retâneo daquela função que finalizou, a gente desempilha, e para isso a gente tinha um nome específico, que é o POP, então a gente desempilha o último endereço que foi armazenado, e passa a executar a partir daquele endereço desempilhado.
Então, olha só aqui como que funcionaria a nossa pilha para este exemplo de chamada de funções.
Então, aqui a nossa pilha está vazia.
A gente começa chamando a função A.
Nesta chamada, ele impreme o carácter A.
Aí, depois, ele tem uma chamada para a função C.
Nesta chamada para função C, a gente armazena na pilha a função que ele estava antes, que é A, e a próxima linha que deve ser executada quando retornar esta função C, que, no caso, está aqui, então, a função A e a linha 3, que é a próxima linha C executada.
E aí, a gente passa a execução para a função C.
A função C vai entre-me o carácter C na tela e vai fazer uma chamada a função D.
Antes de chamar de executar a função D, a gente deve empilhar a função que a gente está atualmente, que é C, e a próxima linha após esta chamada, que é a linha 3 da função C.
Então, aqui é onde a gente está empilhando a função C e a linha 3 lá na pilha.
Passamos a execução para a função D.
A função D vai entre-me D.
E aí, a gente tem aqui o nosso primeiro return.
Então, nesse return, o que acontece? A gente vai desempilhar um elemento da pilha.
Desempilhar um elemento da pilha envolve o pegar o elemento que está lá no topo e retornar ele, remover da pilha.
Aqui, no caso, é o C3.
Então, no C3, a gente sabe qual que é a próxima instrução esta executada, que seria da função C, linha 3.
Que é exatamente esta daqui.
Na função C, linha 3, a gente tem mais um return.
Nesse return, o que vai acontecer? A gente vai desempilhar mais uma vez da pilha.
Então, a gente vai desempilhar o elemento que está no topo da pilha, que é o A3.
Então, esse A3 indica para a gente qual que é a posição que deve ser executada, que é na função A, linha 3.
Exatamente, esta linha que está aqui, essa linha é a função B, e aí, onde vai seguir adiante? Nesse processo.
Então, ele vai começar a executar todas esses passos aqui, até o final da execução de todo o programa.
Tá bom? Então, operações usuais de pilha.
A gente tem lá o push, que seria um elemento na pilha, a função pop, que é desempilhar o elemento que está no topo, a função top, que é acessar um elemento do topo, mais sem desempilhar ele, e a função impite que é verificar se a pilha está vazia ou não.
Bom, a gente vai fazer um exemplo aqui, que seria esse, mais antes de a gente executar este exemplo, a gente vai implementar o nosso uma classe para a pilha.
Então, vamos lá.
Então, pessoal, eu já estou aqui no meu na main dpitchar, eu vou criar, inicialmente, uma classe chamada de pilha.
Nessa classe, a gente vai definir a nossa função init, que, como a gente viu na nossa vídeo aula sobre programação oriental do objeto, a função init é chamada automaticamente, quando a gente cria um objeto desta classe pilha.
O que a gente vai fazer dentro desta função init? A gente vai inicializar uma lista que vai ser a lista, onde a gente vai armazenar os elementos desta pilha.
Depois disso, eu vou implementar a função push, que é para inserir um elemento x dentro da pilha.
O que que eu vou fazer dentro? Eu vou usar a nossa lista interna e vou chamar a função atende para inserir no final, no final do direito da nossa lista, esse elemento x.
Vou ter também a função pop, que é para remover um elemento da pilha.
O que que eu vou fazer? Eu vou verificar inicialmente se o comprimento, se o tamanho da lista, ela é maior do que zero, porque para eu remover um elemento da pilha, ela tem que ter pelo menos um elemento ali dentro.
E aí, se essa condição for verdadeira, eu retorno o self.
data.
pop.
d-1.
Esse menu 1 indica que eu vou pegar o elemento último, o elemento que eu tinha na minha lista, isso é que é o elemento mais à direita.
Também posso implementar a função top, a função top ela vai fazer também o mesmo processo da função pop, que é verificar se a lista tem pelo menos um elemento inserido.
Se ela tiver a gente retorna o self.
data, da posição menos 1.
Repare aqui, pessoal, eu estou simplesmente consultando o último elemento lá da lista.
Na função pop, realmente, eu removo, por meio da função pop implementada na própria estrutura lista do Python, a gente remove, de fato, o elemento da lista.
Aqui não, a gente simplesmente consulta aquele elemento.
E aí, por fim, a gente tem a função empate que vai verificar se a pilha está vazia ou não.
Com isso, a gente vai implementar, por meio do meu retor, notch, len, tamanho da lista.
Se isso daqui é maior, o que é zero.
Ele vai retornar verde adeiro caso a pilha esteja vazia e falso caso ela não esteja vazia.
Bom, então, essa foi a implementação da nossa classe pilha.
Agora, a gente vai instanciar uma pilha.
A gente pode fazer algumas inserções nesta pilha para a gente verificar o funcionamento.
Eu vou colocar isso aqui no meu interpretador.
Então, eu vou colocar na memória esprimeira.
Agora, eu vou criar uma pilha.
Eu vou inserir, por exemplo, o elemento 4, o elemento 5, e o elemento 6.
E aí, eu vou mandar desempilar o elemento desta pilha.
Reparem que, quando a gente chama a função pop, ele remove o último elemento que foi inserido, que, no caso, é o 6.
Se eu remover mais um elemento, ele vai remover o elemento 5.
E se eu remover mais um elemento, ele vai remover o elemento 4.
Está sempre em hora inversa de inserção.
E aí, a gente pode, agora, fazer este exercício, que é implementar um programa em partom, que realiza a conversão desse mal para binário usando pilha.
Como a gente faz a conversão de um número que está em decimal, na base 10, para um número binário, base 2? Então, suponio que eu tenho um número 13.
Eu quero converter isso para um número binário.
Então, eu vou fazendo divisões até que o meu cosinte seja igual a 0.
Então, eu faço 13 dividido por 2.
Tive um resultado com o 6, com o resto 1.
Depois, eu faço a divisão novamente do cosinte por 2.
Vai te dar um valor 3 com o resto 1.
Faça a divisão novamente por 2.
Vai te dar valor 1 com o resto 1.
Depois, eu faço a divisão novamente, que vai te dar o valor 0 com o resto 1.
Quando esse cosinte aqui for 0, a gente para.
Quando para, a gente consegue analisando os restos dessas divisões sucessivas, esse valor vai ser o número binário do número que a gente estava número 13.
A gente tinha aqui, só que isso de ordem inversa.
Então, pegando o 1 daqui e voltando, a gente tem os bits 1, 1, 0 e 1.
Então, esse número aqui é o número binário do número 13.
Então, 13 em decimal equivale a 1, 1, 1, 1 em binário.
Então, a ideia, a gente implementar este programa usando a nossa classe pilha que foi criada.
Então, vamos voltar para o nosso atelo.
Então, o que eu vou fazer aqui? Eu vou criar um objeto da classe pilha.
Vou ter o número que a gente vai converter, no caso vai ser o número 13.
Aí, eu vou colocar isso dentro de um loop, enquanto esse número for maior do que 0.
A gente vai armazenar o resto da divisão desse número por 2.
A divisão do número por 2, a gente obtém o resto.
Isso é feito por meio desse operador aqui.
Resta a divisão da linguagem Python.
A gente vai pegar o novo, consciente da divisão sem considerar números em ponto futuante, a somente ao aparte inteiro.
Então, isso faz o número dividido por 2.
Divisão inteira sem considerar o resto dessa divisão.
E aí, a gente vai empilhar o resto na nossa pilha.
E vai fazendo esse processo enquanto este número, o consciente, for maior do que 0.
Quando esse consciente chegar no valor 0, a gente para este loop.
E agora, começamos a desempilhar a nossa pilha.
Então, a gente coloca isso dentro de um loop.
Então, enquanto a nossa pilha não for vazia, não estiver vazia, a gente vai imprimir o pop, que é os valores que a gente inseriu no loop anterior.
Então, vamos rodar isto aqui para ver.
Então, está aqui os números.
O número binário do 13 seria 1, 1, 0, 1.
Se a gente quiser, por exemplo, colocar um outro número 14, a gente vai ter o número binário 1, 1, 1, 0.
100 e 40, por exemplo.
Você já vai ter um número maior aqui.
Então, pessoal, esta aqui foi a nossa videoaula sobre pilhas.
Espero que vocês possam ter entendido a ideia fundamental de pilhas.
Aí, a gente vai dar continuidade a estas videoaulas desta semana.
Então, na próxima videoaula, a gente vai entender, vai aprender sobre uma outra estrutura de dados.
Então, agradeço pela atenção de vocês e a gente se vê numa próxima.