我一直在思考如何将双端队列(即双端队列)实现为不可变的数据结构。
似乎有不同的方法可以做到这一点。AFAIK,不可变数据结构通常是分层的,因此它的主要部分可以在修改操作(例如插入或删除项目)后重用。
Eric Lippert 在他的博客上有两篇 关于此主题的文章,以及 C# 中的示例实现。
他的两个实现都让我觉得比实际需要的更复杂。不能将双端队列简单地实现为二叉树,其中元素只能在树的“左”(前)和“右”(后)插入或删除?
o
/ \
… …
/ \
… …
/ \ / \
front --> L … … R <-- back
此外,树将通过旋转保持合理的平衡:
- 在前面插入或从后面取出时向右旋转,以及
- 从前面移除或从后面插入时左旋转。
在我看来,Eric Lippert 是一个非常聪明的人,我非常尊重他,但他显然没有考虑过这种方法。因此,我想知道,这是有充分理由的吗?我建议的实现双端队列的方法是否幼稚?