UGC NET CSE | December 2012 | Part 3 | Question: 17

Question

Which of the following permutations can be obtained in the output using a stack of size 3 elements assuming that input, sequence is 1, 2, 3, 4, 5?

• A. 3, 2, 1, 5, 4
• B. 5, 4, 3, 2, 1
• C. 3, 4, 5, 2, 1
• D. 3, 4, 5, 1, 2

Answer 1

A.

Operation	Push(1)	Push(2)	Push(3)	Pop	Pop	Pop	Push(4)	Push(5)	Pop	Pop
			3
		2	2	2				5
	1	1	1	1	1		4	4	4
Output				3	32	321	321	321	3215	32154

C.

Operation	Push(1)	Push(2)	Push(3)	Pop	Push(4)	Pop	Push(5)	Pop	Pop	Pop
			3		4		5
		2	2	2	2	2	2	2
	1	1	1	1	1	1	1	1	1
Output				3	3	34	34	345	3452	34521

 

Both Option(A) and (C) satisfied here.

Answer 2

A and C are valid...

Just insert the elements into the stack as per given order...here order is given 1,2,3,4,5...

So if input contains any order which doesn't follow this is invalid...

 

For D..

insert 1,2,3 into the stack now top symbol is similar to the  input symbol just pop it...

After popping 3 top of the stack is 2 not matched with remaining first input symbol...

So insert 4 into stack..Now matched pop it...

Same way insert 5 and pop it...

Now the I input symbol is 1 but top of the stack is 2...so this sequence is not followed

For B...

1,2,3 ,4,5  we need to insert but our stack size is 3 so not possible...

For A..

Push 1,2,3 now top matches so pop 3,2,1...

Push 4,5 top matches with input so pop 5,4

For C..

push 1,2,3, top match with input 3 so pop it...

Now push 4 , top matches with input so pop 4

Now push 5, top matches with input so pop 5,2,1

Comments

How (B) is possible?

---

Simply insert all from 1 to 5 and then top of stack and input matches so remove it...

---

how you can insert 5 elements? Given stack size is 3 here.

---

Sorry ... Mistake in reading... I'll update...