Pilhas
Pilhas são estruturas de dados em que só é possível inserir um novo elemento no final da pilha e só é possível remover um elemento do final da pilha. Dizemos que pilhas seguem um protocolo em que o último a entrar é o primeiro a sair. Pilhas são geralmente implementadas com arranjos.
Em uma pilha, para que o último elemento a entrar (ser inserido) seja o primeiro a sair (ser removido), precisamos ser capazes de:
-
Inserir um novo elemento no final da pilha.
-
Remover um elemento do final da pilha.
Existe uma forma de usarmos listas como se fossem pilhas em Python. Assim como fizemos na seção anterior, usaremos listas em nossos exemplos, mas lembrando que pilhas são implementadas com arranjos. Podemos inclusive dizer que pilhas são arranjos em que as operações de inserção e remoção de elementos seguem um protocolo específico: o último elemento a ser inserido é sempre o primeiro elemento a ser removido.
Vejamos um exemplo simples do uso de pilhas em Python.
pilha = [1, 1, 2, 3, 5]
print("Pilha: ", pilha)
pilha.append(8)
print("Inserindo um elemento: ", pilha)
pilha.append(13)
print("Inserindo outro elemento: ", pilha)
pilha.pop()
print("Removendo um elemento: ", pilha)
pilha.pop()
print("Removendo outro elemento: ", pilha)Pilha: [1, 1, 2, 3, 5] Inserindo um elemento: [1, 1, 2, 3, 5, 8] Inserindo outro elemento: [1, 1, 2, 3, 5, 8, 13] Removendo um elemento: [1, 1, 2, 3, 5, 8] Removendo outro elemento: [1, 1, 2, 3, 5]
O exemplo acima ilustra o funcionamento das operações de inserção e remoção de elementos em uma pilha. Tanto inserções (append) quando remoções (pop) acontecem à direita (no final) da pilha. Se implementadas cuidadosamente, essas operações possuem complexidade constante, ou seja, $O(1)$.
Pilhas com Estruturas Encadeadas
Na seção anterior, ilustramos o uso de arranjos como pilhas. A ideia básica é que precisamos inserir e remover elementos de um arranjo de um modo específico: elementos são sempre inseridos no final do arranjo, e elementos são sempre removidos do final do arranjo.
Nesta seção mostraremos como implementar uma pilha usando uma estrutura encadeada. Sempre que inserirmos um elemento, o colocaremos no final da pilha, ou seja, no topo da pilha. E sempre que removermos um elemento, removeremos o elemento que está no topo da pilha.
Na seção anterior, a lista encadeada possuia uma cabeça, e cada nodo da lista encadeada fazia referência ao próximo nodo. Nossa pilha funcionará de modo parecido: ela possui um topo, e cada elemento faz referência ao elemento anterior. Essencialmente, as duas implementações são muito parecidas, as únicas mudanças são conceituais (cabeca versus topo, e próximo versus anterior), conforme ilustrado na figura abaixo e mostrado na implementação seguinte.
O código abaixo tenta deixar os conceitos acima mais claros.
class Nodo:
"""Esta classe representa um nodo de uma estrutura encadeada."""
def __init__(self, dado=0, nodo_anterior=None):
self.dado = dado
self.anterior = nodo_anterior
def __repr__(self):
return '%s -> %s' % (self.dado, self.anterior)
class Pilha:
"""Esta classe representa uma pilha usando uma estrutura encadeada."""
def __init__(self):
self.topo = None
def __repr__(self):
return "[" + str(self.topo) + "]"A figura acima mostra a implementação de uma pilha com uma estrutura encadeada, semelhante à que usamos no caso das listas. Tomando como base essa implementação, podemos desenvolver funções para inserir e remover elementos da pilha. Como dissemos acima, tanto inserções quanto remoções em uma pilha ocorrem ao final da estrutura, como ilustrado nas figuras abaixo.
A figura abaixo a inserção de um novo elemento em uma pilha.
O código a seguir implementa uma função que insere um novo elemento em uma pilha.
def insere(self, novo_dado):
"""Insere um elemento no final da pilha."""
# Cria um novo nodo com o dado a ser armazenado.
novo_nodo = Nodo(novo_dado)
# Faz com que o novo nodo seja o topo da pilha.
novo_nodo.anterior = self.topo
# Faz com que a cabeça da lista referencie o novo nodo.
self.topo = novo_nodoNa figura abaixo mostramos a remoção de um elemento de uma pilha. Remoções também ocorrem no final (topo) da pilha.
Apesar de a figura acima mostrar o nodo sendo apagado da pilha, na prática, só precisamos alterar o apontador do topo da pilha. Com isso, o nodo que desejamos remover não será mais referenciado, e eventualmente o interpretador Python o removerá da memória.
O código a seguir implementa uma função que remove o elemento no topo da pilha.
def remove(self):
"""Remove o elemento que está no topo da pilha."""
assert self.topo, "Impossível remover valor de pilha vazia."
self.topo = self.topo.anteriorNovamente, é importante ressaltar que tanto inserções quanto remoções ocorrem em somente um extremo da pilha, no topo.
Vejamos agora como usar nossa implementação de pilha.
# Cria uma pilha vazia.
pilha = Pilha()
print("Pilha vazia: ", pilha)
# Insere elementos na pilha.
for i in range(5):
pilha.insere(i)
print("Insere o valor {0} no topo da pilha: {1}".format(i, pilha))
# Remove elementos na pilha.
while pilha.topo != None:
pilha.remove()
print("Removendo elemento que está no topo da pilha: ", pilha)Pilha vazia: [None] Insere o valor 0 no topo da pilha: [0 -> None] Insere o valor 1 no topo da pilha: [1 -> 0 -> None] Insere o valor 2 no topo da pilha: [2 -> 1 -> 0 -> None] Insere o valor 3 no topo da pilha: [3 -> 2 -> 1 -> 0 -> None] Insere o valor 4 no topo da pilha: [4 -> 3 -> 2 -> 1 -> 0 -> None] Removendo elemento que está no topo da pilha: [3 -> 2 -> 1 -> 0 -> None] Removendo elemento que está no topo da pilha: [2 -> 1 -> 0 -> None] Removendo elemento que está no topo da pilha: [1 -> 0 -> None] Removendo elemento que está no topo da pilha: [0 -> None] Removendo elemento que está no topo da pilha: [None]
Playground
# Use este espaço para praticar o que você aprendeu nesta seção.
# Basta digitar o código no espaço abaixo e clicar 'run'.