Estrutura de dados: Stack
Parte 1
Stack (pilha, em português) é uma coleção de itens ou estrutura de dados, onde a adição e a remoção de um item é feita pela mesma saída. Essa saída é comumente chamada de “top” e o extremo oposto é chamado de “base”.
O item mais recentemente adicionado será o primeiro removido em caso de remoção, já que estará no topo (ou “top”).
Há muitos casos de stack no cotidiano. Exemplo: Quando empilhamos livros em uma estante. O primeiro da pilha fica embaixo de todos os outros livros. E o último, colocado na pilha de livros, estará no topo (top). Caso quisermos retirar esse livro, precisaríamos retirar o do topo (top) primeiramente, antes de retirar qualquer outro.
Em Python, uma representação de um stack de objetos Python, seria a seguinte imagem, onde o valor 8.4 é o top e o inteiro 4 é o valor mais próximo da base:
Vamos definir a estrutura e operações (métodos) que podemos fazer com um Stack (uma pilha).
Stack() → cria um stack vazio
push(item) → método que adiciona um novo item no stack
pop() → método que remove e retorna o item do top do stack
peek() → método que retorna o último item adicionado (top)
isEmpty() → método que retorna um bool (true ou false), se o stack está vazio
size() → método que retorna a quantidade de itens no stack
Então agora que entendemos um pouco sobre alguns métodos de um stack, vamos utilizá-los:
Podemos adicionar (push), remover (pop), saber se o stack está vazio ou não (isEmpty) e saber a quantidade de itens no stack (size).
Com esse melhor entendimento dos métodos de um stack, podemos fazer uma implementação de um empilhamento de objetos livro:
Então começamos criando uma classe livro, na qual podemos instanciar vários objetos livro, inicializando o objeto com seu nome. Criamos os objetos livros (livro1, livro2, livro3, livro4 e livro5) e podemos implementar o empilhamento dessas objetos.
Quando queremos colocar um livro na pilha, usamos o método push(), e caso quisermos retirar, usamos pop().
Resultado..
——————————————— // ———————————————
Uma outra implementação interessante que podemos fazer usando um stack é reverter a ordem de seus itens. A imagem seguinte mostra como isso acontece:
O primeiro item, o inteiro 4, será o último item a ser retirado. O que de fato reverterá o stack. Vamos ver como isso funciona com código:
Usamos o método revstring() para reverter uma string. Nele, iteramos para adicionar cada unidade/letra da string em um stack. E iteramos novamente (enquanto o stack não estiver vazio — not stack.isEmpty) para retirar do stack e colocar na variável “reverse”. Por fim, comparamos se o método realmente reverte a string.
Bom, é isso gente. Espero que tenham gostado do post! Achei bem interessante essa estrutura de dados. Escreverei sobre mais estruturas de dados em breve..
See ya..