algorithm - 合并一个包含升序元素的队列和一个包含降序元素的堆栈

Question

假设我有一个元素按升序排列的队列，即 head < 2nd < 3rd < ... < tail

和一个元素按降序排列的堆栈，即 top > 2nd > 3rd > ...

并且它们的大小最多相差 1（它们可以是相同的大小）。

将它们合并到同一个队列（或堆栈）中作为单个排序序列而不需要额外的堆栈/队列的最有效方法是什么？

似乎到目前为止我想到的最好的是二次算法，它基本上是选择排序，它并没有真正利用队列和堆栈是预先排序的事实及其大小。我想知道我们是否可以做得更好？

Answer 1

只需就地合并，将您的结果放在队列的末尾。保持计数，以便您知道何时完成。这是 O(n)。

这是在 python 中完成的。我没有使用队列或堆栈类，但您会看到 q 列表是 FIFO 并且 s 列表是 LIFO！

启用了最有趣的调试案例，因此您可以看到输出。

def sort(Q, S, debug=False):
  q = Q
  s = S
  size = len(Q) + len(S)
  handled = 0
  while handled < size:
    move_from_queue = len(s) == 0 or (len(q) > 0 and q[0] < s[0])
    last_from_stack = (handled == size-1) and (len(s) == 1)
    if move_from_queue and not last_from_stack:
      q_front = q[0]
      q = q[1:] + [q_front]
      msg = 'moved q[0]=%d to end, q=%r' % (q_front, q)
    else:
      (s_top, s) = (s[0], s[1:])
      q += [s_top]
      msg = 'popped s[0]=%d to end of q=%r,s=%r' % (s_top, q, s)
    handled += 1
    if debug:
      print 'Debug-Step %d: %s' % (handled, msg)
  return (q, s)

def test_sort(Q, S, debug=False):
  print 'Pre  Q: %r' % Q
  print 'Pre  S: %r' % S
  (Q, S) = sort(Q, S, debug)
  print 'Sorted: %r' % Q
  print

if __name__ == "__main__":
  test_sort([1, 3, 7, 9], [2, 5, 5])
  test_sort([1, 3, 7], [2, 5, 5])
  test_sort([1, 3, 7], [2, 5, 5, 9], True)
  test_sort([], [])
  test_sort([1], [])
  test_sort([], [1])

输出：

预问：[1, 3, 7, 9]
前 S: [2, 5, 5]
排序：[1, 2, 3, 5, 5, 7, 9]

预问： [1, 3, 7]
前 S: [2, 5, 5]
排序： [1, 2, 3, 5, 5, 7]

预问： [1, 3, 7]
前 S: [2, 5, 5, 9]
调试步骤 1：将 q[0]=1 移至结束，q=[3, 7, 1]
调试步骤 2：将 s[0]=2 弹出到 q=[3, 7, 1, 2],s=[5, 5, 9] 的末尾
调试步骤 3：将 q[0]=3 移至结束，q=[7, 1, 2, 3]
调试步骤 4：将 s[0]=5 弹出到 q=[7, 1, 2, 3, 5],s=[5, 9] 的末尾
调试步骤 5：将 s[0]=5 弹出到 q=[7, 1, 2, 3, 5, 5],s=[9] 的末尾
调试步骤 6：将 q[0]=7 移至结束，q=[1, 2, 3, 5, 5, 7]
调试步骤 7：将 s[0]=9 弹出到 q=[1, 2, 3, 5, 5, 7, 9],s=[] 的末尾
排序：[1, 2, 3, 5, 5, 7, 9]

预问：[]
预S：[]
排序：[]

预问：[1]
预S：[]
排序：[1]

预问：[]
前 S: [1]
排序：[1]