Comment fusionner deux files d'attente dans une file d'attente?

Question

Étant donné deux files d'attente à l'appui des opérations Enqueue/push_back, dequeue/pop_front, et la taille

Q1: A1 A2 A3 
Q2: B1 B2 B3 

comment puis-je les fusionner en une troisième file d'attente (supportant également les mêmes opérations), pour obtenir:

Q3: A1 B1 A2 B2 A3 B3 

Je suis plus intéressé par un algorithme à utiliser, plutôt que par des implémentations de langage spécifiques.

Answer 1

Bien que les deux files d'attente ne soient pas vides, retirez un élément de A et mettez-le en file d'attente sur newQ. Ensuite, supprimez un élément de la file d'attente B. Si l'une des files d'attente (A ou B) est vide, remettez en file d'attente le reste de l'autre file d'attente et mettez chaque élément en file d'attente sur newQ.

Answer 2

Voici quelques pseudo-code:

Queue mergeQueues(Queue A, Queue B) 
{ 
    Queue newQ; 
    while(A.nonempty() OR B.nonempty()) 
    { 
     if (A.nonempty()) 
      newQ.push(A.pop()); 
     if (B.nonempty()) 
      newQ.push(B.pop()); 
    } 
    return newQ; 
} 

Lorsque push insère un élément dans une file d'attente et pop supprime l'élément suivant dans la file d'attente et le renvoie.

Notez que cela ne fonctionne pas pour une pile. Vous finirez avec les éléments en arrière. Si vous pouviez inverser la pile (par exemple, en transférant plusieurs fois vers une autre pile), cela fonctionnerait.

Answer 3

Il semble tout à fait prête à une mise en œuvre récursive:

mergeQueues :: Queue a -> Queue a -> Queue a 
mergeQueues qa qb = 
    merge qa qb emptyQueue 
    where 
     merge qa qb qr 
      | isEmpty qa = append qb qr 
      | otherwise = move (merge qb) qa qr 
     append q qr 
      | isEmpty q = qr 
      | otherwise = move append q qr 
     move f q qr = 
      let (val,q') = pop q 
      in f q' (push val qr) 

Notez que nous suffit de retourner les files d'attente avant et en arrière comme nous RECURSE afin d'alterner entre eux, jusqu'à ce que l'un est vide, à quel point nous venons joindre de l'un à l'autre. Notez que, bien que ce soit plus long que la version impérative donnée par ribond, cela fait un nombre minime de vérifications isEmpty Si cela ne vous dérange pas de faire autant de contrôles que le sien dans une version légèrement plus optimisée (en associant les valeurs isEmpty aux variables pour réutilisation ci-dessous), vous pouvez supprimer la fonction append et continuer à appeler merge à la place, après avoir ajouté une initiale. test à merge qui vérifie que les deux files d'attente sont vides et termine la récursivité si c'est le cas.

Pour ceux qui ne sont pas familiers avec Haskell, nous passons pour déplacer la fonction suivante à appeler (c'est la programmation fonctionnelle d'ordre supérieur); dans le cas append, c'est juste ajouter, dans le cas move qui est une fonction de déplacement "partiellement appliquée": il obtient le premier paramètre, qb appliqué avant d'appeler move, puis move applique les deux autres paramètres.

Cela semble être une tâche raisonnable que l'on pourrait rencontrer dans la programmation d'entreprise au jour le jour. Cependant, si c'est une fonction de devoir, je vous suggère d'étudier attentivement comment le code ci-dessus fonctionne, et je pense que vous apprendrez quelque chose.

En outre, il existe une possibilité d'erreur dans le code ci-dessus; prouver que cela fonctionne (ou trouver le bug) serait un excellent exercice.