是否可以使用 4 个队列来实现 n 个堆栈？

Question

我知道如何使用一个或两个队列来实现堆栈，但是仅使用 4 个队列实现 n 个堆栈怎么样？有可能吗？如果是，请解释一下算法吗？谢谢。

Answer 1

是的。

假设您可以从 2 个队列实现堆栈（如您的问题所述），“4 个队列”现在只是噪音，如果您可以使用 2 个堆栈实现 n 个堆栈，那么您的问题的答案是肯定的。

这可以通过不仅将元素推送到堆栈，还可以将堆栈的 ID 推送到堆栈来完成。弹出时，将元素推入另一个堆栈，直到从所需堆栈中找到元素，然后 return 将它们返回。

这可能会被优化以避免一遍又一遍地向后推，但我相信最坏情况的复杂性仍然与元素数量成线性关系。

这是一个（非常未优化的）伪代码。

Pop(stack_number):
  element = null
  while not head_stack.empty():
    if head_stack.peek()[0] == stack_number:
      element = head_stack.pop()
      break
    else:
      other_stack.push(head_stack.pop())
  while not other_stack.empty():
    head_stack.push(other_stack.pop())
  return element

Push(stack_number, element):
  head_stack.push({stack_number, element})

是否可以使用 4 个队列来实现 n 个堆栈？

Is it possible to implement n stacks using 4 queues?

queue

stack

data-structures