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.
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.
