我想维护一个不变的，有界的FIFO队列，可以在一段时间后从中删除最旧的值。在Scala中，immutable.Queue非常适合大小限制的队列(.size似乎是O(N)，因为它内部基于List，但是我可以单独维护大小)，但是似乎没有便宜的方法访问head元素以使用比O(N)便宜的任何东西来测试最旧值的年龄，因此我无法测试最旧条目的到期状态。有任何指向纯功能(不可变)实现的指针吗？
最佳答案
本文Haskell: Queues without pointers，
描述了具有O(1)摊销成本的纯功能队列(编辑:用于添加和删除元素)。我认为数据结构来自Chris Okasaki，更多细节在his book中。
基本思想是将队列分解为两个列表，一个列表用于正面，一个列表用于背面。新元素添加到“前”。 “后退”以相反的顺序存储，以方便弹出元素。当“后退”的所有元素都消失时，“前”将被反转并重新标识为“后退”。对于这些操作，此数据结构的摊销成本为O(1)，但是显然，通过某些工作，可以将其降低为O(1)。
编辑:Okasaki's paper描述了队列和双端队列(双端队列)的一种优雅，纯功能的实现。双端队列允许从任一端添加或删除元素。所有此类操作均为O(1)，最坏的情况。