in DS
229 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
in DS
by
229 views

1 comment

Why Option B can't be the answer?

4, 3, 1, 2

1)  Push(4) , Push(3), Push(1)  [4 is at bottom and 1 is at the top]

2)  Pop(1)    $1$

3)  Push(4) , Push(3), Push(2)

4)  Pop(2)    $2$

5)  Pop(3)    $3$

5)  Pop(4)    $4$

So the obtained sequence is 1, 2, 3, 4.

This is my approach. Please someone verify it
0
0

2 Answers

2 votes
2 votes
Best answer
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