Question

Letters are pushed on a stack in order: R A N D O M O P S. Specify where to insert pop operations (shown by ‘*’) among the pushes of the given letters, in order to produce the output: ADONOMSPR . You can only do this process once. That is, you cannot take the output produced and then pass it again through the stack.

Answer 1

Pop() operation should be performed after the insetion of 'R' in the sequence.

i.e.

Initially Stack is empty, after that steps are as follows:

Step 1 : Push R Stack : R     Remaining elements : A N D O M O P S

Step 2 : Pop R Stack : 'Empty'    Remaining elements : A N D O M O P S R

Step 3 : Push A Stack : A Remaining elements : N D O M O P S R

Step 4 : Push N Stack : A N   Remaining elements : D O M O P S R

Step 5 : Push D Stack : A N D Remaining elements : O M O P S R

Step 6 : Push O Stack : A N D O Remaining elements : M O P S R

Step 7 : Push M Stack : A N D O M    Remaining elements : O P S R

Step 8 : Push O Stack : A N D O M O    Remaining elements : P S R

Step 9 : Push P Stack : A N D O M O P Remaining elements : S R

Step 10 : Push S Stack : A N D O M O P S Remaining elements : R

Step 11 : Push S Stack : A N D O M O P S R Remaining elements : 'Empty'

-----------------------------------

Explanation : Here we need to apply Pop Operation after the first Push operation and then R will pop out and go down to the end of the list of remaining elements and then push regularly to get the desired output.