670 views
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
retagged | 670 views

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

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