算法来复制一个堆栈 [英] algorithm to copy a stack

问题描述

是否有可能堆栈复制到另一个在C中不使用任何外部堆栈或数组？

Is it possible to copy a stack onto another in C without using any external stack or array?

我知道，它可以使用递归来完成，但是否还有其他可能的解决方案提到限制范围内做到这一点？

I know that it can be done using recursion, but are there any other possible solution to do this within mentioned constraints?

推荐答案

是的，这是可能的，但它是要采取 O（N ^ 2）。考虑栈取值（源）和 T （目标）。

Yes, it is possible, but it is going to take O(N^2). Consider stacks S (source) and T (target).

1. 的init 计数零
2. 在弹出的顶级元素电子从堆栈取值，然后将剩余的数据推入堆栈 T ，留下计数堆栈项取值
3. 按电子在取值
顶
4. 复制元素回程从 T 到取值
5. 增量计数
6. 如果计数不等于对取值的项目数，请回到步骤1
7. 在弹出取值的元素和推入 T

1. init count to zero
2. pop the top element E off the stack S, then push the remaining data onto stack T, leaving count items on stack S
3. push E on top of S
4. Copy elements back from T to S
5. increment count
6. If count is not equal the number of items on S, go back to step 1
7. pop elements of S and push onto T

步骤0至到位5反向堆栈取值;第6步移动它交给 T ，扭转了订单和生产的原件及复印件。这是一个破坏性的拷贝，但因为原来的堆栈现在是空的。

Steps 0 through 5 reverse stack S in place; step 6 moves it over to T, reversing the order and producing a copy of the original. It's a destructive copy, though, because the original stack is now empty.

这篇关于算法来复制一个堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！