[Solved]: Interleaving algorithm for 2 stacks

Problem Detail: 

Suppose I have two stacks $<a_1,a_2,...a_m>$ and $<b_1, b_2,...b_n>$ and a third stack of size $m+n$. I want to have the third stack in the following manner, $$<a_1,b_1,a_2,b_2,...a_n,b_n...a_m-1,a_m>$$ for $$m>n$$ This was easy to do if the two initial stacks were not size constrained. But if the two stacks are size constrained, I am in a fix.

Is it even possible to interleave the elements of the two stacks into a third stack in constant space? Also what would be the minimum number of moves to do this? I know using recursion this can be reduced to Tower of Hanoi variant, but what about a non-recursive algorithm?

Asked By : Adwait Kumar

Answered By : ZeroUltimax

Here's an algorithm that works without using recursion. I might say it's even easier to do without recursion.

I'll be working off the underlying assumption that you don't have access to temporary variables, and that the only available operation to you is $pop(s, d)$ which pop the top element of s(source) and places it on top of d(destination). E.g.: we have the stacks $A=<a_1,a_2,a_3>$ and $B=<>$. After calling $pop(A,B)$ we have $A=<a_1,a_2>$ and $B=<a_3>$.

First, I'll define a new function $popm(s,d,c)$. It's role is to iterate $pop(s,d)$ c times. E.g.: $A=<a_1,a_2,a_3>$ and $B=<>$. After calling $popm(A,B,3)$, $A=<>$ and $B=<a_3,a_2,a_>$.

Here is the proposed algorithm.

1. Start with $A=<a_1,a_2,\dots,a_m>$, $B=<b_1,b_2,\dots,b_n>$ and $C=<>$
2. $pop(B,C,n)$. $A=<a_1,a_2,\dots,a_m>$, $B=<b_1,b_2,\dots,b_n-1>$ and $C=<b_n>$ The goal is free a spot in $B$
3. $popm(A,C,m)$. $A=<>$, $B=<b_1,\dots,b_n-1>$ and $C=<b_n,a_m,\dots,a_2,a_1>$ You've exposed $a_1$ on top of $C$
4. $pop(C,B)$. $A=<>$, $B=<b_1,\dots,b_n-1,a_1>$ and $C=<b_n,a_m,\dots,a_2>$ Have $B$ hold the value $a_1$ on top
5. $popm(C,A,m-1)$. $A=<a_2,a_3,\dots,a_m>$, $B=<b_1,\dots,b_n-1,a_1>$ and $C=<b_n>$ Restore $A$ (excluding $a_1$) to it's original order. Also, have $A$ hold $b_n$ for now.
6. $pop(C,A)$. $A=<a_2,a_3,\dots,a_m,b_n>$, $B=<b_1,\dots,b_n-1,a_1>$and $C=<>$ Have $A$ hold $b_n$ for now.
7. $pop(B,C)$. $A=<a_2,a_3,\dots,a_m,b_n>$, $B=<b_1,\dots,b_n-1>$ and $C=<a_1>$ Put $a_1$ at the bottom of $C$, it's desired place.
8. $pop(A,B)$. $A=<a_2,a_3,\dots,a_m>$, $B=<b_1,\dots,b_n-1,b_n>$ and $C=<a_1>$. Restore $b_n$ to the top of B
9. Interchange $A$ and $B$ and repeat from step 1, adjusting for the new state of $A$, $B$ and $C$. You can ignore steps 2, 6 and 8 since you now will have a free spot on top of B from now on.
10. When $B$ has been emptied, $popm(A,B,m-n)$ then $popm(B,C,m-n)$ to have your remaining stack $A$ do a "double back flip" off $B$ onto $C$.

Let me say why this isn't related to tower of Hanoi. In the Hanoi problem, you cannot inverse the tower. Moreover, you have the middle peg as a temporary holder, which we don't have. Finally, in this example, you can reverse the order on the elements.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28980

3.2K people like this

 Download Related Notes/Documents