What are common examiner traps in Stacks?

Operand order reversal during non-commutative operations (computing op2 - op1 or op2 / op1 instead of op1 - op2 or op1 / op2). Overlooking auxiliary stack capacity overflow when attempting to access an element buried deep in the primary stack. Assuming a single global pointer can track the minimum element in O(1) without accounting for the O(n) search required when the minimum element is popped. Assuming auxiliary data structures like Min-Heaps or sorted arrays maintain O(1) stack operations, overlooking the O(log n) or O(n) degradation on push/pop.

GATE CSE Stacks PYQs

Standard yield2% of Programming and Data Structures

GATE tests Stacks across both classical execution mechanics (postfix evaluation and LIFO sequence tracing) and advanced data structure design (state-space simul… Read the guide

Take topic test

Questions: 3
Asked: since 2015
Total marks: 5
Marks / paper: 0.2

3 GATE CSE Stacks PYQs with solutions, from Programming and Data Structures. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Stacks

Concepts, patterns, formulas and traps distilled from past papers.

GATE tests Stacks across both classical execution mechanics (postfix evaluation and LIFO sequence tracing) and advanced data structure design (state-space simulation with capacity constraints and $O(1)$ stack augmentation). While earlier years focused on 1-mark algorithmic evaluations, recent years leverage 2-mark MSQs to test structural limits and asymptotic invariants.

Core concepts

LIFO (Last-In, First-Out) property
Postfix expression evaluation and operand order
Stack permutation feasibility and invalid permutation conditions
Bounded stack capacity and auxiliary buffering
Stack augmentation for O(1) auxiliary queries (e.g., Min-Stack)

Recurring question patterns

Postfix Expression Evaluation
OccasionalMCQ1 marks2015
Evaluate an arithmetic expression in postfix notation by processing tokens left-to-right, pushing operands to a stack, and popping two operands when an operator is encountered.
Bounded Multi-Stack Permutation and Simulation
OccasionalMSQ2 marks2024
Determine feasible output sequences generated from a stack configuration under specific transfer rules, pop/push constraints, and strict auxiliary stack capacity bounds.
Stack Augmentation and Operation Complexity
OccasionalMSQ2 marks2025
Analyze structural modifications to a standard stack (e.g., tracking minimum/maximum element) such that specialized queries run in $O(1)$ without increasing the asymptotic time complexity of standard PUSH and POP operations.

Formulas GATE uses

Postfix Binary Operation Evaluation

\text{result} = op_1 \ \odot \ op_2 \quad \text{where } op_2 = \text{pop}(), \ op_1 = \text{pop}()

Used when an operator is encountered while scanning a postfix expression from left to right.

Augmented Prefix-Minimum Invariant

\text{min\_below}(x) = \min(x.\text{key}, \text{min\_below}(\text{top}))

Used during a PUSH operation to maintain the minimum element pointer in $O(1)$ time.

Examiner traps in Stacks

Operand order reversal during non-commutative operations (computing op2 - op1 or op2 / op1 instead of op1 - op2 or op1 / op2).
Overlooking auxiliary stack capacity overflow when attempting to access an element buried deep in the primary stack.
Assuming a single global pointer can track the minimum element in O(1) without accounting for the O(n) search required when the minimum element is popped.
Assuming auxiliary data structures like Min-Heaps or sorted arrays maintain O(1) stack operations, overlooking the O(log n) or O(n) degradation on push/pop.

How questions are asked

Direct arithmetic evaluation of postfix token sequences
Permutation feasibility identification with bounded capacity constraints
Algorithmic design and time complexity analysis for augmented data structures

Paper trends

Shift from direct arithmetic evaluation (1-mark single-correct MCQ) toward complex multi-select structural reasoning (2-mark MSQs).
2025, 2024, 2015
Emphasis on resource and complexity bounds—such as finite stack buffer capacity and strict $O(1)$ worst-case time complexity for augmented operations.
2025, 2024

Difficulty notes

Easy items involve deterministic single-pass tracing (e.g., evaluating postfix notation). Medium items involve combinatorial permutation analysis with buffer constraints (MSQs where multiple permutations must be simulated) or rigorous asymptotic verification of augmented data structure operations under PUSH/POP lifecycles.