相关疑难解决方法(0)

我一直在考虑如何将deque(即双端队列)实现为不可变数据结构.

似乎有不同的方法来做到这一点.AFAIK,不可变数据结构通常是分层的,因此在修改诸如插入或删除项之类的操作之后,可以重用它的主要部分.

Eric Lippert 在他的博客上有两篇 关于这个主题的文章,以及C#中的示例实现.

他的两个实现都让我觉得比实际需要更精细.难道deques只能被实现为二叉树,其中元素只能在树的"左"(前)和非"右"(后面)插入或删除？

                               o
                              / \
                             …   …
                            /     \
                           …       …
                          / \     / \
              front -->  L   …   …   R  <-- back

此外,树将与旋转保持合理平衡:

• 在插入前部或从背部移除时右旋转,和
• 从前面移开或在后面插入时左旋转.

在我看来,Eric Lippert是一个非常聪明的人,我非常尊重他,但他显然没有考虑这种方法.因此我想知道,这是有充分理由的吗？我建议的实施dequesnaïve的方法吗？

我在YouTube上看到了这个视频:https://www.youtube.com/watch？v = YQs6IC-vgmo,其中Bjarne说最好使用向量而不是链接列表.我无法掌握整个事情,所以任何人都可以用外行的话来解释他说的话吗？

PS:我是一名高中生,可以轻松处理链接列表,但我正在努力学习自己的向量.你能建议学习载体的任何来源吗？