GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
244 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 (53.1k points)   | 244 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.7k 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 Apr 2017
  1. akash.dinkar12

    3826 Points

  2. Divya Bharti

    2798 Points

  3. Deepthi_ts

    2294 Points

  4. rude

    2142 Points

  5. Prashant.

    1900 Points

  6. Tesla!

    1888 Points

  7. Kapil

    1842 Points

  8. Debashish Deka

    1830 Points

  9. Arjun

    1810 Points

  10. Sanjay Sharma

    1712 Points

Monthly Topper: Rs. 500 gift card

22,177 questions
28,200 answers
63,649 comments
24,364 users