algorithm - 使用队列实现栈——最好的复杂度

Question

我想知道是否有一种方法可以根据需要使用尽可能多的队列来实现堆栈，从而在 O(1) 中推送和弹出数据。如果没有任何 O(1) 算法，那么最好的复杂度是多少？

Answer 1

如果允许在队列中递归定义队列，则可以使用以下 O(1) 次推送/弹出:

代码:

STACK:
  QUEUE q

PUSH (S, x):
  QUEUE temp
  ENQUEUE(temp, x)
  ENQUEUE(temp, S.q)
  S.q = temp


POP (S):
  ANY x := DEQUEUE(S.q) # Error here if queue is empty
  QUEUE S.q := DEQUEUE(S.q)
  return x

结果是递归形成的堆栈。

如果 [1,2] 表示一个堆栈，其中 dequeue([1,2]) 将返回 1。那么如果 1 然后 3 然后 6 被压入堆栈的数据结构将如下所示:

[6,[3,[1,[]]]]