algorithm - 在 O(1) 中实现并合并两个堆栈

Question

有人问过我这个问题。

我得到了 2 个堆栈。我必须执行以下操作:

// Pass one of the stacks and a value to insert
push(Stack stack, value)    
pop(Stack stack, val)    
merge(Stack s1, Stack s2)

我必须在 O(1) 中执行 push 和 pop 等堆栈操作。到目前为止，我已经使用链表成功地实现了这些操作。

但是如何在 O(1) 中合并两个堆栈？我在 O(1) 中找不到如何做到这一点。

也许我需要使用一些其他的数据结构或其他东西？

Answer 1

如果您的堆栈对象保留堆栈的两端(顶部/底部、开始/结束、头/尾等)，这真的很容易。我将使用顶部/底部来回答这个问题。

当你实现 push/pop 时，你操作的是顶层对象。底部将保持不变(除非堆栈为空)并且代表它的节点会将其下一个指针设置为空。

因此，要合并两个堆栈，您需要一个堆栈的底部，将其指向另一个堆栈的顶部，并返回一个由其他指针组成的"new"堆栈。

Stack merge(Stack s1, Stack s2) {
  // join the stacks
  s2.bottom.next = s1.top

  // make a nice object to give back
  Stack result;
  result.bottom = s1.bottom
  result.top = s2.top

  // cleanup the parameters so they don't mess up the new structure.
  s1.bottom = s1.top = s2.bottom = s2.top = null;

  return result;
}

如果您没有将这两个指针很好地保存在堆栈对象中，您将需要遍历其中一个堆栈以获得将保留在这里作为底部的内容，从而使复杂度为 O(N)。