GATE CS 2025 (Afternoon) — Question 45

Data StructuresAbstract Data Types (ADTs), Stacks, QueuesMSQ2 marksMedium

Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct. We wish to augment the stack data structure with an O(1) time MIN operation that returns a pointer to the record with smallest key present in the stack 1. without deleting the corresponding record, and 2. without increasing the complexities of the standard stack operations. Which one or more of the following approach(es) can achieve it?
  1. A
    Keep with every record in the stack, a pointer to the record with the smallest key below it.
  2. B
    Keep a pointer to the record with the smallest key in the stack.
  3. C
    Keep an auxiliary array in which the key values of the records in the stack are maintained in sorted order.
  4. D
    Keep a Min-Heap in which the key values of the records in the stack are maintained.
Practise the full 2025-AN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAWhat rank do your marks get?GATE score, likely All-India Rank and qualifying marks for your category.
Practise more on Abstract Data Types (ADTs), Stacks, QueuesTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group