GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
1.1k 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 (65.2k points) 35 224 637
retagged by | 1.1k views
is the answer d?

2 Answers

+7 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 (11.6k points) 6 20 88
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 Boss (5.4k points) 3 13 44
edited by
Can you please elaborate?

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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23678 Points

  2. Bikram

    17278 Points

  3. Habibkhan

    8962 Points

  4. srestha

    6460 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5128 Points

  7. Sachin Mittal 1

    4892 Points

  8. joshi_nitish

    4486 Points

  9. sushmita

    4052 Points

  10. Rishi yadav

    3974 Points


Recent Badges

Famous Question makhdoom ghaya
Notable Question PriDix
Popular Question ManojK
Reader Chandramani Adil
Regular qwerty007
Notable Question rishu_darkshadow
Popular Question Rishi yadav
Popular Question makhdoom ghaya
Nice Comment Pratyush Madhukar
Popular Question suvasish pal
27,417 questions
35,262 answers
84,531 comments
33,497 users