我一直在寻找持久的实时可连接双端队列的工作。有多种方法在双端队列的级联上具有对数复杂性,有些方法已摊销了固定时间的实现,但是在固定时间级联的情况下,实时(未摊销)双端队列的数量要少得多。

Haim Kaplan和Robert Tarjan,Purely Functional, Real-Time Deques with Catenation在1999年的文章中描述了一种众所周知的实时可连接双端队列。但是,关于双端双引语的wikipedia pagethis fantastic StackOverflow answer都提到了Robert Tarjan和Radu Mihaescu的最新作品(显然是2003年),据说更简单。

有人链接到罗伯特·塔里扬(Robert Tarjan)和米哈斯库(Mihaescu)关于这项工作的出版物吗?浏览网页时,我唯一能找到的就是a .doc document,显然是一些类(class)笔记的一部分,这种格式既不便于阅读,也不够可靠,无法实现。

一些网页将第二作者称为“Mihaesau”,这似乎是一个错误。我找到了DBLP list of publications,它是最新的,没有提及可连接的队列,还有一个meager webpage,没有指向发布部分的链接。

最佳答案

great answer on CStheory.SE链接到该.doc并指出

  • most recent version of Kaplan & Tarjan's work was published in 2000。此版本在某些方面更简单。

  • 因此,显然到目前为止,还没有 session 或期刊对数据结构的描述,并且至少到目前为止,您已经获得了明确的引用。请注意,这门类(class)是由塔里安(Tarjan)提出的。您可以通过电子邮件查询此数据结构。

    关于algorithm - Tarjan和Mihaescu的 "*simpler* real-time catenable deque"工作在哪里?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/16422795/

    10-10 01:00