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.
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.