Wenn ich mir einige Algorithmen-Übungen im Netz anschaue, habe ich ein interessantes gefunden:
Wie würden Sie einen FIFO mit einem LIFO implementieren?
Ich habe es selbst versucht, aber ich hatte nur eine Lösung: Jedes Mal, wenn wir das front Element des FIFO wollen, kopieren Sie den lifo in einen anderen lifo ( letztes letztes Element ausschließend) , das ist die Vorderseite), holen Sie das Frontelement und entfernen Sie es, kopieren Sie dann das zweite LIFO in das erste LIFO zurück.
Aber das ist natürlich schrecklich langsam, es macht eine einfache Schleife wie folgt:
%Vor%wird O (n²) anstelle von O (n) in einer Standardimplementierung des FIFO.
Natürlich werden LIFO nicht dazu gebracht, FIFO zu machen, und wir werden sicherlich nicht die gleiche Komplexität haben, indem wir einen "nativen" FIFO und einen gefälschten FIFO basierend auf einem LIFO verwenden, aber ich denke, dass es einen Weg gibt besser als O (n²). Hat jemand eine Idee dazu?
Vielen Dank im Voraus.
Sie können die amortisierte Zeitkomplexität von O(1) pro OP FIFO [Warteschlange] mit 2 LIFOs [Stapeln] ermitteln.
Angenommen, Sie haben stack1 , stack2 :
Beispiel:
%Vor% Um echtes O(1) [nicht amortisiert] zu erhalten, ist es viel komplizierter und erfordert mehr Stacks. Schaut euch einige der Antworten in diesen Beitrag
BEARBEITEN: Komplexitätsanalyse:
insert() ist trivalally O(1) [drücke ihn einfach auf stack1 ] push() ed ist und pop() höchstens zweimal, einmal von stack1 und einmal von stack2 . Da es keine Ops mehr gibt, haben wir für n elements höchstens 2n push() s und 2n pop() s, was uns höchstens 4n * O(1) complexity [da sowohl pop() und push() sind O(1) ], das ist O(n) - und wir bekommen amortisierte Zeit von: O(1) * 4n / n = O(1)
Sowohl LIFO als auch FIFO können mit einem Array implementiert werden, der einzige Unterschied zwischen ihnen besteht in der Funktionsweise der Zeiger tail und head . Wenn Sie mit LIFO beginnen, können Sie zwei zusätzliche Zeiger hinzufügen, die FIFO-Tail und Kopf widerspiegeln, und dann Methoden zum Hinzufügen, Entfernen usw. mit den FIFO-Zeigern hinzufügen.
Der Ausgabetyp wäre so schnell wie ein dedizierter FIFO- oder LIFO-Typ, würde jedoch beides unterstützen. Sie müssten unterscheidbare Typen wie AddToStack / AddToQueue, RemoveFromStack / RemoveFromQueue usw. verwenden.