连接两个堆栈(一个堆栈在另一个堆栈之上)

Question

我了解如何使用循环 S1 和 S2 执行此操作(伪代码)

Loop (NOT emptyStack(S2))
     pop(S2, dataptr)
     push (temp, dataptr)
end loop 
Loop (NOT emptyStack(temp))
     pop (temp dataptr)
     push(S1, dataptr)
end loop 

如果没有循环(大 O 常量)，您将如何做到这一点？使用队列很容易，因为您所要做的就是将 q1 的后指针移动到 q2 的前面并将它们链接起来。

像伪代码这样的 C 会很棒!非常感谢。

Answer 1

在内部将堆栈实现为链表，并保留指向堆栈顶部和底部元素的指针。那么拼接栈的操作就和将两个链表拼接在一起一样，都是O(1)。