Concatenate two stacks (one stack on top of another)

Question

I understand how to do this with a loop S1 and S2 (in pseudocode)

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

How would you do this without a loop (big O constant)? With queues it is easy as all you have to do is move the rear pointer of q1 to the front of q2 and link them.

C like pseudocode would be great! Thank you very much.

Answer 1

Implement the stacks internally as linked lists and hang on to pointers to the top and bottom elements of the stack. Then the operation of concatenating the stacks is just the same as splicing two linked lists together, which is O(1).