Wie führe ich zwei Warteschlangen in eine Warteschlange?

Gegeben zwei Listen unterstützen die Operationen enqueue/push_back, dequeue/pop_front und Größe

Q1: A1 A2 A3
Q2: B1 B2 B3

wie kann ich Sie Zusammenführen in eine Dritte Warteschlange (auch unterstützt die gleichen Operationen), erhalten:

Q3: A1 B1 A2 B2 A3 B3

Ich bin mehr daran interessiert, einen Algorithmus zu verwenden, eher als irgendeine spezifische Sprache-Implementierungen.

Was wollen Sie tun, wenn Sie eine Warteschlange erschöpft früher als der andere? Zu stoppen? Weitermachen, ignorieren Sie alle fehlenden Elemente aus der kurzen Warteschlange? Keep going, putting-null-Elemente an die Stelle der fehlenden Elemente?

InformationsquelleAutor | 2009-05-18

  1. 3

    Hier einige pseudocode:

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

    Wo push fügt ein element in eine queue und pop entfernt das nächste element der queue und gibt es zurück.

    Beachten Sie, dass dies keine Arbeit für einen stack. Sie werden am Ende mit den Elementen zurück. Wenn Sie umkehren könnten den stack (zum Beispiel, indem Sie wiederholt die übertragung zu einem anderen Stapel), dann würde es auch funktionieren.

    InformationsquelleAutor rlbond

  2. 2

    Während beide Warteschlangen nicht leer sind, entfernen Sie ein Element aus und stellen Sie in die Warteschlange zu newQ. Dann aus der Warteschlange entfernt ein Element aus der queue B, Wenn entweder der Warteschlangen (A oder B) leer sind, entfernen Sie den rest von der anderen Warteschlange und enqueue-jedes element auf newQ.

    InformationsquelleAutor Evan Meagher

  3. 1

    Scheint es ganz offen um eine rekursive Implementierung:

    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)

    Beachten Sie, dass wir nur flip den Warteschlangen hin und her, wie wir recurse, um ein wechseln zwischen Ihnen, bis der eine leer ist, an welchem Punkt wir gerade Anhängen, von der einen zur anderen.

    Beachten Sie, dass, wenn dieses länger ist, als der Imperativ version gegeben durch ribond, dies bedeutet eine minimale Anzahl von isEmpty überprüft. Wenn Sie nichts dagegen tun, so viele Prüfungen wie seine macht in eine leicht optimierte version (assiging die isEmpty-Variablen Werte für re-use unten), können Sie entfernen Sie die append Funktion und nur zu halten, ruft merge statt, nach dem hinzufügen einer Erstprüfung zu merge, dass die tests für beide Warteschlangen nicht leer und der Abbruch der Rekursion, wenn so.

    Für diejenigen, die nicht vertraut mit Haskell, wir gehen zu bewegen, wird die nächste Funktion zu nennen (dies ist höher-um die funktionale Programmierung); in der append Fall, das ist nur anfügen, in der move Fall, dass eine "teilweise angewendet" move-Funktion: es wird der erste parameter qb angewendet, bevor wir uns move, und dann move gilt für die beiden anderen Parameter.

    Das klingt wie eine vernünftige Aufgabe könnte man begegnen, in Tag-zu-Tag-Geschäft der Programmierung. Allerdings, wenn dies ist ein Hausaufgaben-Funktion, ich schlage vor, Sie studieren sorgfältig, wie der obige code funktioniert, und ich denke, du wirst etwas lernen.

    Außerdem gibt es eine Möglichkeit, dass es einen Fehler im obigen code; beweist, dass es funktioniert (oder das finden der Fehler) wäre eine ausgezeichnete übung.

    InformationsquelleAutor Curt J. Sampson

Schreibe einen Kommentar