Queue mithilfe von 2 Stacks erstellen

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.
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben