GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
155 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 (52.4k points)   | 155 views
is the answer d?

2 Answers

+2 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 (10.6k points)  
selected by
0 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 (3.2k points)  
edited by


Top Users Mar 2017
  1. rude

    4758 Points

  2. sh!va

    3014 Points

  3. Rahul Jain25

    2830 Points

  4. Kapil

    2636 Points

  5. Debashish Deka

    2442 Points

  6. 2018

    1514 Points

  7. Vignesh Sekar

    1416 Points

  8. Akriti sood

    1298 Points

  9. Bikram

    1286 Points

  10. Sanjay Sharma

    1076 Points

Monthly Topper: Rs. 500 gift card

21,470 questions
26,801 answers
61,040 comments
23,037 users