Previously Asked GATE Questions on Stack

Question 1:

The end of a stack, traditionally known as the position where PUSH and POP operations performed, is known as:

1. FIFO
2. LIFO
3. FRONT
4. TOP

Answer: Option 4 : TOP
Explanation:The top of the stack refers to the end of the stack where operations are performed. This is where elements are added (pushed) and removed (popped). When an element is added to an empty stack, it becomes the top element. When additional elements are pushed onto the stack, they become the new top elements.

Question 2:

What is the equivalent infix expression of the following postfix expression?

M, N, O, +, *, P, /, Q, R, S, T, /, +, *, –

1. N*(M+Q)/Q-P*(S+R/T)
2. (((M*(N+O))/P)-(Q*(R+(S/T))))
3. O * (M + N)/P – Q * (R + S/T)
4. M * (N + O)/Q – P * (R/S + T)

Answer: Option 2 : (((M * (N + O)) / P) – (Q * (R + (S / T))))
Explanation:

Let’s apply this algorithm to the given postfix expression – M, N, O, +, *, P, /, Q, R, S, T, /, +, *, –

Step 1 – Push M, N, O onto the stack Stack – O, N, M

Step 2 – Pop O, N, M and concatenate them with + and * Stack – (M*(N+O))

Step 3 – Push P onto the stack Stack – P, (M*(N+O))

Step 4 – Pop P and concatenate it with / Stack – ((M*(N+O))/P)

Step 5 – Push Q, R, S, T onto the stack Stack – T, S, R, Q, ((M*(N+O))/P)

Step 6 – Pop T, S, R, Q and concatenate them with / and + and * Stack – ((Q*(R+(S/T))), ((M*(N+O))/P)

Step 7 – Pop the final expression from the stack after “-” Infix expression – (((M*(N+O))/P) – ((Q*(R+(S/T))))

Question 3:

What is the postfix representation of the following infix expression?

(A + B) * C – D * E / F

1. A B + C * D E * F – /
2. A B * C + D E * F / –
3. A B + C – D E * F / *
4. A B + C * D E * F / –

Answer: Option 4 : A B + C * D E * F / –
Explanation:

() has highest precedence

* and / has same precedence while + and – has same precedence

(* and /) and higher precedence than (+, -)

Associativity is left to right:

(A + B) * C – D * E / F

A B + * C – D * E / F

A B + C * – D * E / F

A B + C * – D E * / F

A B + C * – D E * F /

A B + C * D E * F / –

Question 4:

The result evaluating the postfix expression 10 5 + 60 6 / * 8 − is

1. 284
2. 213
3. 142
4. 71

Answer: Option 3 : 142

Question 5:

The five items P,Q,R,S and T are pushed in a stack, one after the other starting from P. The stack is popped four times and each element is inserted in a queue. Then two elements are deleted from the queue and pushed back on the stack. now one item is popped from the stack. The popped item is:  

1. P
2. R
3. Q
4. S

Answer: Option 4 : S

Question 6:

Consider the following postfix expression with single digit operands:

6 2 3 * / 4 2 * + 6 8 * –

The top two elements of the stack after second * is evaluated, are:

1. 6, 3
2. 8, 1
3. 8, 2
4. 6, 2

Answer: Option 2 : 8, 1

Question 7:

What is the outcome of the prefix expression +, -, *, 3, 2, /, 8, 4, 1?

1. 12
2. 5
3. 11
4. 4

Answer: Option 2 : 5

Question 8:

A stack is implemented with an array of ‘A [0..N – 1]’ and a variable ‘pos’. The push and pop operations are defined by the following code.

push(x)
                A[pos] ← x
                pos ← pos – 1
end push
pop( )
                pos ← pos + 1
                return A[pos]
end pop

Which of the following will initialize an empty stack with capacity N for the above implementation?

1. pos ← -1
2. pos ← 0
3. pos ← 1
4. pos ← N – 1

Answer: Option 4 : pos ← N – 1

Question 9:

A stack can be implemented using queue, but then we need to use atleast:

1. 3 queues
2. 2 queues
3. only one queue is sufficient
4. none of the options

Answer: Option 2 : 2 queues

Question 10:

Which of the following applications may use a stack?

(a) Parenthesis balancing program

(b) Process scheduling operating system

(c) Conversion of infix arithmetic expression to postfix form

• (a) and (b)
• (b) and (c)
• (a) and (c)
• (a), (b) and (c)

Answer: Option 3 : (a) and (c)

Stacks, a fundamental data structure in computer science, are crucial for understanding algorithmic paradigms and solving complex computational problems. As candidates gear up for the GATE Exam 2024, a solid grasp of stack concepts is indispensable. These notes are designed to provide a concise yet comprehensive overview of stacks, covering key topics that are likely to be assessed in the GATE examination.