Deseja aprimorar suas habilidades de programação com estruturas de dados? Comece hoje mesmo explorando as estruturas de dados em Python.
Ao iniciar em uma nova linguagem de programação, é crucial entender os tipos de dados fundamentais e as estruturas de dados internas que ela oferece. Neste guia sobre estruturas de dados em Python, abordaremos:
- Os benefícios de utilizar estruturas de dados.
- Estruturas de dados nativas do Python, como listas, tuplas, dicionários e conjuntos.
- Implementações de tipos de dados abstratos, como pilhas e filas.
Vamos começar!
Por que Estruturas de Dados são Importantes?
Antes de detalharmos as diversas estruturas de dados, vamos entender a utilidade dessas estruturas:
- Processamento de Dados Eficiente: A escolha correta da estrutura de dados otimiza o processamento de dados. Por exemplo, para armazenar uma coleção de itens do mesmo tipo com tempos de busca rápidos e acoplamento rígido, um array é uma boa opção.
- Gerenciamento de Memória Otimizado: Em projetos extensos, para armazenar os mesmos dados, algumas estruturas de dados podem ser mais eficientes em termos de uso de memória do que outras. Em Python, por exemplo, listas e tuplas podem armazenar coleções de dados do mesmo tipo ou de diferentes tipos. No entanto, se a coleção não necessitar de modificação, uma tupla pode ser mais eficiente em termos de memória do que uma lista.
- Código Mais Organizado: A utilização da estrutura de dados adequada para cada funcionalidade torna seu código mais claro e organizado. Outros programadores, ao lerem seu código, esperam que você use estruturas de dados específicas, dependendo do comportamento desejado. Se você necessitar de um mapeamento chave-valor com tempos de busca e inserção constantes, por exemplo, um dicionário é a escolha ideal.
Listas
Quando precisamos criar arrays dinâmicos em Python, seja em entrevistas de programação ou em situações comuns, as listas são a estrutura de dados mais utilizada.
As listas em Python são tipos de dados de contêiner que são mutáveis e dinâmicos, permitindo adicionar e remover elementos diretamente na lista, sem a necessidade de criar uma cópia.
Ao usar listas em Python:
- A indexação e o acesso a um elemento específico da lista ocorrem em tempo constante.
- Adicionar um elemento ao final da lista é uma operação de tempo constante.
- Inserir um elemento em uma posição específica é uma operação de tempo linear.
Python oferece um conjunto de métodos de lista que facilitam a execução de tarefas comuns. O código abaixo demonstra algumas dessas operações em uma lista:
>>> nums = [5,4,3,2] >>> nums.append(7) >>> nums [5, 4, 3, 2, 7] >>> nums.pop() 7 >>> nums [5, 4, 3, 2] >>> nums.insert(0,9) >>> nums [9, 5, 4, 3, 2]
As listas em Python também suportam fatiamento e testes de associação utilizando o operador ‘in’:
>>> nums[1:4] [5, 4, 3] >>> 3 in nums True
A estrutura de dados da lista não só é flexível e simples, mas também permite armazenar elementos de diversos tipos. O Python também fornece uma estrutura de dados array dedicada para armazenar elementos do mesmo tipo de dados de forma eficiente. Exploraremos isso mais adiante.
Tuplas
Em Python, tuplas são outra estrutura de dados nativa muito utilizada. Elas são semelhantes às listas em termos de indexação em tempo constante e fatiamento. No entanto, as tuplas são imutáveis, não permitindo modificações diretas. O exemplo a seguir demonstra isso:
>>> nums = (5,4,3,2) >>> nums[0] 5 >>> nums[0:2] (5, 4) >>> 5 in nums True >>> nums[0] = 7 # not a valid operation! Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: 'tuple' object does not support item assignment
Portanto, se precisar de uma coleção imutável, mas ainda com processamento eficiente, tuplas são a escolha certa. Se, ao contrário, a coleção necessitar de modificação, prefira listas.
📋 Consulte mais informações sobre as semelhanças e diferenças entre listas e tuplas em Python.
Arrays
Arrays são estruturas de dados menos conhecidas em Python. São similares às listas em termos de operações suportadas, como indexação em tempo constante e inserção em tempo linear.
A principal diferença entre listas e arrays reside no fato de que arrays armazenam elementos de um único tipo de dados. Isso os torna fortemente acoplados e mais eficientes em termos de memória.
Para criar um array, utilizamos o construtor `array()` do módulo array nativo. O construtor `array()` recebe uma string especificando o tipo de dados dos elementos, bem como os próprios elementos. O exemplo abaixo cria `nums_f`, um array de números de ponto flutuante:
>>> from array import array
>>> nums_f = array('f',[1.5,4.5,7.5,2.5])
>>> nums_f
array('f', [1.5, 4.5, 7.5, 2.5])
É possível acessar elementos de um array por meio de indexação, de forma similar às listas:
>>> nums_f[0] 1.5
Arrays são mutáveis, permitindo modificações:
>>> nums_f[0]=3.5
>>> nums_f
array('f', [3.5, 4.5, 7.5, 2.5])
Contudo, não é possível modificar um elemento para um tipo de dado diferente:
>>> nums_f[0]='zero' Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: must be real number, not str
Strings
Em Python, strings são coleções imutáveis de caracteres Unicode. Ao contrário de linguagens como C, Python não tem um tipo de dados específico para caracteres. Logo, um caractere também é uma string de comprimento um.
Como já mencionado, strings são imutáveis:
>>> str_1 = 'python' >>> str_1[0] = 'c' Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: 'str' object does not support item assignment
Strings em Python suportam fatiamento e oferecem diversos métodos para formatação. Aqui estão alguns exemplos:
>>> str_1[1:4] 'yth' >>> str_1.title() 'Python' >>> str_1.upper() 'PYTHON' >>> str_1.swapcase() 'PYTHON'
⚠ Lembre-se de que todas as operações acima retornam uma cópia da string e não alteram a original. Consulte o guia sobre operações de strings em Python, se estiver interessado em saber mais.
Conjuntos
Em Python, conjuntos são coleções de itens únicos e hasheáveis. Você pode realizar operações comuns de conjuntos, como união, interseção e diferença:
>>> set_1 = {3,4,5,7}
>>> set_2 = {4,6,7}
>>> set_1.union(set_2)
{3, 4, 5, 6, 7}
>>> set_1.intersection(set_2)
{4, 7}
>>> set_1.difference(set_2)
{3, 5}
Conjuntos são mutáveis por padrão, permitindo adição e modificação de elementos:
>>> set_1.add(10)
>>> set_1
{3, 4, 5, 7, 10}
📚 Explore mais sobre conjuntos em Python: um guia completo com exemplos.
Frozensets
Para criar um conjunto imutável, utilize um frozenset. Um frozenset pode ser criado a partir de conjuntos existentes ou de outros iteráveis.
>>> frozenset_1 = frozenset(set_1)
>>> frozenset_1
frozenset({3, 4, 5, 7, 10, 11})
Como `frozenset_1` é um frozenset, qualquer tentativa de adicionar (ou modificar) elementos resultará em erro:
>>> frozenset_1.add(15) Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'frozenset' object has no attribute 'add'
Dicionários
Um dicionário em Python funciona como um mapa hash, armazenando pares chave-valor. As chaves do dicionário devem ser hasheáveis, o que significa que o valor de hash do objeto não se altera.
É possível acessar valores usando chaves, inserir novos itens e remover itens existentes em tempo constante. Métodos de dicionário oferecem suporte a essas operações.
>>> favorites = {'book':'Orlando'}
>>> favorites
{'book': 'Orlando'}
>>> favorites['author']='Virginia Woolf'
>>> favorites
{'book': 'Orlando', 'author': 'Virginia Woolf'}
>>> favorites.pop('author')
'Virginia Woolf'
>>> favorites
{'book': 'Orlando'}
OrderedDict
Apesar de um dicionário em Python oferecer um mapeamento chave-valor, é inerentemente uma estrutura de dados não ordenada. A partir do Python 3.7, a ordem de inserção dos elementos é preservada. Mas, para garantir a ordem, use um `OrderedDict` do módulo `collections`.
Um `OrderedDict` preserva a ordem das chaves, como demonstrado abaixo:
>>> from collections import OrderedDict
>>> od = OrderedDict()
>>> od['first']='one'
>>> od['second']='two'
>>> od['third']='three'
>>> od
OrderedDict([('first', 'one'), ('second', 'two'), ('third', 'three')])
>>> od.keys()
odict_keys(['first', 'second', 'third'])
Defaultdict
Erros de chave são comuns ao trabalhar com dicionários em Python. Quando se tenta acessar uma chave que não foi adicionada ao dicionário, um erro `KeyError` é gerado.
Utilizando `defaultdict` do módulo `collections`, você pode lidar com esse cenário de forma nativa. Ao tentar acessar uma chave inexistente, ela é adicionada e inicializada com os valores padrão especificados pela fábrica padrão.
>>> from collections import defaultdict >>> prices = defaultdict(int) >>> prices['carrots'] 0
Pilhas
Uma pilha é uma estrutura de dados LIFO (Last-In, First-Out – Último a Entrar, Primeiro a Sair). As operações em uma pilha são:
- Adicionar elementos ao topo: operação push.
- Remover elementos do topo: operação pop.
Vejamos um exemplo que ilustra como as operações push e pop de uma pilha funcionam:
Como Implementar uma Pilha Usando uma Lista
Em Python, uma pilha pode ser implementada utilizando listas.
| Operação na Pilha | Operação Equivalente na Lista |
| Push (empilhar) | Adicionar um elemento ao final da lista utilizando `append()` |
| Pop (desempilhar) | Remover e retornar o último elemento utilizando `pop()` |
O trecho de código abaixo demonstra como emular o comportamento de uma pilha utilizando uma lista em Python:
>>> l_stk = [] >>> l_stk.append(4) >>> l_stk.append(3) >>> l_stk.append(7) >>> l_stk.append(2) >>> l_stk.append(9) >>> l_stk [4, 3, 7, 2, 9] >>> l_stk.pop() 9
Como Implementar uma Pilha Usando um Deque
Outro método para implementar uma pilha é utilizar um deque do módulo `collections`. Deque significa fila dupla e permite adicionar e remover elementos de ambas as extremidades.
Para emular uma pilha, podemos:
- adicionar elementos ao final do deque usando `append()` e
- remover o último elemento adicionado utilizando `pop()`.
>>> from collections import deque >>> stk = deque() >>> stk.append(4) >>> stk.append(3) >>> stk.append(7) >>> stk.append(2) >>> stk.append(9) >>> stk deque([4, 3, 7, 2,9]) >>> stk.pop() 9
Filas
Uma fila é uma estrutura de dados FIFO (First-In, First-Out – Primeiro a Entrar, Primeiro a Sair). Elementos são adicionados ao final da fila e removidos do início (cabeça da fila), conforme ilustrado abaixo:
A estrutura de dados fila pode ser implementada utilizando um deque:
- Adicione elementos ao final da fila utilizando `append()`.
- Utilize o método `popleft()` para remover elementos do início da fila.
>>> from collections import deque >>> q = deque() >>> q.append(4) >>> q.append(3) >>> q.append(7) >>> q.append(2) >>> q.append(9) >>> q.popleft() 4
Heaps
Nesta seção, exploraremos heaps binários, com foco em min heaps.
Um min heap é uma árvore binária completa. Vamos detalhar o significado de uma árvore binária completa:
- Uma árvore binária é uma estrutura de dados em árvore, onde cada nó tem no máximo dois nós filhos, e cada nó é menor que seus filhos.
- O termo “completa” significa que a árvore está totalmente preenchida, com exceção, talvez, do último nível. Se o último nível estiver parcialmente preenchido, os nós serão preenchidos da esquerda para a direita.
Como cada nó tem no máximo dois nós filhos e é menor que eles, a raiz de um min heap é sempre o menor elemento.
Aqui está um exemplo de min heap:
Em Python, o módulo `heapq` auxilia na construção de heaps e na execução de operações sobre eles. Vamos importar as funções necessárias do `heapq`:
>>> from heapq import heapify, heappush, heappop
Se você tiver uma lista ou outro iterável, pode construir um heap chamando `heapify()`:
>>> nums = [11,8,12,3,7,9,10] >>> heapify(nums)
É possível verificar o primeiro elemento para confirmar que ele é o menor elemento:
>>> nums[0] 3
Ao inserir um elemento no heap, os nós serão reorganizados para manter a propriedade de min heap.
>>> heappush(nums,1)
Como inserimos 1 (1 < 3), `nums[0]` passa a retornar 1, que agora é o menor elemento (e o nó raiz).
>>> nums[0] 1
Para remover elementos do min heap, utilize a função `heappop()`:
>>> while nums: ... print(heappop(nums)) ...
# Output 1 3 7 8 9 10 11 12
Max Heaps em Python
Agora que você entende min heaps, consegue imaginar como implementar um max heap?
Uma forma de converter um min heap em um max heap é multiplicar cada número por -1. Os números negados, dispostos em um min heap, são equivalentes aos números originais dispostos em um max heap.
Em Python, podemos multiplicar os elementos por -1 ao adicionar um elemento ao heap utilizando `heappush()`:
>>> maxHeap = [] >>> heappush(maxHeap,-2) >>> heappush(maxHeap,-5) >>> heappush(maxHeap,-7)
O nó raiz – multiplicado por -1 – será o maior elemento.
>>> -1*maxHeap[0] 7
Ao remover elementos do heap, utilize `heappop()` e multiplique por -1 para recuperar o valor original:
>>> while maxHeap: ... print(-1*heappop(maxHeap)) ...
# Output 7 5 2
Filas de Prioridade
Finalizaremos nossa discussão com a estrutura de dados fila de prioridade em Python.
Em uma fila, elementos são removidos na ordem em que entram. Uma fila de prioridade, no entanto, atende aos elementos com base na sua prioridade, o que é útil em aplicações como agendamento. O elemento com a maior prioridade é sempre retornado primeiro.
Chaves podem ser utilizadas para definir a prioridade. Neste caso, utilizaremos pesos numéricos para as chaves.
Como Implementar Filas de Prioridade Usando Heapq
A implementação de uma fila de prioridade utilizando `heapq` e listas em Python é a seguinte:
>>> from heapq import heappush,heappop >>> pq = [] >>> heappush(pq,(2,'write')) >>> heappush(pq,(1,'read')) >>> heappush(pq,(3,'code')) >>> while pq: ... print(heappop(pq)) ...
Ao remover elementos, a fila atenderá primeiro ao elemento de maior prioridade (1, ‘read’), seguido por (2, ‘write’) e, por fim, (3, ‘code’).
# Output (1, 'read') (2, 'write') (3, 'code')
Como Implementar Filas de Prioridade Usando PriorityQueue
Para implementar uma fila de prioridade, também podemos utilizar a classe `PriorityQueue` do módulo `queue`. Esta classe também utiliza heaps internamente.
Aqui está a implementação equivalente utilizando `PriorityQueue`:
>>> from queue import PriorityQueue >>> pq = PriorityQueue() >>> pq.put((2,'write')) >>> pq.put((1,'read')) >>> pq.put((3,'code')) >>> pq <queue.PriorityQueue object at 0x00BDE730> >>> while not pq.empty(): ... print(pq.get()) ...
# Output (1, 'read') (2, 'write') (3, 'code')
Conclusão
Neste guia, exploramos diversas estruturas de dados nativas em Python, examinando suas operações e métodos.
Também analisamos outras estruturas de dados, como pilhas, filas e filas de prioridade, bem como suas implementações em Python, utilizando a funcionalidade do módulo `collections`.
Explore mais projetos Python amigáveis para iniciantes.