gas*_*che 10 algorithm deque data-structures
我一直在寻找持久的实时可连接deques的工作.有各种方法具有用于连接deques的对数复杂性,有些方法具有摊销的常数时间实施,但实时(非摊销)具有恒定时间连接的deques少得多.
众所周知的实时可连接deque是1999年由Haim Kaplan和Robert Tarjan撰写的文章,Purely Functional,Real-Time Deques with Catenation.然而,关于deques 的维基百科页面和这个梦幻般的StackOverflow答案都提到了Robert Tarjan和Radu Mihaescu最近的工作(显然是2003年),这应该更简单.
有没有人链接到Robert Tarjan和Mihaescu关于这项工作的出版物？我在浏览网页时唯一能找到的就是一个.doc文档,显然是某些课程笔记的一部分,而且这种格式既不舒服,也不够可靠,无法实现.
有些网页将第二作者称为"Mihaesau",这似乎是一个错误.我找到了一个DBLP的出版物列表,更近期,没有提及可连接的队列,以及一个微薄的网页,没有链接到出版物部分.
CStheory.SE 上的一个很好的答案链接到.doc并指出
所以显然没有关于数据结构的会议或期刊描述，你已经得到了明确的参考，至少到现在为止。请注意，课程问题是由 Tarjan 给出的。您可以通过电子邮件询问有关此数据结构的信息。