GATE CSE 1994 | Question: 1.14

Question

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 $\text{1, 2, 3, 4, 5}$ in that order?

• A. $\text{3, 4, 5, 1, 2}$
• B. $\text{3, 4, 5, 2, 1}$
• C. $\text{1, 5, 2, 3, 4}$
• D. $\text{5, 4, 3, 1, 2}$

Comments

Similar concept : 

https://gateoverflow.in/3695/gate-it-2004-question-52

Answer 1

Push $1$ push $2$ push $3$ pop $3$ push $4$ pop $4$ push $5$ pop $5$ pop $2$ pop $1$ then o/p is $3,4,5,2,1$

So, option is B.

Comments

can any one tell me why did we used only 3 boxes in the stack to implement this particular problem?

---

you can see any  stack size, that is not an issue here. these questions the easier method is just try out each option and see whether it is valid. for example take option A.

3, 4, 5, 1, 2

it is given in question push is in order 1 2 3 4 5.

in the op 3 is coming first. so it means 1 2 3 are pushed (3 elements in stack)

now pop 3. stack becomes 1 2

then next o/p is 4 . we need to push 4, then only it  can be popped

now stack 1 2 4

now pop 4

next is 5 similar manner push and pop 5

now stack becomes 1 2 and 2 being on top

in the option next is 1. so it is not possible, because next pop can give only 2

in every step it have max 3 elements in the stack. there is nothing magical in the number 3 used here. you can do the same operations with stack of other size. if you have confusion just draw with               stack size 5. no problems

---

@jothee

@Sankaranarayanan P.N

how such sequence possible then what should be answer ? for n input 

Answer 2

How to do this within second @ GATE.

Conclusion after long analysis...

Algo..(if values are in increasing order then no problem..but when decrease.. Plz see the range of values between consecutive increased and decrease no. and verify that range of values must appear in ur current state of  input sequence if not then it is invalid sequence.)

A.

3,4,5(increase order no problem)

1(decreased)

Now check range of values between 1 to 5( I.e.2,3,4) but 2 not came till now...So invalid sequence.

C. 1,5(Increase order no problem),2(decreased)

See range between 2-5 (means 3,4) which are not came in sequence till now so invalid sequence.

D.5,4(decreased) but there is no value in-between of (4-5)

Now 3 came(decreased) but no Value between 3-4 so ok

Now 1 came ...between 1-3 there is 2 but Still 2 not came in sequence so invalid.

B. 3,4,5,(increased order),2(decreased)

Between 2-5 (3,4)which Already came in sequence so no problem.

Now 1(decreased) .between 1-2 no value is there.. So this is correct sequence.

So option B is Ans.

Once U practice this U can identify Correct sequence within seconds.

PS:--Concepts make shortcut... Not vice versa.. So practice with concept too

Comments

@ Rajesh Pradhan

very nice... :) 

---

how did you reach this conclusion?

---

Really great trick @Rajesh Pradhan Sir

---

the reason i visit go even on questions i am able to do 

TY @Rajesh Pradhan sir

Answer 3

hope this helps :)

Comments

great explanation

---

great work dude !! How did you make this ??

Answer 4

1,2,3,4,5 in this given sequence 1 is pushed in as 1st element or in other word we can say 1 is the last element of the stack which was popped out in output so check in given options which option have last pop as 1 option (B) 3,4,5,2,1 have last element so option B is answer 

Comments

Very Nice..give me some more tricks like this

Answer 5

Push 1

Push 2

Push 3

Pop 3. (3)

Push 4

Pop 4. (4)

Push 5

Pop 5. (5)

Pop 2. (2)

Pop 1 .(1)

Soo the order is 3,4,5,2,1

Answer 6

we can do it inspection very easily,how it can be efficiently using programming ?