3.1 Operações com dados: inserção, exclusão, busca
Inserção (Insert):
Operação de adicionar um novo elemento em uma estrutura de dados. A inserção pode ocorrer no início, no final ou em uma posição arbitrária da estrutura de dados.
Exclusão (Delete):
Operação de remover um elemento da estrutura de dados. A exclusão pode ocorrer pelo valor do elemento, pelo índice ou pela posição do elemento na estrutura de dados.
Busca (Search):
Operação de encontrar um elemento na estrutura de dados. A busca pode ocorrer por valor ou por outros critérios.
Exemplos de operações:
- Arrays: Inserção e exclusão requerem deslocamento de elementos, o que pode ser caro em termos de tempo —
O(n). - Listas ligadas: Inserção e exclusão podem ocorrer em
O(1)se a posição do nó for conhecida. - Tabelas hash: Busca, inserção e exclusão geralmente são realizadas em
O(1)no caso médio. - Árvores: Operações de busca, inserção e exclusão podem ser realizadas em
O(log n)em árvores balanceadas.
3.2 Conceitos básicos: array, lista, stack, fila
Array
Array — é uma sequência de elementos de um tipo, aos quais se pode acessar por índice.
Complexidade das operações: Acesso por índice — O(1), inserção e exclusão — O(n).
Exemplo: Criação de um array, alteração de elemento e exibição do resultado
# Criando um array de números
arr = [1, 2, 3, 4, 5]
# Alterando o elemento com índice 2 (terceiro elemento, pois a indexação começa em 0)
arr[2] = 10
# Exibindo o array alterado
print(arr) # Saída: [1, 2, 10, 4, 5]
# Adicionando um novo elemento ao final do array
arr.append(6)
print(arr) # Saída: [1, 2, 10, 4, 5, 6]
# Removendo elemento por índice
del arr[1]
print(arr) # Saída: [1, 10, 4, 5, 6]
Lista
Lista — é uma coleção de elementos, onde cada elemento contém um link para o próximo (lista simplesmente ligada) ou para o próximo e anterior (lista duplamente ligada).
Complexidade das operações: Inserção e exclusão — O(1) se a posição for conhecida, busca — O(n).
Exemplo: Criação de uma lista simplesmente ligada e sua travessia
# Definindo a estrutura do nó da lista
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Criando uma lista simplesmente ligada
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")
# Ligando os nós
node1.next = node2
node2.next = node3
# Definindo o início da lista
list_head = node1
# Percorrendo a lista e exibindo os dados
current = list_head
while current:
print(current.data)
current = current.next
# Saída:
# 101
# 102
# 103
Stack
Stack — é uma coleção de elementos com o princípio LIFO (Last In, First Out): o último a entrar é o primeiro a sair.
Complexidade das operações: Inserção (push) e exclusão (pop) — O(1).
Exemplo: Implementação e uso de stack para verificar o equilíbrio de parênteses
def is_balanced(expression):
stack = []
opening = "({["
closing = ")}]"
pairs = {")": "(", "}": "{", "]": "["}
for char in expression:
if char in opening:
stack.append(char)
elif char in closing:
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0
# Verificando várias expressões
print(is_balanced("({[]})")) # Saída: True
print(is_balanced("([)]")) # Saída: False
print(is_balanced("((")) # Saída: False
Fila (Queue)
Fila — é uma coleção de elementos com o princípio FIFO (First In, First Out): o primeiro a entrar é o primeiro a sair.
Complexidade das operações: Inserção (enqueue) e exclusão (dequeue) — O(1).
Exemplo: Implementação e uso de fila para simular o processamento de tarefas
from collections import deque
class TaskQueue:
def __init__(self):
self.queue = deque()
def add_task(self, task):
self.queue.append(task)
print(f"Tarefa '{task}' adicionada à fila")
def process_task(self):
if self.queue:
task = self.queue.popleft()
print(f"Processando tarefa: '{task}'")
else:
print("Fila vazia")
def display_queue(self):
print("Fila atual de tarefas:", list(self.queue))
# Criando e usando fila de tarefas
task_queue = TaskQueue()
task_queue.add_task("Enviar email")
task_queue.add_task("Atualizar banco de dados")
task_queue.add_task("Criar relatório")
task_queue.display_queue()
task_queue.process_task()
task_queue.process_task()
task_queue.display_queue()
# Saída:
# Tarefa 'Enviar email' adicionada à fila
# Tarefa 'Atualizar banco de dados' adicionada à fila
# Tarefa 'Criar relatório' adicionada à fila
# Fila atual de tarefas: ['Enviar email', 'Atualizar banco de dados', 'Criar relatório']
# Processando tarefa: 'Enviar email'
# Processando tarefa: 'Atualizar banco de dados'
# Fila atual de tarefas: ['Criar relatório']
3.3 Diferenças entre diferentes tipos de estruturas de dados
Aqui estão as principais diferenças entre diferentes tipos de estruturas de dados:
Arrays:
- Acesso: Acesso rápido por índice —
O(1). - Alteração de tamanho: Tamanho fixo, aumento requer cópia de todos os elementos —
O(n). - Adequado para: Acesso aleatório aos elementos, quando o tamanho dos dados é conhecido antecipadamente.
Listas ligadas:
- Acesso: Acesso lento por índice —
O(n). - Alteração de tamanho: Tamanho facilmente alterável, inserção e exclusão em
O(1). - Adequado para: Adição e remoção frequentes de elementos.
Stack:
- Princípio de funcionamento:
LIFO. - Operações: Inserção e exclusão apenas em uma extremidade —
O(1). - Adequado para: Execução de tarefas em ordem inversa, controle de chamadas de funções.
Fila:
- Princípio de funcionamento:
FIFO. - Operações: Inserção e exclusão em extremidades diferentes —
O(1). - Adequado para: Gerenciamento de tarefas pela ordem de chegada.
3.4 Aplicação de diferentes estruturas de dados
Exemplos de aplicação de diferentes estruturas de dados na prática:
Arrays
Armazenamento de dados de comprimento fixo, como dias da semana ou meses do ano.
Exemplo: Uso de array para trabalhar com dias da semana
# Criando um array com os dias da semana
days = ["Segunda-feira", "Terça-feira", "Quarta-feira", "Quinta-feira", "Sexta-feira", "Sábado", "Domingo"]
# Obtendo o dia da semana pelo índice (por exemplo, o terceiro dia)
print(days[2]) # Saída: Quarta-feira
# Modificando o nome do dia
days[0] = "Segunda-feira (início da semana)"
print(days[0]) # Saída: Segunda-feira (início da semana)
# Percorrendo todos os dias da semana
for day in days:
print(day)
# Saída:
# Segunda-feira (início da semana)
# Terça-feira
# Quarta-feira
# Quinta-feira
# Sexta-feira
# Sábado
# Domingo
Listas ligadas
Implementação de coleções dinâmicas, onde elementos podem ser adicionados e removidos do meio da coleção.
Exemplo: Implementação e uso de lista ligada para armazenar uma lista de afazeres
class TodoItem:
def __init__(self, task):
self.task = task
self.next = None
class TodoList:
def __init__(self):
self.head = None
def add_task(self, task):
new_item = TodoItem(task)
if not self.head:
self.head = new_item
else:
current = self.head
while current.next:
current = current.next
current.next = new_item
def display_tasks(self):
current = self.head
if not current:
print("Lista de afazeres está vazia")
else:
while current:
print(f"- {current.task}")
current = current.next
# Criando e usando lista de afazeres
todo = TodoList()
todo.add_task("Comprar mantimentos")
todo.add_task("Ligar para a mãe")
todo.add_task("Preparar apresentação")
print("Minha lista de afazeres:")
todo.display_tasks()
# Saída:
# Minha lista de afazeres:
# - Comprar mantimentos
# - Ligar para a mãe
# - Preparar apresentação
Stack
Execução de tarefas em ordem inversa, por exemplo, processamento de chamadas de funções em recursão, operações de desfazer (undo).
Exemplo: Uso de stack para reverter uma string
def reverse_string(s):
stack = []
# Colocando cada caractere da string na stack
for char in s:
stack.append(char)
reversed_s = ''
# Retirando caracteres da stack, formando a string invertida
while stack:
reversed_s += stack.pop()
return reversed_s
# Exemplo de uso
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"String original: {original}")
print(f"String invertida: {reversed_str}")
# Saída:
# String original: Hello, World!
# String invertida: !dlroW ,olleH
Fila
Gerenciamento de tarefas pela ordem de chegada, por exemplo, trabalhos na impressora, filas no atendimento ao cliente.
Exemplo: Simulação de fila de impressão de documentos
from collections import deque
class PrinterQueue:
def __init__(self):
self.queue = deque()
def add_document(self, document):
self.queue.append(document)
print(f"Documento '{document}' adicionado à fila de impressão")
def print_document(self):
if self.queue:
document = self.queue.popleft()
print(f"Imprimindo documento: '{document}'")
else:
print("Fila de impressão vazia")
def display_queue(self):
print("Fila atual de impressão:", list(self.queue))
# Criando e usando fila de impressão
printer = PrinterQueue()
printer.add_document("Relatório")
printer.add_document("Apresentação")
printer.add_document("Contrato")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()
# Saída:
# Documento 'Relatório' adicionado à fila de impressão
# Documento 'Apresentação' adicionado à fila de impressão
# Documento 'Contrato' adicionado à fila de impressão
# Fila atual de impressão: ['Relatório', 'Apresentação', 'Contrato']
# Imprimindo documento: 'Relatório'
# Imprimindo documento: 'Apresentação'
# Fila atual de impressão: ['Contrato']
Neste exemplo, criamos uma simples simulação de fila de impressão. Os documentos são adicionados ao final da fila e impressos na ordem de chegada, demonstrando o princípio FIFO (First In, First Out).
GO TO FULL VERSION