recategorized by
33,091 views
33 votes
33 votes

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?

  1. $\text{3, 4, 5, 1, 2}$
  2. $\text{3, 4, 5, 2, 1}$
  3. $\text{1, 5, 2, 3, 4}$
  4. $\text{5, 4, 3, 1, 2}$
recategorized by

6 Answers

Best answer
45 votes
45 votes

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.

23 votes
23 votes
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
14 votes
14 votes

hope this helps :)

6 votes
6 votes

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 

Answer:

Related questions

35 votes
35 votes
4 answers
2
Kathleen asked Oct 4, 2014
22,917 views
Linked lists are not suitable data structures for which one of the following problems?Insertion sortBinary searchRadix sortPolynomial manipulation
29 votes
29 votes
6 answers
4
Kathleen asked Oct 5, 2014
4,887 views
An array $A$ contains $n$ integers in non-decreasing order, $A \leq A \leq \cdots \leq A[n]$. Describe, using Pascal like pseudo code, a linear time algorithm to find $...