9. Pilha¶
Uma pilha é um tipo de dado abstrato muito utilizado em computação. Seu nome é devido a analogia do comportamento dessa estrutura com pilhas de objetos no mundo real como, por exemplo, uma pilha de livros. O comportamento dessa estrutura sugere que um novo livro seja colocado no topo, assim como o primeiro livro a ser retirado deve sair do topo também.
9.1. Objetivos de aprendizagem¶
Ao final dessa aula você será capaz de:
- Descrever o comportamento da estrutra de dados Pilha;
- Criar uma classe Pilha usando listas em Python;
- Utilizar objetos do tipo Pilha para resolver problemas computacionais.
9.2. Introdução¶
Uma pilha (= stack) é uma estrutura linear dinâmica em que todas as operações (inserções, remoções e consultas) são feitas em uma mesma extremidade chamada de topo da pilha.
Portanto, em uma estrutura do tipo pilha, o último elemento inserido é o primeiro a ser removido ou consultado. Essa estrutura também é conhecida como como LIFO (= last-in first-out), como ilustrado abaixo.
empilha --->---+ +-->----> desempilha
(=push) | | (=pop)
V |
+-----------+
| vvvvvvvvv |
+-----------+
| wwwwwwwww |
+-----------+
| zzzzzzzzz |
+-----------+
| yyyyyyyyy |
+-----------+
| xxxxxxxxx |
+-----------+
Apenas para fins de comparação, uma fila (= queue) é outra estrutura linear dinâmica bastante utilizada em computação e que é conhecida como FIFO (= first-in first-out). Novos elementos entram no final da fila, e são removidos do começo da fila.
9.3. Uma classe Pilha em Python¶
Vamos continuar a exercitar a programa orientada a objetos criando uma classe Pilha em Python. Essa classe tem comportamento muito parecido com a classe Stack do livro https://panda.ime.usp.br/panda/static/pythonds_pt/index.html, mas “fala” português.
Nossa classe Pilha deve possuir um atributo de nome dados.
Esse atributo dados deve ser uma lista que armazena os itens da pilha. Esse requisito implica no seguinte construtor da classe Pilha:
class Pilha:
def __init__(self):
self.dados = []
9.3.1. Comportamentos de um objeto do tipo Pilha¶
Os comportamentos esperados de um objeto do tipo Pilha são ilustrados pela seguinte função testes():
def testes():
pil = Pilha() ## cria uma Pilha vazia
print(f"pil.dados = {pil.dados} --> deve ser a lista vazia []")
print(f"pil.vazia() = {pil.vazia()} --> deve ser True")
pil.empilhe('todos')
pil.empilhe(4)
pil.empilhe('paz')
# Pilha.topo() apenas pega o valor no topo mas sem desempilher
print(f"pil.topo() = {pil.topo()} --> deve ser 'paz'")
pil.empilhe(True)
print(f"len(pil) = {len(pil)} --> deve ser 4") ## implemente o método __len__
print(f"pil.vazia() = {pil.vazia()} --> deve ser False")
print(f"pil.dados = {pil.dados} --> deve ser ['todos', 4, 'paz', True]")
pil.empilhe(2.7)
print(f"pil.desempilhe() = {pil.desempilhe()} --> deve ser 2.7")
print(f"pil.desempilhe() = {pil.desempilhe()} --> deve ser True")
print(f"len(pil) = {len(pil)} --> deve ser 3")
print(f"pil.dados = {pil.dados} --> deve ser ['todos', 4, 'paz']")
Estudando os comportamentos esperados pela função testes() podemos inferir que a classe deve possuir os seguintes métodos:
vazia(): retorna True quando a pilha estiver vazia e False caso contrário.empilhe(): empilha um objeto na pilha.desempilhe(): retorna o valor do topo da pilha e o remove da pilha.topo(): retorna o valor no topo da pilha, mas sem desempilhar.
Além disso, a função len() retorna o tamanho da pilha (seu número de elementos).
Lembre-se que a função len() também é usada para listas e strings.
Embora possamos definir uma função def len() fora da classe Pilha, essa redefinição de len() não é recomendada pois, dentro do nosso programa, essa função deixaria de funcionar para objetos do tipo list e str. Para estender o comportamento de len() para o tipo Pilha sem perder os demais casos nativos da função nativa len(), devemos implementar o método especial __len__(self) dentro da classe Pilha. A seguinte implementação da classe Pilha inclui esse e os demais métodos.
class Pilha:
def __init__(self):
'''(Pilha) -> None
Monta um objeto da classe Pilha.
'''
self.dados = []
def __len__(self):
'''(Pilha) -> int
Recebe uma Pilha referenciada por self e retorna
o número de itens na pilha.
Usado pelo Python quando escrevemos len(Pilha).
'''
return len(self.dados)
def vazia(self):
'''(Pilha) -> bool
Recebe uma Pilha referenciada por self e retorna
True se ela está vazia e False em caso contrário.
'''
return self.dados == []
def empilhe(self, item):
'''(Pilha, objeto) -> None
Recebe uma Pilha referenciada por self e um objeto
item e coloca item no topo da pilha.
'''
self.dados.append(item)
def desempilhe(self):
'''(Pilha) -> objeto
Recebe uma Pilha referenciada por self e desempilha
e retorna o objeto no topo da pilha.
'''
return self.dados.pop()
def topo(self):
'''(Pilha) -> objeto
Recebe uma Pilha referenciada por self e retorna
o objeto no topo da pilha. O objeto não é removido
da pilha.
'''
return self.dados[-1]
Simule o comportamento dessa classe executando passo-a-passo os testes definidos pela função testes(), clicando no botão Forward >.
9.4. Exercícios¶
função palindromo()
Palíndromo é uma palavra, frase ou número que permanece igual quando lida de trás para diante. Por extensão, palíndromo é qualquer série de elementos com simetria linear, ou seja, que apresenta a mesma sequência de unidades nos dois sentidos [veja mais a respeito na Wikipedia ].
Na janela do Trinket abaixo, escreva a função palindromo() que recebe uma string e retorna True caso a string seja um palíndromo, e retorna False caso contrário. Sua solução para a função palindromo() deve utilizar a sua classe Pilha.
Observe que uma sequência de empilhamentos seguido por uma sequência de desempilhamentos é uma forma de inverter uma sequência. Por exemplo a sequência de caracteres “pilha” pode ser empilhada, caractere a caractere e, ao ser desempilhada, forma a sequência “ahlip”.
função bem_formada()
Uma pilha pode ser utilizada para verificar se uma expressão aritmética contendo uma sequência de parênteses e colchetes está bem formada, ou seja, se todo parênteses e colchetes que abre é fechado na sequência correta. Por exemplo, a sequência “()[] ([])” é bem formada, enquanto as sequências “([)]”, “()(” e “]()[” não são bem formadas.
Observe que, em Python, ao invés de criarmos a classe
Pilha, podemos usar uma lista diretamente, mas tratando a lista como pilha, ou seja, sempre tratando o final da lista como o topo da pilha.Assim, usando os métodos append() e pop() de listas mas tratando a lista como pilha, escreva uma função
bem_formada()que recebe uma string s contendo apenas os caracteres ‘(’, ‘)’ e devolve True` caso a expressão estiver bem formada e False caso contrário.Dica: a idéia é empilhar todo caractere ‘(’ ou ‘[’ (abre parênteses e abre colchetes) e, ao encontrar um fecha parênteses ou colchetes, verificar se o caractere no topo da pilha “casa” com esse caractere que fecha. Se houver casamento o processo continua, caso contrário o processo pode ser interrompido. Ao final, a pilha precisa estar vazia. Simule esse processo desenhando o que acontece com a pilha usando apenas papel e lápis com algumas sequências bem e mal formadas antes de tentar escrever seu código em Python.
9.5. Onde estamos e para onde vamos?¶
O tipo Pilha (= stack) é uma estrutura utilizada na solução de vários problemas computacionais. Vimos que criar uma classe Pilha é muito simples usando uma lista (tipo list do Python) para representar os dados da pilha. Na verdade, essa implementação é tão simples que podemos usar uma lista diretamente, apenas impondo a inserção e remoção de elementos sempre do “topo”, como se a lista fosse uma pilha.
Na próxima aula vamos ilustrar o uso de pilhas no cálculo de expressões em notação reversa (= posfixa).
9.6. Para saber mais¶
- Pilhas da página do Prof. Paulo Feofilloff, em C.
- O que é uma Pilha?.
- O tipo abstrato de dados Pilha.
- Implementando uma Pilha em Python.