Question

A program attempts to generate as many permutations as possible of the string 'xyzw' by pushnig the characters x, y, z, w in the same order onto a stack, but it may pop off the top charaacter at any time. Which on of the following strings CANNOT be generated using this program?

• A. zyxw
• B. zxyw
• C. xyzw
• D. wzyx

Answer 1

The correct option is B zxyw

For option (a): Push x, pop x, push y, pop y, push z, pop z, push w, pop w.

For ption (b): Push all of x, y, z, w first and then pop them at once.

For option (c): Push x, y, z now pop all of these and now push w and pop w at the very next moment.

But option (d) is clearly not possible because first x, y, z is pushed; then once z is popped, y has to be at the top of stack and so x cannot come in the output before y in a situation like this because pushing has to be done in the oder aready specified in the question.

So option (d) is not possible.