GATE DA Stacks and Queues Previous Year Questions

GATE DA 2025 | Question 64

NAT · 2 marks

Consider the following pseudocode.

Create empty stack S
Set x=0, flag=0, sum=0
Push x onto S
while (S is not empty){
    if (flag equals 0){
        Set x = x+1
        Push x onto S}
    if (x equals 8):
        Set flag=1
    if (flag equals 1){
        x = Pop(S)
        if (x is odd):
            Pop(S)
        Set sum = sum + x}
}
Output sum

The value of sum output by a program executing the above pseudocode is ________ (Answer in integer)

Your answer

Explanation

Answer: 24

While flag is 0, each pass pushes the next value, so the stack grows to 0, 1, …, 8 (top 8). In the pass that pushes 8, x equals 8, so flag becomes 1 (for good) and the third block already runs in that same pass.

Each such pass pops the top into x and adds it to sum; if x is odd, the element below it is popped and thrown away:

pop 8 (even): sum = 8
pop 7, discard 6: sum = 15
pop 5, discard 4: sum = 20
pop 3, discard 2: sum = 23
pop 1, discard 0: sum = 24

The stack is now empty, so the loop stops and 24 is output.

Answer: 24

GATE DA 2024 | Question 16

MCQ · 1 mark · −0.33

Match the items in Column 1 with the items in Column 2 in the following table:

Column 1	Column 2
(p) First In First Out	(i) Stacks
(q) Lookup Operation	(ii) Queues
(r) Last In First Out	(iii) Hash Tables

(p) − (ii), (q) − (iii), (r) − (i) (p) − (ii), (q) − (i), (r) − (iii) (p) − (i), (q) − (ii), (r) − (iii) (p) − (i), (q) − (iii), (r) − (ii)

Explanation

Answer: (A)

Each phrase in Column 1 is the defining behaviour of one structure:

(p) First In First Out: a queue removes items in the order they arrived, like a line at a counter, so (p) − (ii).
(q) Lookup: a hash table exists to find a value by its key in expected constant time, so (q) − (iii).
(r) Last In First Out: a stack always removes the most recently added item, like a pile of plates, so (r) − (i).

Only option (A) has all three pairs; (C) and (D) pair FIFO with stacks, and (B) pairs lookup with stacks.

Answer: A

GATE DA 2024 | Question 32

NAT · 1 mark

The fundamental operations in a double-ended queue D are:

insertFirst(e) – Insert a new element e at the beginning of D.
insertLast(e) – Insert a new element e at the end of D.
removeFirst() – Remove and return the first element of D.
removeLast() – Remove and return the last element of D.

In an empty double-ended queue, the following operations are performed:

insertFirst(10)

insertLast(32)

a ←removeFirst()

insertLast(28)

insertLast(17)

a ←removeFirst()

a ← removeLast()

The value of a is ______.

Your answer

Explanation

Answer: 17

Trace the deque, writing its front on the left:

insertFirst(10): [10]
insertLast(32): [10, 32]
removeFirst() returns 10, so a = 10: [32]
insertLast(28) and insertLast(17): [32, 28, 17]
removeFirst() returns 32, so a = 32: [28, 17]
removeLast() returns 17, so a = 17: [28]

Each assignment overwrites a, so its final value is 17. The 28 is still in the deque and is never assigned.

Answer: 17