Ich habe nach der Arbeit an dauerhaften catenable Deques in Echtzeit gesucht. Es gibt verschiedene Ansätze, die logarithmische Komplexitäten für die Verkettung von Deques haben, und einige, die sich bei der Konstantzeitenimplementierung amortisiert haben, aber viel weniger Echtzeit (nicht amortisierte) Deques mit Konstant-Zeit-Verkettung.
Die bekannte Echtzeit-Catenable-Kurve ist diejenige, die 1999 in dem Artikel von Haim Kaplan und Robert Tarjan beschrieben wurde, Rein funktionale, Echtzeit-Deques mit Kettenbildung . Allerdings ist sowohl die Wikipedia-Seite auf Deques und diese fantastische StackOverflow-Antwort erwähnt jüngere Arbeiten (anscheinend 2003) von Robert Tarjan und Radu Mihaescu, die angeblich einfacher sind.
Hat jemand eine Verbindung zu einer Veröffentlichung von Robert Tarjan und Mihaescu zu dieser Arbeit? Das einzige, was ich beim Surfen im Internet finden konnte, ist a .doc Dokument , anscheinend ein Teil von einigen Kursnotizen, und dieses Format ist weder angenehm zu lesen noch vielleicht zuverlässig genug, um eine Implementierung darauf aufzubauen.
Einige Webseiten verweisen auf den zweiten Autor als "Mihaesau", was ein Fehler zu sein scheint. Ich fand eine DBLP-Publikationsliste , aktueller und ziehbare Warteschlangen und eine dürftige Seite ohne Links zu einem Veröffentlichungsteil.
Eine großartige Antwort auf CStheory.SE verweist auf diesen .doc und gibt dies an
Offensichtlich gibt es keine Konferenz- oder Zeitschriftenbeschreibung der Datenstruktur und Sie haben bereits die definitive Referenz, zumindest bis jetzt. Beachten Sie, dass der Kurs von Tarjan gestellt wird. Sie können per E-Mail nach dieser Datenstruktur fragen.
Tags und Links algorithm data-structures deque