GATE CS 1994 Q1.14 — Arrays, Stacks and Queues

A permutation can be obtained using a stack if and only if we can simulate the sequence of push and pop operations without violating the Last-In, First-Out (LIFO) property.

Let's trace the operations for the correct option and see why the others fail.

Analyzing Option B: 3, 4, 5, 2, 1

We can obtain this permutation using the following sequence of operations:

1. Push 1, Push 2, Push 3 (Stack: [1, 2, 3])
2. Pop 3 → Output: 3 (Stack: [1, 2])
3. Push 4 (Stack: [1, 2, 4])
4. Pop 4 → Output: 3, 4 (Stack: [1, 2])
5. Push 5 (Stack: [1, 2, 5])
6. Pop 5 → Output: 3, 4, 5 (Stack: [1, 2])
7. Pop 2 → Output: 3, 4, 5, 2 (Stack: [1])
8. Pop 1 → Output: 3, 4, 5, 2, 1 (Stack: [])

Since all operations are valid, Option B is achievable.

Why other options are invalid:

• Option A (3, 4, 5, 1, 2): To output 3, 4, and 5, elements 1 and 2 must remain in the stack with 2 on top of 1 (Stack: [1, 2]). Thus, 2 must be popped before 1. We cannot pop 1 before 2.
• Option C (1, 5, 2, 3, 4): To output 1, we push and pop 1. To output 5 next, we must push 2, 3, 4, 5 (Stack: [2, 3, 4, 5]) and pop 5. The stack is now [2, 3, 4]. The next element popped must be 4, so we cannot output 2 next.
• Option D (5, 4, 3, 1, 2): To output 5, 4, 3, we push 1, 2, 3, 4, 5 and pop 5, 4, 3. The stack is now [1, 2]. The next element popped must be 2, so we cannot output 1 next.