Ich verstand die traditionelle Art, entweder Push-Betrieb teuer oder pop-Betrieb teuer.Wie ein FIFO mit einem Stapel (LIFO) mit gleicher Komplexität für Push-und Pop-Operationen von FIFO implementieren
Wie macht man Push und Pop zu gleicher Komplexität?
Dies ist Standard Interview Frage. Gemeinsame Idee: minus x minus = plus. Sie verwenden 2 sequenziert Stapel:
+1. Aber bitte beachten Sie, dass dies zu einer * amortisierten * konstanten Zeit führt: die Pop-Operation wird immer wieder teuer (weil sie alles auf einmal kopieren muss), aber dies ergibt sich aus der konstanten Zeit, da die Kosten dafür Ein teurer "Pop" ist proportional zur Anzahl der nachfolgenden kostengünstigen "Pops". – ruakh
hat 2 Stapelzeiger einen zum schieben in und einen für – Spektre
knallend aus kann ich nur push(), pop(), isempty() Funktionen eines Stapels verwenden. Es sind keine Zeiger erlaubt (Zeiger würden das Problem sehr einfach machen). –
@PaulHankin: Ich versuche, die Komplexität der Insert() - und take() - Funktionen der Top-Antwort Ihres Links auszugleichen. –