c - 复制堆栈的算法

Question

是否可以在不使用任何外部堆栈或数组的情况下将堆栈复制到 C 中的另一个堆栈？

我知道它可以使用递归来完成，但是在提到的约束范围内还有其他可能的解决方案吗？

Answer 1

是的，这是可能的，但需要O(N^2). 考虑堆栈S（源）和T（目标）。

1. 初始化count为零
2. E从堆栈中弹出顶部元素S，然后将剩余数据压入堆栈T，将count项目留在堆栈上S
3. 压E在上面S
4. 将元素复制T回S
5. 增量count
6. 如果 count 不等于 on 的项目数S，则返回步骤 1
7. 弹出元素S并推到T

步骤 0 到 5 反向堆叠S到位；第 6 步将其移至T，颠倒顺序并生成原件的副本。不过，这是一个破坏性的副本，因为原始堆栈现在是空的。

Answer 2

它不是很有效，但是是的，它是可行的。

Stack S = source, Stack T = target, int size = number of elements;
while(size >0 ) {
  pop size-1 elements from S (all but last), pushing them onto T (using it as temp storage)
  pop and copy the last element from S; push it back onto S;
  pop and push size-1 elements on T back to S.
  push your copy  of the last element onto T
  decrement size;
}

引用 ugoren，这类似于“河内有 2 个钉子，加上恒定数量的 1 盘存储空间”的塔

Answer 3

好的，我将展示我自己的可视化和从一个堆栈到另一个堆栈的真正无损复制的解决方案。

所以我们有一对堆栈S和T，我们可以想象它们像这样相互接近：

    ____________        _______________
    |                                  |
S   | S0 S1 S2   ........     T2 T1 T0 | T
    |____________       _______________| 

如果我们将整个数据结构视为单个序列(S0, S1, S2, ...., T2, T1, T0)，我们可以执行将特定元素从一个位置移动或复制到另一个i位置的动作j。我们如何做到这一点？我们可以像这样分小步完成这个序列：

void MoveLeft()
{
    T.push( S.pop() );
    curPosition--;
}

void MoveRight()
{
    S.push( T.pop() );
    curPosition++;
}

然后我们可以访问任何元素，记住它，然后移动到任何其他位置并将该元素放在那里。这是辅助函数：

void MoveToI(int i)
{
    while( curPosition > i ) {
        MoveLeft();
    }

    while( curPosition < i ) {
        MoveRight();
    }
}

因此，使用这些操作，我们基本上将序列转换(S0,S1,S2,...,SN)为(S0,S1,S2,...,SN,SN,SN-1,...,S2,S1,S0).

这是算法：

curPosition = NElements;
for( int i = 0; i < NElements; ++i ) {
    MoveToI( i );
    x = T.peek();
    MoveToI(Nelements);
    T.push( x );
}

MoveToI( Nelements );

Answer 4

这是一个 O(N) 操作，因为堆栈是一个已知开始和结束的连续区域，可以是memlcpy()或memcpy_s()从一个进程到共享内存或通过 IPC 发送。理想情况下，如果这是一些进程重播或实时迁移代码，请在执行任何操作之前检查数据结构和 ABI 是否足够接近。另外，复制堆。然后，诀窍是在某处设置一个魔术变量，以指示一个进程应该等待准备运行，而另一个应该关闭。文件句柄、互斥体、信号量和其他内核模式状态也需要复制。a) 使用更便宜fork()它为您完成所有这些工作，或者 b) 有一个可检查点的反应器（堆栈、堆和外部资源），它可以“停止世界”暂停所有线程并在子进程中重新启动它们，然后再杀死它。我会 fork() + exec() 并复制堆栈和堆。可能需要一个辅助入口指针补丁表（两个指针的数组：旧指针 -> 新指针），它必须修补代码、堆栈、堆、常量表，以免崩溃。