retagged by
482 views
0 votes
0 votes

Which of the following permutation can be obtained in the output (in the same order) using a stack assuming that the input is the sequence $1, 2, 3, 4$ in that order?

  1. 3, 4, 1, 2
  2. 4, 3, 1, 2
  3. 1, 2, 3, 4
  4. none
retagged by

2 Answers

Best answer
3 votes
3 votes
very simple approach push(1),pop(1),push (2), pop (2), push(3), pop(3),push(4),pop(4).
o/p= 1,2,3,4
selected by
2 votes
2 votes
for a valid stack permutation, check the options. if they are in increasing order then so far so good. if we encounter a lower valued number, it should be the most recently used one sequentially.

option a :- 3,4 (increase), 1  reject  (decrease, incorrect as it should;ve been 2 here then 1)

option b :- 4,3(decrease but ok as 3 immediately precedes 4,) 1 (reject as the no immediately preceding the seen nos should be 2 not 1)

option c:- increasing order, hence valid

similar valid permutations :- 4321 , all immediately preceding the previous when decreasing,  2314,  2341 etc.
Answer:

Related questions

2 votes
2 votes
2 answers
2
0 votes
0 votes
1 answer
4
Arjun asked Oct 10, 2016
404 views
The postfix expression for the infix expression$$A + B*C/D +E$$isAB+*CD/E+ABC*D/+E+AB+C*D/E+A+*BCD/E+