in DS retagged by
7,531 views
4 votes
4 votes
Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence 5, 7, 8, 4, 6 in that order?

a)6, 8, 4, 7, 5

b)6, 4, 5, 7, 8

c)6, 4, 7, 8, 5

d)7, 8, 4, 6, 5
in DS retagged by
by
7.5k views

1 comment

is the answer d?
0
0

2 Answers

9 votes
9 votes
Best answer

Stack returns only top most element in it

Input Sequence is 5,7,8,4,6.

Check one by one options.

I)Given o/p permutation is 6,8,4,7,5.

Push elements into stack and stack becomes

 when perform pop operation O/P permutation is 6,4,8,7,5. so not correct.

II)2nd option is 6,4,5,7,8.

5 is poped out after poping 8 and 7.so not correct.

III)3rd option is 6,4,7,8,5.

7 is poped out after poping 8 only.so not correct.

IV)4th option is 7,8,4,6,5.

First push 5 and 7 and pop 7. //stack contains only one element i.e)5.

Next push 8 and pop 8.//again stack contains only one element i.e)5.

Next push 4 and pop 4.

Next push 6 and pop 6.

Finally pop 5.

Hence option D satisfies stack O/P permutation.

selected by

3 Comments

how you actually pushing the elements into stack? is this having any algo?? plz tell and where did you studied this topic in DS.
0
0

@srestha

How many such permutation is possible if Input size is n??

0
0

For No of permutation we can relate this problem to proper bracket sequences problem.

So, No of permutation is Nth Catalan number.

This link is worth reading

 https://math.stackexchange.com/questions/1431923/how-many-sequences-possible-in-stack-if-the-input1-2-3-n-is-in-order

 

3
3
2 votes
2 votes

Answer is D. 

Push $5$ & $7$; Pop 1 time: ​​​​​​Output: 7.

Push $8$; Pop 1 time: Output: 8.

Push $4$; Pop 1 time: Output: 4.

Push $6$; Pop 2 time: Output: 6,5.

Output sequence: 7,8,4,6,5

edited by

3 Comments

Can you please elaborate?

Thanks.:-)
0
0
What part exactly is being difficult for you?
0
0
how pushing and poping going on ? any algo involved?
0
0