GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
59 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 (49.8k points)   | 59 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.2k 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 (3k points)  
edited by

Related questions

+5 votes
1 answer
1
asked in DS by Rahul Jain25 Loyal (4.7k points)   | 119 views
+2 votes
2 answers
3
Top Users Jan 2017
  1. Debashish Deka

    9008 Points

  2. sudsho

    5326 Points

  3. Habibkhan

    4798 Points

  4. Bikram

    4676 Points

  5. Vijay Thakur

    4496 Points

  6. Arjun

    4244 Points

  7. saurabh rai

    4222 Points

  8. Sushant Gokhale

    3834 Points

  9. santhoshdevulapally

    3808 Points

  10. Kapil

    3752 Points

Monthly Topper: Rs. 500 gift card

19,239 questions
24,127 answers
53,274 comments
20,327 users