Escreva uma função que, dado duas filas, concatene as duas filas. Retorne a fila concatenada em F1. F2 deve ficar vazia.

Passo 1

O enunciado pede uma função que receba duas filas (F1 e F2), concatene os elementos de F2 ao final de F1 e deixe F2 vazia. O conteúdo aqui é estrutura de dados fila, em que precisamos usar as operações básicas de enfileirar (enqueue) e desenfileirar (dequeue).

Passo 2

Para entender como mexer em filas, vamos relembrar que uma fila oferece pelo menos três operações: 1) filaVazia(F) retorna verdadeiro se não houver elementos; 2) desenfileira(F) retira e retorna o elemento no início da fila; 3) enfileira(F, x) insere o elemento x no final da fila.
A estratégia mais direta é retirar todos os elementos de F2 e ir colocando em F1. Como cada desenfileira reduz F2 e cada enfileira acrescenta em F1, ao final teremos exatamente F1 original seguido de F2 original, e F2 vazia.

Passo 3

Implementamos um laço de repetição que enquanto F2 não estiver vazia faça: 1) x ← desenfileira(F2); 2) enfileira(F1, x). Esse laço roda exatamente uma vez para cada elemento originalmente em F2.
Quando o laço terminar, F2 estará vazia (pois retiramos todos os seus elementos) e F1 estará atualizada com a concatenação. A complexidade desse método é O(n), onde n é o número de elementos em F2.

Passo 4

A seguir, apresentamos o pseudocódigo da função concatenaFilas.

Resposta

function concatenaFilas(Fila *F1, Fila *F2) {
while (!filaVazia(F2)) {
TipoDado x = desenfileira(F2);
enfileira(F1, x);
}
// Ao sair do laço, F1 contém a concatenação e F2 está vazia
}

Exercícios relacionados