Pilhas em Python com listas (stack)

Pilhas em Python com listas (stack)

Pilhas em Python são comumente criadas usando listas, porque estamos interessados em manipular apenas a extremidade do topo da estrutura (o final da lista). Isso nos garante complexidade de tempo O(1) (tempo constante) com métodos append e pop.

Uma pilha é uma coleção de itens que segue o princípio LIFO (Last In First Out) , ou seja, o último item a entrar, será o primeiro a sair. A adição e remoção de novos itens ocorre sempre na mesma ponta da pilha, o final da lista. O final da lista (último índice), representa o topo da pilha, o começo da lista (índice 0) representa a base da pilha.

Itens mais novos são sempre adicionados no topo da pilha e se tornam mais antigos a medida que adicionamos outros itens. Quanto maior o índice na lista, mais novo é o item e mais cedo ele será removido da pilha.

Pilhas são estruturas de dados muito simples, mas podem ser usadas para representar várias coisas no mundo real, por exemplo: uma pilha de pratos, uma pilha de livros ou qualquer coisa que você coloque uma sobre a outra formando uma pilha. Além disso, programas também usam pilhas, como a pilha de chamadas para funções que já vimos anteriormente nesse blog.

Uma pilha de livros

Vamos ver como representar uma pilha em Python.

Listas são pilhas muito genéricas em Python

Como pilhas só precisam de métodos para adicionar e remover itens do seu topo, as listas do Python já fazem esse trabalho com excelência e complexidade de tempo O(1), ou tempo constante. Então, é super rápido.

Porém, ou você só usa esses dois métodos (append e pop), ou você cria sua própria estrutura de dados chamada de Stack (uma classe que você verá ao final desse post) para outros desenvolvedores não usarem sua pilha de maneira genérica (como filas, por exemplo).

Se você quiser trabalhar diretamente com as listas, pode fazer o seguinte:

Perceba que no código acima, criei uma pilha de livros (stack_of_books) como uma lista vazia {1}. Quando precisei adicionar livros na pilha, usei o método append, que é padrão de listas em Python para adicionar itens ao final da lista {2}. Além disso, quando precisei obter o livro mais novo (do topo da pilha), usei o método pop, que também é padrão de listas em Python para obter o último item da lista (ou o elemento do topo da pilha) {3}.

Na verdade, o método pop faz duas coisas. Além de remover o item do topo da pilha, ele também retorna este valor. Então, Isso me permitiu fazer duas coisas em {3}: remover o item do topo da pilha e coletar seu valor em uma variável.

Por fim {4}, imprimimos o valor de book, que foi o “Livro 3”.

Cuidados com pop

Note que, a cada execução do método pop, o item mais novo será removido da pilha. Em algum momento, sua pilha poderá estar vazia e esse método levantará a exceção “IndexError: pop from empty list“, ou “Erro de índice: pop de uma lista vazia” (em tradução livre).

Isso ocorre porque não há mais valores para serem removidos e recuperados da sua pilha {4}.

Para prevenir esse tipo de situação, podemos envolver nosso código em um bloco try e except, tratando a exceção “IndexError“. Veja:

Assim, a partir do momento que a exceção ocorrer {4}, seu código pulará imediatamente para o bloco except. Se não houver exceções, seu código não executará o bloco except.

Não use listas como filas

Além das pilhas, outra estrutura de dados muito usada em programação são as filas (falamos sobre elas em outro artigo). Basicamente, filas trabalham no lado oposto das pilhas. Então, se nas pilhas você trabalha na extremidade final (adicionando e removendo itens do topo), nas filas você trabalha nas duas extremidades, enfileirando itens no final (topo) e desenfileirando itens do início (base).

As listas podem ser usadas para filas também, porém, não é recomendável. Isso torna sua complexidade de tempo O(n), ou tempo linear, o que torna as listas mais lentas para isso.

O método pop, pode receber o índice que você pretende remover da pilha, por exemplo (mas não faça isso):

Perceba que, no código acima, eu consigo passar um índice para pop descrevendo qual livro quero remover da pilha {3}. Assim, isso me permite remover o item da base da minha pilha (índice 0). Mas, o problema ao fazer algo assim, é que como as listas não foram otimizadas para tal, todos os outros itens da lista agora precisam ter seus índices alterados. O que tinha índice 1, passa a ter índice 0, o que tinha índice 2, passa a ter índice 1 e assim por diante.

A complexidade de tempo O(n) significa que, na pior das hipóteses, quando eu removo um item da base da minha pilha (como nas filas), todos os outros items agora precisam ser modificados, e eu assumo que não era essa a sua intenção.

Nós já falamos sobre filas aqui, mas para resumir, use collections.deque para filas e listas para pilhas.

Iterando pilhas

Em Python a iteração dos iteráveis é feita com for. Se você não quer remover nenhum elemento, mas apenas iterar sobre toda a pilha, faça o seguinte:

Perceba que no código acima, na linha 13, temos um laço for que vai iterar em todos os elementos da lista. Então eu posso fazer o que preferir com a variável book.

Detalhe importante: para manter a ordem da pilha (do topo para a base), eu preciso fazer uma iteração em ordem reversa na pilha quando uso for. Por isso adicionei [::-1] em stack_of_books. Isso inverte a ordem de listas em Python.

Um outro tipo de iteração sobre pilha, seria removendo os elementos da pilha ao mesmo tempo que itero sobre eles. Podemos fazer isso com o laço while:

Perceba que usando o laço while com o método pop, a ordem é mantida. Porém, é importante saber que estou removendo cada um dos elementos da minha pilha.

Copiando pilhas

Trabalhar com dados mutáveis, como as listas, pode ser perigoso em qualquer linguagem de programação porque manipulamos o dado diretamente. Então, é uma boa ideia manter uma cópia do dado original sempre que o manipulamos (se for possível, é claro). Por outro lado, pode ser caro manter cópia de dados que são muito grandes, então você precisa ponderar as duas coisas: segurança e peso.

Manter a cópia de uma lista, pode ter uma complexidade de tempo linear O(n) se você fizer uma cópia rasa (shallow copy) ou mais do que isso se você mantiver uma cópia profunda (deep copy).

Shallow copy:

Esse tipo de cópia é um clone superficial dos itens da pilha. Ela tem complexidade de tempo linear – O(n) – o que significa que é necessário passar por todos os itens para realizar a cópia destes. A parte interessante desse tipo de cópia é que dados imutáveis (como str, int, float e bool) serão realmente copiados para uma nova pilha. Porém, dados mutáveis (como outras listas, dicionários e sets) não serão copiados, a nova pilha terá apenas uma referência para os dados mutáveis da pilha original.

Para realizar uma cópia do tipo shallow copy da sua pilha, faça o seguinte:

Deep copy

Quando falamos em pilhas que contém dados mutáveis, como por exemplo, outras listas dentro da nossa pilha. É preciso tomar cuidado com a shallow copy, porque ela não vai copiar esses elementos, vai fazer apenas uma referência apontando para os dados da lista original. Isso significa que meus dados ainda continuarão mutáveis internamente, mesmo na cópia.

A complexidade de tempo de uma deep copy vai depender da profundidade dos itens mutáveis da sua pilha, quanto maior a profundidade, maior a complexidade (mais tempo leva).

Imagine essa estrutura de dados:

Esse é um tipo de estrutura que devo tomar cuidado, porque existem listas dentro da minha pilha.

Veja o problema:

Os comentários do código acima, explicam o que ocorre em cada trecho. Mas, aqui vai uma breve explicação:

  • Linha 13 – Faço uma shallow copy da minha pilha. Como te descrevi anteriormente, dados mutáveis NÃO são copiados de dentro da pilha original, eles passados apenas como referência. Isso significa que a lista cópia terá uma referência desses dados (você consegue acessá-los por ela) mas eles ainda são os dados da lista original e não uma cópia real;
  • Linha 17 – Obtém o item do topo da lista (esse ainda é o dado da lista original);
  • Linha 20 – Altero o item. Porém, como esse item é uma referência ao item da lista original, quem será alterado efetivamente será o item da lista original;
  • Linha 23 – Percebo a besteira que fiz.

Para solucionar esse tipo de coisa, usamos a deep copy, que é um tipo de cópia recursiva. Com isso, todos os dados, mutáveis e imutáveis serão copiados para a lista cópia.

Veja:

Veja que as únicas coisas alteradas foram na linha 5, porque eu preciso importar “deepcopy” do módulo “copy”. E a linha 16, porque ao invés de “shallow copy”, agora estou fazendo uma “deep copy”.

Classe Stack

A maneira mais segura e correta de se trabalhar com listas como pilhas em Python, é proteger o código para que os métodos genéricos das listas não possam ser chamados diretamente. Assim protegeremos o nosso código para que outros desenvolvedores não possam chamar um pop(0) na nossa pilha, dentre vários outros.

Criando uma classe, podemos adicionar exclusivamente os métodos que queremos. Como append, pop e alguns métodos mágicos para iteração e visualização de dados.

Em vídeo

Também fiz um vídeo sobre esse exato conteúdo no meu canal, segue abaixo:

Resumo

Em Python, usamos as listas como pilhas (nunca como filas). Elas são estruturas de dados bem simples que precisam de apenas dois métodos para funcionarem corretamente. Um método de inserção e outro de remoção de valores (append e pop). Geralmente, o método de remoção (pop) também retorna o valor removido e você pode usá-lo com o que preferir.

As pilhas trabalham apenas na extremidade final da lista, por isso têm comportamento LIFO (Last In First Out), ou, o último a entrar é o primeiro a sair. O último elemento adicionado é considerado o elemento do topo da pilha; o primeiro elemento adicionado é o elemento da base da pilha.

Podemos iterar sobre pilhas usando laços for (invertendo seus valores) ou laço while combinado com pop.

É possível copiar listas utilizando shallow copy ou deep copy.

É só isso… Te vejo no próximo artigo.

0 respostas

Deixe uma resposta

Quer participar da conversa?
Sinta-se livre para contribuir!

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *