我想知道是否有一种方法可以根据需要使用尽可能多的队列来实现堆栈，从而在 O(1) 中推送和弹出数据。 如果没有任何 O(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,[]]]]
关于algorithm - 使用队列实现栈——最好的复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26643483/