FIFO-basierte Warteschlangenimplementierungen?

Lesezeit: 3 Minuten

Benutzer-Avatar
Rajat Gupta

Ich brauche eine einfache FIFO-implementierte Warteschlange zum Speichern einer Reihe von Ints (es macht mir nichts aus, wenn es sich um eine generische Implementierung handelt).

Alles, was schon für mich eingebacken ist java.util oder Trove/Guava-Bibliothek?

Benutzer-Avatar
Johannes B

Ja. Warteschlange

VerlinkteListe die trivialste konkrete Implementierung zu sein.

  • Beachten Sie, dass das Javadoc alle Implementierungen auflistet. Auch der zweite Link darüber zu LinkedList

    – Johannes B

    18. April 2012 um 16:26 Uhr

  • LinkedList ist keine Schnittstelle; es ist eine explizite Klasse. Abwechselnd, ArrayDeque ist häufig schneller.

    – Louis Wassermann

    18. April 2012 um 16:26 Uhr

  • Ich muss die Größe meiner Warteschlange nicht jederzeit ändern, die Anzahl der Elemente ist immer konstant.

    – Rajat Gupta

    18. April 2012 um 16:36 Uhr

  • Gibt es Unterschiede zwischen ArrayDeque und ArrayQueue?

    – Rajat Gupta

    18. April 2012 um 16:38 Uhr


  • Dies ist nicht wirklich wahr: Laut Javadoc ist Queue nicht unbedingt FIFO: docs.oracle.com/javase/7/docs/api/java/util/Queue.html. LinkedList kann als Warteschlange verwendet werden, da die Reihenfolge jedoch festgelegt ist.

    – Pieter Bos

    14. Dezember 2013 um 21:42 Uhr

Benutzer-Avatar
DavidNg

Hier ist ein Beispielcode für die Verwendung der integrierten FIFO-Warteschlange von Java:

public static void main(String[] args) {
    Queue<Integer> myQ = new LinkedList<Integer>();
    myQ.add(1);
    myQ.add(6);
    myQ.add(3);
    System.out.println(myQ);   // 1 6 3
    int first = myQ.poll();    // retrieve and remove the first element
    System.out.println(first); // 1
    System.out.println(myQ);   // 6 3
}

ArrayDeque ist wahrscheinlich die schnellste objektbasierte Warteschlange im JDK; Trove hat die TIntQueue Schnittstelle, aber ich weiß nicht, wo ihre Implementierungen leben.

  • Zum ArrayDeque um als Warteschlange (FIFO) und nicht als Stapel (LIFO) zu fungieren, sollten Sie verwenden add und remove. Wenn du benutzt push und pop, verhält es sich wie ein Stack. (Genau genommen, remove und pop sind die gleichen, aber da add/pop oder push/remove als Paar nicht gut klingen, gehen wir mit add/remove und push/pop.)

    – ADTC

    22. Januar 2015 um 10:36 Uhr

EIN VerlinkteListe kann als Warteschlange verwendet werden – aber Sie müssen es richtig verwenden. Hier ist ein Beispielcode:

@Test
public void testQueue() {
    LinkedList<Integer> queue = new LinkedList<>();
    queue.add(1);
    queue.add(2);
    System.out.println(queue.pop());
    System.out.println(queue.pop());
}

Ausgabe :

1
2

Denken Sie daranwenn du benutzt drücken Anstatt von hinzufügen (was Sie sehr wahrscheinlich intuitiv tun werden), wird dadurch ein Element am Anfang der Liste hinzugefügt, wodurch es sich wie ein Stapel verhält.

Dies ist also nur dann eine Warteschlange, wenn es in Verbindung mit add verwendet wird.

Versuche dies :

@Test
public void testQueue() {
    LinkedList<Integer> queue = new LinkedList<>();
    queue.push(1);
    queue.push(2);
    System.out.println(queue.pop());
    System.out.println(queue.pop());
}

Ausgabe :

2
1

Benutzer-Avatar
Aniket Thakur

Queue ist eine sich erweiternde Schnittstelle Collection auf Java. Es hat alle Funktionen, die zur Unterstützung benötigt werden FIFO die Architektur.

Zur konkreten Umsetzung können Sie verwenden LinkedList. LinkedList implementiert Deque die wiederum implementiert Queue. All dies ist ein Teil von java.util Paket.

Einzelheiten zur Methode mit Beispielbeispielen finden Sie unter FIFO-basierte Queue-Implementierung in Java.

PS: Der obige Link führt zu meinem persönlichen Blog, der zusätzliche Details dazu enthält.

1256990cookie-checkFIFO-basierte Warteschlangenimplementierungen?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy