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
, depois fazemos
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
até
, em cada passo faz dequeue, testa
para descobrir se é ímpar, incrementa o contador se for, e finalmente reenfileira
. Ao fim do loop retornamos o contador.
Passo 4
A complexidade dessa função é
em tempo e
em espaço extra (além da fila original), pois fazemos exatamente
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;
}
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;
}