Queue mithilfe von 2 Stacks erstellen

Diskutiere Queue mithilfe von 2 Stacks erstellen im Java Basics - Anfänger-Themen Bereich.
L

lennero

Hallo. Ich soll eine Queue implementieren. Dazu sollen 2 Stacks genutzt werden. Eine Bedingung ist, dass alle Queue Operationen (Enqueue, Dequeue) eine "constant amortized time" haben. Das Prinzip habe ich noch nicht 100% verstanden. Ist das das Gegenstück zur Zeitkomplexität? Quasi Zeitkomplexität = worst case, amortized time = average case?

Naja hab mich trotzdem an die Aufgabe gewagt und das ganze folgendermaßen realisiert:

1. 2 private stacks primary und secondary als Felder der Queue Klasse
2. Der erste Stack wird primär zum einfügen genutzt, der zweite zum ausgeben.

Also 3 Enqueue Operationen würden dann so aussehen:

primary stack: 1, 2, 3
secondary stack: empty

Zeitkomplexität der enqueue Operation wäre dann O(1)

Um jetzt das erste Element auszugeben, pushe ich alles auf den zweiten Stack und pop das erste Element vom zweiten Stack

primary stack: empty
secondary stack 3, 2, 1

stack2.pop()

primary stack: empty
secondary stack 3, 2

Das hätte dann eine Zeitkomplexität von O(n) für ein Dequeue was ja eher nicht erwünscht ist.
 
mihe7

mihe7

Das hätte dann eine Zeitkomplexität von O(n) für ein Dequeue was ja eher nicht erwünscht ist.
Das ist ja genau der Unterschied: Du hast eine O(n) Operation, der Aufwand verteilt sich aber auf n Entnahmen (von denen jede für sich betrachtet konstante Zeit benötigt).
 
Thema: 

Queue mithilfe von 2 Stacks erstellen

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben