algorithm to copy a stack

Question

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?

Answer 1

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

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

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.

Answer 2

It's not very efficient, but yes it's do-able.

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;
}

To quote ugoren, this is similar to the tower of "Hanoi with 2 pegs, plus a constant number of 1-disc storage spaces"

Answer 3

Ok, I'll present my own visualization and a solution for a true non-destructive copy from one stack to another.

So we have a pair of stacks S and T, we can imagine them growing towards each other like this:

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

If we consider the whole data structure as a single sequence (S0, S1, S2, ...., T2, T1, T0), we can perform actions of moving or copying a particular element from position i to position j. How do we do this? We can move through this sequence in small steps like this:

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

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

Then we can have access to any element, remember it, then move to any other position and put that element there. Here is the helper function:

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

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

So using these operations we basically transform the sequence (S0,S1,S2,...,SN) to (S0,S1,S2,...,SN,SN,SN-1,...,S2,S1,S0).

And here is the algorithm:

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

MoveToI( Nelements );