Gewusst wie: implementieren eine dequeue-mit zwei stacks

Dequeue - Doppelt ended queue: en-queue und de-queue möglich von beiden enden.

Wie definieren Sie den ADT-Operationen dequeue mit 2 stacks.

Umsetzung sollte auch in Betracht ziehen, die Leistung.

  • keine Mühe gezeigt
  • Ich bin nicht in der Lage zu finden, jeder gute link, der erklärt das Konzept klar. Wenn Sie eines gefunden, können Sie bitte teilen.
  • Nur queue-Implementierung mit Hilfe von stacks ist nicht dequeue mit zwei stacks.
  • Ist das für Hausaufgaben?
  • Nein. Einer meiner Freunde gefragt wurde, dies ist in einem interview, die einzige Lösung, die wir denken konnte, wurde bereits von Andreas in die Antworten, aber es ist nicht gut, performance-wise.
  • Gut, das ist der einzige Weg, es zu tun. Eine dequeue sollte wirklich umgesetzt werden, mit einer verknüpften Liste (vorzugsweise eine einfach verknüpfte Liste). Die Frage war wohl eher der Versuch, um festzustellen dein Freund das problem lösen Fähigkeiten. Das ist eigentlich das, warum man bezeichnet es auch als Kopf-Schwanz-verknüpften Liste.
  • Ich denke es ist nicht so, dass schlechte Leistung Weise tatsächlich. Sicher, es gibt bestimmte Aufgaben, die wirklich töten die Leistung, aber wenn Sie in etwa wissen, was Ihre Arbeitslast, die Sie verwenden können, andere (vielleicht schneller) Dinge, die als verknüpfte Listen.
  • Wie...?
  • zwei Stapel.
  • Naja, ein stack ist sehr im Grunde ein Spezialfall einer verknüpften Liste. Also, ich sehe nicht, wie sich die Verwendung von zwei stapeln wäre effizienter als eine einfach verknüpfte Liste zu sehen, wie die zwei-Stapel-Implementierung übertragen muss der Inhalt zwischen den Stapel in regelmäßigen Abständen. Dies kann dazu führen, dass einige (oder sogar viele) Operationen linear, in der Erwägung, dass eine einfach verkettete Liste-Implementierung ist garantiert Konstante Zeit.
  • aber Sie müssen auch sehen, Speicher-Allokation als ein Faktor. Ich bin implizieren, C/C++ als Sprache ist hier, wo die Stapel sind in der Regel implemted über arrays, im Gegensatz zu verketteten Listen, weil der zeitliche Aufwand, der für die Speicherreservierung ist signifikant höher bei verlinkten Listen. Auch die zwei-stack würde nur lineare Zeit für eine dequeue-operation, wenn der stack leer ist. und wieder, wenn Ihre Arbeitsauslastung deutet dies eher unwahrscheinlich ist, dann zwei stacks sollten in Ordnung sein.
  • Bitte beachten Sie, dass wirklich, ich will nicht sagen, dass die beiden Stapel sind in der Regel besser als eine doppelt verkettete Liste, nur, dass es gewisse Grenzfälle, wo Sie KÖNNEN theoretisch eine bessere Leistung. 🙂

InformationsquelleAutor Harshdeep | 2012-09-09
Schreibe einen Kommentar