Python

# Rápidos (tempo e espaço)

    # O(1) tempo, O(1) espaço
    def pega_central(a):
        return a[len(a)//2] if a else None

    # O(N) tempo, O(1) espaço
    def tem_x(s):
        for c in s:
            if c == 'X':
                return True
        return False

    # O(N log N) tempo, O(N) espaço
    def ordenar(a):
        return sorted(a)

    # O(N²) tempo, O(1) espaço
    def tem_par_igual(a):
        for i in range(len(a)):
            for j in range(i+1, len(a)):
                if a[i] == a[j]:
                    return True
        return False
    

def selection_sort(lista):
    """
    Implementa o algoritmo de ordenação Selection Sort.
    Complexidade de tempo: O(N²). Espaço: O(1).
    """
    n = len(lista)
    # O laço externo define a fronteira entre a parte ordenada e a desordenada.
    # Ele executa n-1 vezes, pois o último elemento não precisa ser verificado.
    for i in range(n - 1):
    # Assume que o menor elemento é o primeiro da parte não ordenada (posição i).
    indice_menor = i

    # O laço interno percorre a parte desordenada (de i+1 até o fim)
    # para encontrar o verdadeiro menor elemento.
    for j in range(i + 1, n):
        # Se encontrar um elemento menor, atualiza o índice.
        if lista[j] < lista[indice_menor]:
        indice_menor = j

    # Após encontrar o menor, se ele não for o próprio elemento i,
    # troca-o de lugar com o elemento no início da parte desordenada.
    if i != indice_menor:
        lista[i], lista[indice_menor] = lista[indice_menor], lista[i]

    return lista

# Exemplo de uso
dados = [64, 25, 12, 22, 11]
print(f"Lista original: {dados}")
lista_ordenada = selection_sort(dados)
print(f"Lista ordenada: {lista_ordenada}")
# Saída: Lista ordenada: [11, 12, 22, 25, 64]
                    

def insertion_sort(lista):
    """
    Implementa o algoritmo de ordenação Insertion Sort.
    Ele percorre a lista e insere cada elemento em sua posição
    correta na sub-lista ordenada à esquerda.
    """
    # Começa do segundo elemento (índice 1), pois o primeiro
    # já é considerado uma sub-lista ordenada.
    for i in range(1, len(lista)):
        chave = lista[i]  # O elemento que queremos posicionar.
        j = i - 1         # O índice do último elemento da sub-lista ordenada.
        
        # Move os elementos da sub-lista ordenada que são maiores
        # que a chave para a direita, abrindo espaço.
        while j >= 0 and chave < lista[j]:
            lista[j + 1] = lista[j]
            j -= 1
        
        # Insere a chave na posição correta (após o elemento
        # que é menor ou igual a ela).
        lista[j + 1] = chave
    return lista

# Exemplo
dados = [5, 2, 4, 6, 1, 3]
print(f"Lista original: {dados}")
lista_ordenada = insertion_sort(dados)
print(f"Lista ordenada: {lista_ordenada}")
# Saída: Lista ordenada: [1, 2, 3, 4, 5, 6]

# Classe para representar a estrutura de dados LIFO (Last-In, First-Out)
class Pilha:
    def __init__(self):
        self.items = []
    def esta_vazia(self):
        return not self.items
    def empilhar(self, item):
        self.items.append(item)
    def desempilhar(self):
        if not self.esta_vazia():
            return self.items.pop()
    def topo(self):
        if not self.esta_vazia():
            return self.items[-1]

# Função 1: Conversão de Infixa para Pós-Fixa
def infixa_para_posfixa(expressao):
    precedencia = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    operadores = Pilha()
    posfixa = []
    tokens = expressao.split()

    for token in tokens:
        # Se for um número, vai direto para a saída.
        if token.isalnum():
            posfixa.append(token)
        # Se for '(', empilha para marcar o início de uma sub-expressão.
        elif token == '(':
            operadores.empilhar(token)
        # Se for ')', desempilha operadores até encontrar o '('.
        elif token == ')':
            op_topo = operadores.desempilhar()
            while op_topo != '(':
                posfixa.append(op_topo)
                op_topo = operadores.desempilhar()
        # Se for um operador...
        else:
            # Desempilha operadores de maior ou igual precedência.
            while (not operadores.esta_vazia() and
                   operadores.topo() != '(' and
                   precedencia.get(operadores.topo(), 0) >= precedencia.get(token, 0)):
                posfixa.append(operadores.desempilhar())
            # Empilha o operador atual.
            operadores.empilhar(token)
            
    # Desempilha todos os operadores restantes.
    while not operadores.esta_vazia():
        posfixa.append(operadores.desempilhar())
        
    return " ".join(posfixa)

# Função 2: Avaliação da Expressão Pós-Fixa
def avaliar_posfixa(expressao):
    operandos = Pilha()
    tokens = expressao.split()

    for token in tokens:
        # Se for um número, empilha na pilha de operandos.
        if token.isdigit():
            operandos.empilhar(int(token))
        # Se for um operador...
        else:
            # Desempilha os dois últimos operandos.
            op2 = operandos.desempilhar()
            op1 = operandos.desempilhar()
            # Realiza a operação e empilha o resultado.
            if token == '+': resultado = op1 + op2
            elif token == '-': resultado = op1 - op2
            elif token == '*': resultado = op1 * op2
            elif token == '/': resultado = op1 / op2
            elif token == '^': resultado = op1 ** op2
            operandos.empilhar(resultado)
            
    # O resultado final é o único item na pilha.
    return operandos.desempilhar()

# --- Exemplo de Uso ---
# IMPORTANTE: A expressão infixa deve ter espaços entre cada token.
expressao_infixa = "10 + 3 * 5 / ( 16 - 4 )"

print(f"Expressão Infixa: {expressao_infixa}")

expressao_posfixa = infixa_para_posfixa(expressao_infixa)
print(f"Expressão Pós-fixa: {expressao_posfixa}")
# Saída: Expressão Pós-fixa: 10 3 5 * 16 4 - / +

resultado = avaliar_posfixa(expressao_posfixa)
print(f"Resultado da Avaliação: {resultado}")
# Saída: Resultado da Avaliação: 11.25

class No:
    """Nó da lista encadeada para a fila de prioridades."""
    def __init__(self, dado, prioridade):
        self.dado = dado
        self.prioridade = prioridade
        self.proximo = None

class FilaDePrioridades:
    """Implementa uma Fila de Prioridades usando lista encadeada."""
    def __init__(self):
        self.inicio = None

    def esta_vazia(self):
        return self.inicio is None

    def inserir(self, dado, prioridade):
        novo_no = No(dado, prioridade)
        
        # Caso 1: A fila está vazia ou o novo nó tem maior prioridade que o início
        if self.esta_vazia() or prioridade < self.inicio.prioridade:
            novo_no.proximo = self.inicio
            self.inicio = novo_no
        else:
            # Caso 2: Percorre a fila para encontrar o local de inserção
            atual = self.inicio
            while atual.proximo is not None and atual.proximo.prioridade <= prioridade:
                atual = atual.proximo
            
            # Insere o novo nó
            novo_no.proximo = atual.proximo
            atual.proximo = novo_no
            
    def remover(self):
        """Remove e retorna o elemento de maior prioridade (o primeiro)."""
        if self.esta_vazia():
            print("A fila está vazia.")
            return None
        
        dado_removido = self.inicio.dado
        self.inicio = self.inicio.proximo
        return dado_removido
        
    def exibir(self):
        if self.esta_vazia():
            print("Fila vazia.")
            return
        
        atual = self.inicio
        fila_str = ""
        while atual:
            fila_str += f"[{atual.dado} (P:{atual.prioridade})] -> "
            atual = atual.proximo
        print(fila_str + "None")


# --- Exemplo de Uso ---
# Usaremos prioridades menores para indicar maior importância (ex: P1 > P2)
fila_processos = FilaDePrioridades()

fila_processos.inserir("Processo C - Baixa", 3)
fila_processos.inserir("Processo A - Urgente", 1)
fila_processos.inserir("Processo D - Baixa", 3)
fila_processos.inserir("Processo B - Média", 2)

print("Fila de prioridades atual:")
fila_processos.exibir()
# Saída: [Processo A - Urgente (P:1)] -> [Processo B - Média (P:2)] -> 
# [Processo C - Baixa (P:3)] -> [Processo D - Baixa (P:3)] -> None

print("\nRemovendo processos por ordem de prioridade:")
print(f"Removido: {fila_processos.remover()}") # Remove A
print(f"Removido: {fila_processos.remover()}") # Remove B
print(f"Removido: {fila_processos.remover()}") # Remove C (entrou antes de D)

print("\nFila após remoções:")
fila_processos.exibir()
# Saída: [Processo D - Baixa (P:3)] -> None