GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
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
asked in DS by Veteran (56.6k points)  
retagged by | 670 views
is the answer d?

2 Answers

+6 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.

answered by Veteran (11k points)  
selected by
+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

answered by Loyal (4.4k points)  
edited by
Can you please elaborate?

Thanks.:-)
What part exactly is being difficult for you?


Top Users Aug 2017
  1. Bikram

    5034 Points

  2. ABKUNDAN

    4730 Points

  3. akash.dinkar12

    3488 Points

  4. manu00x

    3296 Points

  5. rahul sharma 5

    3178 Points

  6. makhdoom ghaya

    2530 Points

  7. just_bhavana

    2428 Points

  8. stblue

    2160 Points

  9. Tesla!

    2076 Points

  10. joshi_nitish

    1830 Points


25,032 questions
32,178 answers
74,989 comments
30,215 users