Объединить два стека (один стек поверх другого)

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).