Stack permutations

Question

Please  solve this question

Q   Assume stack A has the entries p, q and r (with p on top and r on bottom). Initially stack B is empty. An entry popped out of stack A can be printed immediately or pushed to stack B. A entry popped out of stack B can only be printed.
The least number of stack permutations of input sequence that start with a particular letter

Comments

Yes, 5 is the correct Answer

---

what is exact meaning of this statement: "The least number of stack permutations of the input sequence that start with a particular letter"??

---

@Hira Thakur I thought it means that the least number of permutations that are possible when the 1st element is fixed. So if p is fixed possible permutations are 2, I.e. pqr and prq. If q is taken as first element then also 2 permutations are possible, namely QRP and QPR. Now when r is fixed as the first element, only 1 permutation rqp is possible. So I thought answer is 1.

Answer 1

As in above question stack A has either print element or push on it B. the stack B has must print the element;

The element is respectively p,q,r so total 8 combinations are possible such as:

POSSIBLE WAYS TO ARRANGE P,Q,R

1	P	Q	R
2	P	R	Q
3	Q	P	R
4	Q	R	Q
5	R	P	Q
6	R	Q	P

first choice p,q,r: print p,q,r from stack A get pqr as output.

second choice p,r,q: print p from stack A, pop q and push it on stack B, print r and then print q from B getting p,r,q as output.

third choice q,p,r: pop p  from stack A and push to stack B.print q, then print p and last print r.

fourth choice q,r,p: pop p from stack A and push to stack B. print q then r and last print p.

fifth choice r,p,q: pop p,q and push it to stack b. print r but in stack B q is the topmost element but we required p as output so this combination is not possible.

sixth choice r,q,p: pop p,q form stack A and push it to B. print r then print topmost element of B that is q,p respectively.

so out of sixth combination 5 are valid and only one combination (r,p,q) is not valid.

Comments

Here, the answer should be 1 i.e. the case corresponding to r,q,p. If we fixed the letter r then we get only 1 possible permutation. For others, we get 2 combinations.