Faça uma função para retornar o número de elementos da fila que possuem valor ímpar.

Passo 1

A questão pede que a gente escreva uma função que, dada uma fila de inteiros, retorne quantos desses elementos têm valor ímpar. O conteúdo aqui é manipulação de filas (estrutura FIFO) e precisamos usar operações básicas: obter o tamanho da fila, retirar o elemento da frente (dequeue) e inserir no final (enqueue).

Passo 2

Para percorrer todos os elementos sem perder o estado original da fila, vamos usar a técnica de rotacionar a fila: primeiro guardamos o tamanho atual n, depois fazemos n iterações onde em cada iteração retiramos o elemento da frente, verificamos se é ímpar e o reenfileiramos no final. Assim a fila volta exatamente ao estado inicial.

Passo 3

Com isso definido, implementamos a função que inicializa um contador em zero, faz um loop de 1 até n, em cada passo faz dequeue, testa x bmod 2 neq 0 para descobrir se é ímpar, incrementa o contador se for, e finalmente reenfileira x. Ao fim do loop retornamos o contador.

Passo 4

A complexidade dessa função é O(n) em tempo e O(1) em espaço extra (além da fila original), pois fazemos exatamente n operações de dequeue e enqueue.

Passo 5

Segue o código em pseudocódigo C-like:

Resposta

int countOdd(Queue *q) {
int count = 0;
int n = queueSize(q); // pega o tamanho atual da fila
for (int i = 0; i < n; i++) {
int x = dequeue(q); // retira da frente
if (x % 2 != 0) { // testa se é ímpar
count++;
}
enqueue(q, x); // coloca de volta no final
}
return count;
}

Exercícios relacionados