Comment puis-je fusionner les deux files d'attente dans une file d'attente?

Donné deux files d'attente de soutenir les opérations de mise en file d'attente/push_back, dequeue/pop_front, et la taille

Q1: A1 A2 A3
Q2: B1 B2 B3

comment dois-je les fusionner en un troisième la file d'attente (également en charge les mêmes opérations), l'obtention d':

Q3: A1 B1 A2 B2 A3 B3

Je suis plus intéressé par un algorithme à utiliser, plutôt que n'importe quelle langue spécifique implémentations.

  • Que voulez-vous faire lors d'une file d'attente épuise plus vite que l'autre? Arrêter? Continuez, en ignorant les éléments manquants à partir de la courte file d'attente? Continuer de mettre null éléments en place des éléments manquants?
InformationsquelleAutor | 2009-05-18
  1. 4

    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;
}

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

    Noter que, cela ne fonctionne pas pour une pile. Vous allez vous retrouver avec les éléments en arrière. Si vous pouvez inverser la pile (par exemple, de façon répétée, le transfert à une autre pile), alors il serait de travailler.

    InformationsquelleAutor rlbond
  2. 2

    Alors que les deux files d'attente ne sont pas vides, retirer un élément de l'Un et de mettre en file d'attente à newQ. Ensuite, retirer un élément de la file d'attente B. Si l'une des files d'attente (A ou B) sont vides, retirer le reste de l'autre de la file d'attente et mettre en file d'attente chaque élément sur newQ.

    InformationsquelleAutor Evan Meagher
  3. 1

    Il semble tout à fait prête à un circuit de mise en œuvre:

    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)

    Remarque que nous venons de retourner les files d'attente avant en arrière, comme nous recurse afin d'alterner entre eux, jusqu'à ce que l'un est vide, auquel nous venons d'ajouter de l'un à l'autre.

    Noter que, même si c'est plus long que l'impératif de la version donnée par ribond, ce qui fait un nombre minimal de isEmpty contrôles. Si vous n'avez pas l'esprit de faire comme de nombreux contrôles que sa fait un peu plus version optimisée (assiging la isEmpty des valeurs à des variables à des fins de réutilisation ci-dessous), vous pouvez supprimer le append fonction et il suffit de garder appel merge au lieu de cela, après l'ajout d'un test initial pour merge que les tests pour les deux files d'attente étant vide et de résiliation de la récursivité si.

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

    Cela sonne comme une tâche raisonnable, l'on peut rencontrer dans la journée-à-jour des affaires de la programmation. Cependant, si c'est un des devoirs de fonction, je vous propose d'étudier avec soin la façon dont le code ci-dessus fonctionne, et je pense que vous allez apprendre quelque chose.

    Aussi, il ya une possibilité que il ya une erreur dans le code ci-dessus; prouver que cela fonctionne (ou trouver le bug) serait un excellent exercice.

    InformationsquelleAutor Curt J. Sampson