Estrutura de Dados Deque e Filas de Prioridade: Modelando Urgência e Acesso Bidirecional

1. O Conceito de Deque (Double-Ended Queue)

O termo Deque é uma abreviação de Double-Ended Queue (Fila de Duas Pontas). Trata-se de uma estrutura de dados linear híbrida que combina o melhor dos dois mundos da Pilha e da Fila: ela permite que operações de adição e remoção aconteçam de forma eficiente tanto na extremidade inicial quanto na extremidade final.

Enquanto uma fila tradicional possui uma boca de entrada e uma boca de saída, um Deque possui duas extremidades totalmente abertas e bidirecionais. Essa versatilidade permite que um Deque seja usado intercambiavelmente como uma pilha LIFO, como uma fila FIFO ou como uma janela deslizante bidirecional de dados.

2. As Quatro Operações Primitivas do Deque

Um Deque padronizado expõe quatro métodos principais, todos operando em tempo constante (O(1)):

1. inserirInicio(valor) (push_front): Adiciona um novo elemento na primeira posição, antes de todos os outros.
2. removerInicio() (pop_front): Remove e devolve o primeiro elemento da coleção.
3. inserirFim(valor) (push_back): Adiciona um novo elemento após o último elemento existente.
4. removerFim() (pop_back): Remove e devolve o último elemento da coleção.

Além dessas quatro operações centrais, métodos de consulta como espiarInicio(), espiarFim() e verificadores de tamanho e ocupação completam a interface.

3. Implementação Completa do Deque em logicabr.dev

Abaixo, implementamos um Deque Circular sobre vetor utilizando a sintaxe oficial do logicabr.dev:

numero CAP_DEQUE = 6;
vetor dequeBuffer = [];
numero dInicio = 0;
numero dFim = 0;
numero dQtd = 0;

funcao dequeVazio() {
  retorno dQtd == 0;
}

funcao dequeCheio() {
  retorno dQtd == CAP_DEQUE;
}

// Inserir no Fim (push_back)
funcao inserirFim(numero valor) {
  se (dequeCheio()) {
    saida("[ERRO]: Deque Cheio ao tentar inserirFim: " + valor);
    retorno falso;
  }
  dequeBuffer[dFim] = valor;
  dFim = resto(dFim + 1, CAP_DEQUE);
  dQtd = dQtd + 1;
  saida("-> [FIM]: Inserido " + valor);
  retorno verdadeiro;
}

// Inserir no Inicio (push_front)
funcao inserirInicio(numero valor) {
  se (dequeCheio()) {
    saida("[ERRO]: Deque Cheio ao tentar inserirInicio: " + valor);
    retorno falso;
  }
  // Recuo circular defensivo para evitar indices negativos
  dInicio = resto(dInicio - 1 + CAP_DEQUE, CAP_DEQUE);
  dequeBuffer[dInicio] = valor;
  dQtd = dQtd + 1;
  saida("<- [INICIO]: Inserido " + valor);
  retorno verdadeiro;
}

// Remover do Inicio (pop_front)
funcao removerInicio() {
  se (dequeVazio()) {
    saida("[ERRO]: Deque Vazio ao tentar removerInicio.");
    retorno -1;
  }
  numero val = dequeBuffer[dInicio];
  dInicio = resto(dInicio + 1, CAP_DEQUE);
  dQtd = dQtd - 1;
  saida("<- [REMOVIDO DO INICIO]: " + val);
  retorno val;
}

// Remover do Fim (pop_back)
funcao removerFim() {
  se (dequeVazio()) {
    saida("[ERRO]: Deque Vazio ao tentar removerFim.");
    retorno -1;
  }
  dFim = resto(dFim - 1 + CAP_DEQUE, CAP_DEQUE);
  numero val = dequeBuffer[dFim];
  dQtd = dQtd - 1;
  saida("-> [REMOVIDO DO FIM]: " + val);
  retorno val;
}

saida("--- Demonstração do Deque logicabr ---");
inserirFim(10);
inserirFim(20);
inserirInicio(5);
inserirInicio(1);
removerFim();    // Remove 20
removerInicio(); // Remove 1
saida("Quantidade restante no Deque: " + dQtd);

4. Filas de Prioridade: Além do FIFO Puro

Em incontáveis cenários computacionais reais, atender tarefas estritamente por ordem de chegada é um grave erro arquitetural.

Uma Fila de Prioridade (Priority Queue) é uma estrutura abstrata onde cada elemento inserido possui dois atributos fundamentais:

• O Dado ou Carga Útil (Payload): O objeto, identificador ou valor a ser processado.
• A Prioridade (Priority Key): Um valor numérico que determina a urgência relativa do elemento.

A regra de despacho estipula que o elemento com o nível de prioridade mais elevado tem o direito de ser processado antes de qualquer elemento de prioridade inferior, independentemente de quando cada um chegou. Caso dois elementos possuam rigorosamente a mesma prioridade, a política de desempate comum recorre à regra FIFO temporal tradicional.

5. Políticas de Urgência e o Sistema de Triagem

Existem duas formas clássicas de categorizar prioridades:

• Prioridade Máxima (Max-Priority): Onde números maiores representam maior urgência (ex: 10 é mais urgente que 1).
• Prioridade Mínima (Min-Priority): Onde números menores representam maior urgência (ex: prioridade 1 significa altíssima gravidade, como na triagem de emergência médica).

6. Implementação de Fila de Prioridade com Múltiplas Faixas

Uma das arquiteturas mais rápidas e elegantes para prioridades discretas (como níveis 1 - Emergência, 2 - Urgência, 3 - Normal) é a técnica de Múltiplas Filas Dedicadas (Multi-Queue Architecture).

Criamos uma fila circular separada para cada nível de urgência. Quando o atendente solicita o próximo chamado, o algoritmo examina a fila de Emergência primeiro. Se ela estiver vazia, examina a de Urgência, e apenas quando ambas estiverem vazias atende a fila Normal:

// Três filas independentes por faixa de prioridade
vetor filaAlta = [];
numero qtdAlta = 0;

vetor filaMedia = [];
numero qtdMedia = 0;

vetor filaBaixa = [];
numero qtdBaixa = 0;

funcao inserirComPrioridade(texto paciente, numero nivel) {
  se (nivel == 1) {
    filaAlta[qtdAlta] = paciente;
    qtdAlta = qtdAlta + 1;
    saida("[ALTA PRIORIDADE]: " + paciente + " alocado na Faixa Vermelha.");
  } senao se (nivel == 2) {
    filaMedia[qtdMedia] = paciente;
    qtdMedia = qtdMedia + 1;
    saida("[MEDIA PRIORIDADE]: " + paciente + " alocado na Faixa Amarela.");
  } senao {
    filaBaixa[qtdBaixa] = paciente;
    qtdBaixa = qtdBaixa + 1;
    saida("[BAIXA PRIORIDADE]: " + paciente + " alocado na Faixa Verde.");
  }
}

funcao atenderProximoPrioritario() {
  // Verifica primeiro a faixa de alta gravidade
  se (qtdAlta > 0) {
    texto p = filaAlta[0];
    para (numero i = 0; i < qtdAlta - 1; i++) {
      filaAlta[i] = filaAlta[i + 1];
    }
    qtdAlta = qtdAlta - 1;
    saida(">>> [CHAMADA MEDICA - URGENTE]: Atendendo " + p + " (Faixa Vermelha)");
    retorno p;
  }

  // Se nao ha emergencia, verifica media
  se (qtdMedia > 0) {
    texto p = filaMedia[0];
    para (numero i = 0; i < qtdMedia - 1; i++) {
      filaMedia[i] = filaMedia[i + 1];
    }
    qtdMedia = qtdMedia - 1;
    saida(">>> [CHAMADA MEDICA]: Atendendo " + p + " (Faixa Amarela)");
    retorno p;
  }

  // Por fim, verifica baixa
  se (qtdBaixa > 0) {
    texto p = filaBaixa[0];
    para (numero i = 0; i < qtdBaixa - 1; i++) {
      filaBaixa[i] = filaBaixa[i + 1];
    }
    qtdBaixa = qtdBaixa - 1;
    saida(">>> [CHAMADA MEDICA]: Atendendo " + p + " (Faixa Verde)");
    retorno p;
  }

  saida("[CONSULTORIO LIVRE]: Nenhum paciente aguardando em nenhuma faixa.");
  retorno "";
}

saida("--- Testando Despacho por Prioridade ---");
inserirComPrioridade("Jose (Gripe)", 3);
inserirComPrioridade("Maria (Fratura)", 2);
inserirComPrioridade("Carlos (Infarto)", 1);

atenderProximoPrioritario();
atenderProximoPrioritario();
atenderProximoPrioritario();

7. Teste de Mesa e Auditoria de Despacho

Observe o comportamento ordenado da estrutura durante as chamadas:

Fundamentos de Arquitetura e Impacto no Hardware da CPU

Para compreender verdadeiramente a performance de um algoritmo em ambientes modernos, não basta analisar apenas a contagem de instruções no papel. A arquitetura dos processadores atuais (x86-64 e ARM) baseia-se em hierarquias complexas de memória: registradores ultra-rápidos, caches L1 (instruções e dados), L2, L3 e finalmente a memória RAM principal.

Quando executamos Escalonamento da CPU e Interrupções IRQ, o comportamento do circuito de Branch Prediction (predição de saltos condicionais) da CPU desempenha um papel determinante. Cada desvio condicional (como um comando se ou condição de laço enquanto) que não pode ser previsto com precisão pela CPU provoca uma descarga da esteira de instruções (pipeline stall), descartando ciclos preciosos de processamento.

No coração de qualquer processador moderno, a CPU recebe interrupções de hardware externas (IRQs) geradas pelo teclado, mouse, placa de rede e relógio interno de ciclos. Essas interrupções possuem prioridades rígidas registradas no APIC (Advanced Programmable Interrupt Controller). Se uma interrupção de erro de energia ou falha de clock ocorre, ela interrompe imediatamente a execução da tarefa atual para ser despachada com prioridade zero.

Sistemas operacionais de tempo real (RTOS - Real-Time Operating Systems) utilizam escalonadores de prioridade fixa preemptiva (Rate-Monotonic Scheduling). O escalonador garante que tarefas de controle de freios ABS em carros ou giroscópios em aeronaves nunca sofram latência provocada por tarefas de multimídia do painel de instrumentos.

Do ponto de vista da física da computação, a localidade espacial e temporal de referência é outro fator crítico: percorrer a memória em posições contíguas sequenciais permite que o mecanismo de Hardware Prefetching da CPU antecipe os próximos blocos de dados antes mesmo de serem solicitados pelo código, carregando linhas inteiras de cache (tipicamente 64 bytes) sem penalidade de latência.

Demonstração Matemática Rigorosa da Eficiência Assintótica

A análise teórica desenvolvida pela ciência da computação formal permite prever o comportamento exato do algoritmo quando o volume de dados (N) cresce exponencialmente em direção ao infinito:

A análise de complexidade demonstra que para conjuntos discretos com K níveis de prioridade, a inserção e remoção com multi-queues executam em O(1) amortizado. Em abordagens universais com chaves contínuas, Heaps Binários alcançam O(log N) para inserção e remoção do topo prioritário.

Essa dedução algébrica formal comprova por que a intuição superficial frequentemente engana programadores juniores. Saber classificar formalmente as curvas de crescimento assintótico separa o amador do engenheiro de software qualificado para arquitetar sistemas de alta escala que atendem milhões de usuários simultâneos sem lentidão.

10. O Problema da Inanição (Starvation) e a Técnica de Aging

O grande perigo de projetar filas puramente prioritárias é a Inanição (Starvation): imagine que José está com gripe na faixa verde. Se chegarem continuamente pacientes graves nas faixas vermelha e amarela durante todo o dia, José passará 12 horas aguardando e nunca será chamado!

A solução consagrada na ciência da computação chama-se Envelhecimento (Aging): a cada período de tempo (ou a cada número de atendimentos de alta prioridade), incrementamos a prioridade das tarefas antigas que ainda estão na espera. Eventualmente, uma tarefa humilde envelhece tanto que atinge o nível máximo e conquista seu direito de execução.

10.1 Comparação Arquitetural: Vetor Não-Ordenado vs Vetor Ordenado vs Heap

Ao projetar uma Fila de Prioridade em software, o arquiteto deve avaliar três estratégias de implementação primárias:

1. Abordagem 1: Vetor Não-Ordenado (Unsorted Array). Novos itens são simplesmente adicionados no fim em tempo (O(1)). Contudo, encontrar e remover o item de maior prioridade exige uma varredura completa por todo o vetor, custando (O(N)). Essa abordagem é excelente quando há milhões de inserções e pouquíssimas remoções.
2. Abordagem 2: Vetor Ordenado (Sorted Array). O vetor é mantido rigorosamente classificado pela prioridade. A remoção do elemento prioritário na ponta ocorre em tempo instantâneo (O(1)). No entanto, cada nova inserção exige encontrar a posição correta e deslocar os demais elementos, com custo (O(N)).
3. Abordagem 3: Heap Binário (Binary Heap). Uma árvore quase completa armazenada sobre um vetor que equilibra perfeitamente as duas operações: tanto a inserção quanto a extração do elemento mais urgente operam em tempo logarítmico (O(log N)).

Para sistemas com prioridades discretas pré-definidas (como os níveis de urgência hospitalar 1 a 5), a abordagem Multi-Queue apresentada na seção 6 supera todas as alternativas, atingindo tempo (O(1)) estrito tanto para enfileirar quanto para atender.

11. Os 5 Erros Críticos em Deques e Filas de Prioridade

Tenha atenção redobrada nestes pontos ao implementar essas estruturas:

12. Projeto Prático: Sistema de Triagem Hospitalar de Manchester em logicabr.dev

Vamos consolidar o conhecimento criando um sistema completo de Triagem com Política de Envelhecimento contra Inanição:

vetor nomesPacientes = [];
vetor gravidadePacientes = [];
vetor tempoEspera = [];
numero totalPacientes = 0;

funcao adicionarPaciente(texto nome, numero gravidade) {
  nomesPacientes[totalPacientes] = nome;
  gravidadePacientes[totalPacientes] = gravidade;
  tempoEspera[totalPacientes] = 0;
  totalPacientes = totalPacientes + 1;
  saida("[TRIAGEM]: " + nome + " registrado com Gravidade " + gravidade);
}

funcao aplicarAging() {
  para (numero i = 0; i < totalPacientes; i++) {
    tempoEspera[i] = tempoEspera[i] + 1;
    se (gravidadePacientes[i] == 2 e tempoEspera[i] >= 2) {
      gravidadePacientes[i] = 1;
      saida("[AGING / PROMOCAO]: Paciente " + nomesPacientes[i] + " promovido a Gravidade 1 devido ao tempo de espera!");
    }
  }
}

funcao chamarPacienteMaisUrgente() {
  se (totalPacientes == 0) {
    saida("[HOSPITAL]: Nenhum paciente em espera.");
    retorno;
  }

  numero melhorIndice = 0;
  numero maiorUrgencia = gravidadePacientes[0];

  para (numero i = 1; i < totalPacientes; i++) {
    se (gravidadePacientes[i] < maiorUrgencia) {
      maiorUrgencia = gravidadePacientes[i];
      melhorIndice = i;
    }
  }

  texto escolhido = nomesPacientes[melhorIndice];
  numero grav = gravidadePacientes[melhorIndice];

  saida(">>> [CHAMADA MEDICA]: " + escolhido + " (Gravidade " + grav + ") chamado ao Consultorio Principal!");

  para (numero j = melhorIndice; j < totalPacientes - 1; j++) {
    nomesPacientes[j] = nomesPacientes[j + 1];
    gravidadePacientes[j] = gravidadePacientes[j + 1];
    tempoEspera[j] = tempoEspera[j + 1];
  }
  totalPacientes = totalPacientes - 1;

  aplicarAging();
}

saida("==================================================");
saida("   SIMULADOR DE TRIAGEM HOSPITALAR COM AGING      ");
saida("==================================================");

adicionarPaciente("Paula (Sintoma Leve)", 2);
adicionarPaciente("Rafael (Trauma Grave)", 1);
adicionarPaciente("Marcos (Trauma Grave)", 1);

chamarPacienteMaisUrgente();
chamarPacienteMaisUrgente();
chamarPacienteMaisUrgente();
saida("==================================================");

Com o Deque e as Filas de Prioridade no seu arsenal técnico, você domina o controle temporal e de urgência em software. Na Aula 39, ingressaremos no universo da alocação dinâmica e ponteiros com as Listas Encadeadas.