GATE CS Stacks and Queues Previous Year Questions

GATE CS 2025 Set 2 | Question 45

MSQ · 2 marks

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

without deleting the corresponding record, and
without increasing the complexities of the standard stack operations.

Which one or more of the following approach(es) can achieve it?

Keep with every record in the stack, a pointer to the record with the smallest key below it. Keep a pointer to the record with the smallest key in the stack. Keep an auxiliary array in which the key values of the records in the stack are maintained in sorted order. Keep a Min-Heap in which the key values of the records in the stack are maintained.

Explanation

Answer: (A)

A works. On PUSH, the new record stores a pointer to the minimum of the records below it: the smaller of the old top and the record the old top points to, found in \(O(1)\). MIN compares the top with the record its pointer names, also \(O(1)\). POP just removes the top, and the pointers in the records left behind are still correct.
B fails. Once the minimum is popped, finding the new minimum needs an \(O(n)\) scan, so POP gets slower.
C fails. Keeping an array sorted costs \(O(n)\) shifting on each PUSH and POP.
D fails. Heap insertion and deletion take \(O(\log n)\), so PUSH and POP are no longer \(O(1)\).

Answer: A

GATE CS 2024 Set 2 | Question 48

MSQ · 2 marks

Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of 2 elements. S1 already has 4 elements: 100, 200, 300, and 400, whereas S2 is empty, as shown below.

Stack `S1`
400 (Top)
300
200
100

Stack `S2`

Only the following three operations are available:
PushToS2: Pop the top element from S1 and push it on S2.
PushToS1: Pop the top element from S2 and push it on S1.
GenerateOutput: Pop the top element from S1 and output it to the user.

Note that the pop operation is not allowed on an empty stack and the push operation is not allowed on a full stack.

Which of the following output sequences can be generated by using the above operations?

100, 200, 400, 300 200, 300, 400, 100 400, 200, 100, 300 300, 200, 400, 100

Explanation

Answer: (B), (C), (D)

Only S1 can output, and S2 can park at most two elements taken from the top of S1.

(A) Impossible: to output 100 first, the three elements above it (400, 300 and 200) must all be parked, but S2 holds only two.
(B) Park 400 and 300, output 200, move 300 back and output it, move 400 back and output it, then output 100.
(C) Output 400, park 300, output 200 and 100, then move 300 back and output it.
(D) Park 400, output 300 and 200, move 400 back and output it, then output 100.

Answer: B, C, D