Algorithmen und Datenstrukturen · Middle · Frage 22 von 75
Wie setzt man eine Queue mit zwei Stacks so um, dass jede Operation amortisiert O(1) ist?
- 1Bei jedem Einreihen einen Stack in den anderen kopieren
- 2Beide Stacks sortiert halten und vom kleineren nehmen
- 3Auf „in“ ablegen; von „out“ nehmen und es leer aus „in“ auffüllen
Antwort zeigen
Richtige Antwort: Auf „in“ ablegen; von „out“ nehmen und es leer aus „in“ auffüllen
Erklärung
Das Umschichten kehrt die Reihenfolge um, sodass das älteste Element oben auf „out“ landet. Jedes Element wird höchstens einmal bewegt, n Operationen kosten also insgesamt O(n).