使用 Memento 进行撤消/重做：堆栈、队列还是仅使用 LinkedList？

Question

实现 Memento 模式（用于撤消/重做）时最好的是什么

在女巫集合中 保留纪念品？

基本上，我需要这个（c =更改，u =撤消，r =重做）：

                  0
                  *c
            -1    0
                  *c
      -2    -1    0
                  *c
-3    -2    -1    0
                  <u
      -2    -1    0    1
                  *c
-3    -2    -1    0

变体：

• LinkedList - 原则上可能，可能没有优化。
• 队列 - IMO，不适合此任务。
• 堆栈 - 不适合撤消和重做；
• 双栈 - 也许是最佳选择，但无法控制撤消最大大小。

Answer 1

最后我用了LinkedList

Public Sub Add(ByVal item As T)
  If _list.Count > 0 Then
    If Me.IsFull Then
      ' we forgot (delete) the oldest state '
      _list.RemoveFirst()
    End If
    ' remove all the following the current items objects '
    Dim lastNode As LinkedListNode(Of T) = _list.Last
    While Not Object.ReferenceEquals(_currentNode, lastNode)
      _list.RemoveLast()
      lastNode = _list.Last
    End While
  End If

  ' add the new item and point current to it '
  _currentNode = _list.AddLast(item)
End Sub

Answer 2

优选地使用双端队列来有效地支持撤消重做操作。当用户输入单词时，节点被插入到队列中，并且头指针指向当前位置。当触发撤消操作时，只需将头移动到前一个节点，并在重做操作时将头指针移动到列表中的下一个位置。如果进行编辑操作，则删除 head 右侧的所有节点并插入到 head 的末尾。这样我们就可以以O(1)时间复杂度执行撤消重做。

Answer 3

当您撤消时，您将希望恢复到最近覆盖的数据。因此，您要使用的纪念品将是最后添加到集合中的纪念品。由于堆栈是后进先出 (LIFO)，因此它们应该非常适合您的意图。

注意：您可能需要研究命令模式，因为它对于实现撤消功能非常有用。

编辑：没有注意到你想要重做。从堆栈中弹出内容将会清除它，因此这对您的目的没有多大用处。链接列表应该可以工作。

Answer 4

您是否希望用户能够选择多个项目进行撤消或重做？

如果是这种情况，那么您可能需要使用通用 List 或 ObservableCollection（如果是 WPF/Silverlight），以便可以在 UI 中显示项目。您可以使用两个列表：一个用于撤消，一个用于重做。

Answer 5

使用双向链表。当用户使用撤消/重做时，他们可能会多次索引状态（例如，执行 4 次撤消，然后意识到他们走得太远并执行重做）。单个堆栈或队列不支持这一点。

两个堆栈将支持撤消和重做，但我认为使用它们有点浪费。一旦用户执行编辑（创建新的备忘录），所有重做备忘录最终都会被删除。因此，应用程序运行的大多数时间不会有“重做”纪念品。

假设您在标记为 .net 后进行了垃圾收集：
当用户进行编辑时，您需要对双向链表执行的操作是将链表的头引用设置为当前备忘录。如果您使用堆栈，那么您必须创建一个新堆栈或弹出其中的所有内容，以便 gc 释放重做备忘录。