Methode "Reverse" kehrt die Elemente einer queue

Dies ist nicht ein HW-oder-Verknüpfung. Dies ist etwas, was ich übe mich.

Gegeben eine Warteschlange schreiben Sie eine Methode "Reverse" kehrt die Elemente einer queue. MyQueue bleibt unverändert.

Signatur:

public Queue<T> reverse(Queue<T> myQueue) {

Hinweis: Es ist unbekannt, ob die Warteschlange mit Knoten oder array.

Der Warteschlange ist Methoden bereits implementiert, die wir nutzen können:

void enqueue(T element)
T dequeue();
boolean isFull();
boolean isEmpty();
int size();
kannst du bitte den code schreiben, dass du schon geschrieben hast?
das ist der Punkt, man kriegt nur die Namen der Methoden, die Sie verwenden können:
Hack: Verwenden Sie ein java.util.ArrayList als Puffer.
Meinst du nicht das JDK ist Queue Umsetzung?

InformationsquelleAutor user2272227 | 2013-05-31

  1. 5
    1. dequeue Elemente der input-queue auf einen Stapel
    2. pop-Elemente aus dem Stapel, enqueueing, jeweils in der Ausgabe-Warteschlange.
    Danke bro, das ist, was ich eigentlich Tat, aber ich wollte sehen, ob es eine bessere Lösung?
    Nicht mit der Schnittstelle, die Sie zur Verfügung gestellt. Es ist eine Daten-Struktur namens double ended queue, das ermöglicht Ihnen das hinzufügen und entfernen von Elementen an beiden enden. Die Umkehrung solch eine Datenstruktur, die getan werden kann, ohne alle temporären Puffer.

    InformationsquelleAutor Oswald

  2. 6

    Können Sie rückgängig machen, ein queue mit einem stack.

    Hier ist, wie in Java:

    public void reverse(Queue q)
{
    Stack s = new Stack();  //create a stack

    //while the queue is not empty
    while(!q.isEmpty())
    {  //add the elements of the queue onto a stack
       s.push(q.serve());
    } 

    //while the stack is not empty
    while(!s.isEmpty())
    { //add the elements in the stack back to the queue
      q.append(s.pop());
    }

}

    Den Anhängen und dienen Methoden der queue hinzufügen und entfernen von Elementen aus der Warteschlange.

    Hier ein Beispiel:

    Warteschlange Elemente:

    1 2 3 4

    Wenn die Elemente Hinzugefügt, um einen Stapel, der Nummer 1 werden am Ende der Liste, und 4 an der Spitze:

    1 2 3 4 <- top

    Nun pop-Stapel aus, und legen Sie die Elemente wieder in die Warteschlange:

    4 3 2 1

    Ich hoffe, dass dies geholfen.

    InformationsquelleAutor Alicia Rodriguez

  3. 4

    Können Sie dies tun, ohne andere arrays oder Listen einfach durch Rekursion:

    public static <T> Queue<T> flip(Queue<T> q) {
    Queue<T> ret = new Queue<>();
    recursiveFlip(q, ret);
    return ret;
}

private static <T> void recursiveFlip(Queue<T> src, Queue<T> dest) {
    T buffer = src.dequeue();
    if(!src.isEmpty()) {
        recursiveFlip(src, dest);
    }
    dest.enqueue(buffer);
}

    Ersten Elemente werden gestapelt im "flachen" Teil des Stapels, während die letzten Elemente in "tiefere" Teil, und bei der Rekursion wird das Ende erreicht, der "tiefere" Werte Hinzugefügt werden erste und "flach" last.

    Aber beachten Sie, dass ein jedes element bedeutet einen Schritt tiefer in die Rekursion, so stack-überlauf-Fehler wird auftreten, wenn die Warteschlange ist zu groß.

    Auch, die ursprüngliche Warteschlange nicht "überleben" der flip.

    InformationsquelleAutor kajacx

  4. 0

    Habe ich zwei verschiedene Ansätze, die nicht hängt davon ab, Ihre queue-Größe. Die erste benutzt Stack und das zweite - Java 8 Stream API (die schnellsten).

    Die effektivste Lösung für Umkehrung Warteschlange in meinen tests ist:

    private Queue<Integer> reverse(Queue<Integer> queue) {
        List<Integer> collect = queue.stream()
                .collect(Collectors.toList());
        Collections.reverse(collect);
        return new LinkedList<>(collect);
    }

    InformationsquelleAutor Dmytro Melnychuk

Schreibe einen Kommentar