Faça uma função que receba três filas, duas já preenchidas em ordem crescente e preencha a última com os valores das duas primeiras em ordem crescente.

Passo 1

O enunciado pede uma função que receba três filas (q1, q2 e q3), sendo que q1 e q2 já estão ordenadas de forma crescente, e que q3 comece vazia e seja preenchida com todos os elementos de q1 e q2, também em ordem crescente. O conteúdo aqui é técnica de mesclagem (merge) de duas sequências ordenadas usando operações básicas de fila (enqueue, dequeue, peek e isEmpty).

Passo 2

Para resolver, vamos usar uma ideia bem simples: enquanto as duas filas q1 e q2 tiverem elementos, a gente olha o elemento da frente de cada uma (peek) e retira (dequeue) o menor, colocando esse menor na fila q3 (enqueue).
Quando uma das filas ficar vazia, não há mais como comparar, então basta esvaziar a outra fila: enquanto q1 não estiver vazia, transferimos tudo para q3, e da mesma forma para q2. Isso garante que todos os elementos sejam copiados mantendo a ordenação.

Passo 3

Em termos de pseudocódigo, ficaria assim:
função mergeQueues(q1, q2, q3):
    enquanto q1 não está vazia e q2 não está vazia:
        se peek(q1) ≤ peek(q2):
            enqueue(q3, dequeue(q1))
        senão:
            enqueue(q3, dequeue(q2))
    enquanto q1 não está vazia:
        enqueue(q3, dequeue(q1))
    enquanto q2 não está vazia:
        enqueue(q3, dequeue(q2))
No final, q3 terá todos os elementos de q1 e q2, em ordem crescente, e q1 e q2 terão sido esvaziadas ou terão tido seus elementos transferidos para q3.

Resposta

Segue a implementação em pseudocódigo da função mergeQueues:
função mergeQueues(q1, q2, q3):
    // enquanto as duas filas tiverem elementos, compara e transfere o menor
    enquanto not isEmpty(q1) e not isEmpty(q2):
        se peek(q1) ≤ peek(q2):
            enqueue(q3, dequeue(q1))
        senão:
            enqueue(q3, dequeue(q2))
    // transfere o que sobrou de q1
    enquanto not isEmpty(q1):
        enqueue(q3, dequeue(q1))
    // transfere o que sobrou de q2
    enquanto not isEmpty(q2):
        enqueue(q3, dequeue(q2))
Dessa forma, a fila q3 fica preenchida com todos os valores de q1 e q2 em ordem crescente.

Exercícios relacionados