Can such an operation be done with two stacks?

Question

Assume a Forth-like environment with two stacks, a main one and an auxiliary one. The following operations can be done on the main stack: DUP (duplicate the top element), SWAP (swap the top two elements), DROP (drop the top value), PUSH (move the top value to the auxiliary stack) and PULL (move the top value of the auxiliary stack to the primary one).

If the main stack is organized like this (top-bottom): x <x elements> y <y elements> z <z elements>, where x, y and z are integers preceding the corresponding number of arbitrary elements, is it possible to re-arrange it like this: x <x elements> z <z elements> y <y elements> using only the operations described above?

If not, what operations can be added to satisfy this condition?

Answer 1

You do not need more operations. In fact, you do not need DUP and DROP, either. All you need are SWAP, PUSH and PULL.

The list of states of main stack below shows how the initial state 1 a 3 p q r 2 x y is changed to 1 a 2 x y 3 p q r. The auxiliary stack is at left hand side growing to the right from its bottom at the very left. The main stack is at right hand side growing to the left from it bottom at the very right. <- means PUSHing to the auxiliary stack and -> mean PULLing from the auxiliary stack.

   <- 1 a 3 p q r 2 x y  //initial state
 1  <-  a 3 p q r 2 x y
 1 a  <-  3 p q r 2 x y
 1 a 3  <-  p q r 2 x y
 1 a 3 p  <-  q r 2 x y
 1 a 3 p q      r 2 x y  //then SWAP
 1 a 3 p q  ->  2 r x y
 1 a 3 p      q 2 r x y  //then SWAP
 1 a 3 p  ->  2 q r x y
 1 a 3      p 2 q r x y  //then SWAP
 1 a 3  ->  2 p q r x y
 1 a      3 2 p q r x y  //then SWAP
 1 a  <-  2 3 p q r x y
 1 a 2  <-  3 p q r x y
 1 a 2 3  <-  p q r x y
 1 a 2 3 p  <-  q r x y
 1 a 2 3 p q      r x y  //then SWAP
 1 a 2 3 p q  ->  x r y
 1 a 2 3 p      q x r y  //then SWAP
 1 a 2 3 p  ->  x q r y
 1 a 2 3      p x q r y  //then SWAP
 1 a 2 3  ->  x p q r y
 1 a 2      3 x p q r y  //then SWAP
 1 a 2  <-  x 3 p q r y
 1 a 2 x  <-  3 p q r y
 1 a 2 x 3  <-  p q r y
 1 a 2 x 3 p  <-  q r y
 1 a 2 x 3 p q      r y  //then SWAP
 1 a 2 x 3 p q  ->  y r
 1 a 2 x 3 p      q y r  //then SWAP
 1 a 2 x 3 p  ->  y q r
 1 a 2 x 3      p y q r  //then SWAP
 1 a 2 x 3  ->  y p q r
 1 a 2 x      3 y p q r  //then SWAP
 1 a 2 x  ->  y 3 p q r
 1 a 2  ->  x y 3 p q r
 1 a  ->  2 x y 3 p q r
 1  ->  a 2 x y 3 p q r
      1 a 2 x y 3 p q r  //final state

Once you have checked the above procedure, you will understand how to proceed in the general situations. In fact, what have been shown above is, basically, the well-known fact that if you can swap any two adjacent elements in an array, you can sort all elements in the array into any permutation you wanted.