我一直在寻找持久的实时可连接双端队列的工作。有多种方法在双端队列的级联上具有对数复杂性,有些方法已摊销了固定时间的实现,但是在固定时间级联的情况下,实时(未摊销)双端队列的数量要少得多。
Haim Kaplan和Robert Tarjan,Purely Functional, Real-Time Deques with Catenation在1999年的文章中描述了一种众所周知的实时可连接双端队列。但是,关于双端双引语的wikipedia page和this 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
并指出
因此,显然到目前为止,还没有 session 或期刊对数据结构的描述,并且至少到目前为止,您已经获得了明确的引用。请注意,这门类(class)是由塔里安(Tarjan)提出的。您可以通过电子邮件查询此数据结构。
关于algorithm - Tarjan和Mihaescu的 "*simpler* real-time catenable deque"工作在哪里?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/16422795/