FIFO-basierte Warteschlangenimplementierungen?

77

Ich benötige eine einfache FIFO-implementierte Warteschlange zum Speichern einer Reihe von Ints (es macht mir nicht viel aus, wenn es sich um eine generische Implementierung handelt).

Etwas, das schon für mich in der java.utilTrove / Guava-Bibliothek gebacken wurde ?

java collections queue Rajat Gupta
quelle
Los geht's: docs.oracle.com/javase/tutorial/collections/implementations/…
Koray Tugay

Antworten:

86

Ja. Warteschlange

LinkedList ist die trivialste konkrete Implementierung.

John B.
quelle
5
Beachten Sie, dass der Javadoc alle Implementierungen auflistet. Auch der zweite Link darüber zuLinkedList
John B
2
LinkedListist keine Schnittstelle; Es ist eine explizite Klasse. Alternativ ArrayDequeist häufig schneller.
Louis Wasserman
Ich muss meine Warteschlange nicht jederzeit ändern, die Anzahl der Elemente ist immer konstant.
Rajat Gupta
Gibt es Unterschiede zwischen ArrayDeque und ArrayQueue?
Rajat Gupta
3
Dies ist eigentlich nicht 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
60

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

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
}
DavidNg
quelle
14

ArrayDequeist wahrscheinlich die schnellste objektbasierte Warteschlange im JDK; Trove hat die TIntQueueSchnittstelle, aber ich weiß nicht, wo die Implementierungen leben.

Louis Wasserman
quelle
8
Um ArrayDequeals Warteschlange (FIFO) und nicht als Stapel (LIFO) zu fungieren, sollten Sie addund verwenden remove. Wenn Sie pushund verwenden pop, verhält es sich wie ein Stapel. (Genau genommen removeund popsind die gleichen, aber da add/popoder push/removenicht gut als Paare klingen, gehen wir mit add/removeund push/pop.)
ADTC
5

Queueist eine Schnittstelle, die Collectionin Java erweitert wird. Es verfügt über alle Funktionen, die zur Unterstützung der FIFOArchitektur erforderlich sind .

Für die konkrete Umsetzung können Sie verwenden LinkedList. LinkedList implementiert, Dequewas wiederum implementiert Queue. All dies ist Teil des java.utilPakets.

Einzelheiten zur Methode mit Beispielbeispiel finden Sie in der FIFO-basierten Warteschlangenimplementierung in Java .

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

Aniket Thakur
quelle
4

Eine LinkedList kann als Warteschlange verwendet werden - Sie müssen sie jedoch 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 daran , wenn Sie Push anstelle von Add verwenden (was Sie sehr wahrscheinlich intuitiv tun werden), wird dadurch ein Element am Anfang der Liste hinzugefügt, sodass es sich wie ein Stapel verhält.

Dies ist also nur dann eine Warteschlange, wenn sie 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
Gautam
quelle