addr(A[i][j]) = base + ((j − c₀) × (#rows) + (i − r₀)) × size
Circular queue
next = (index + 1) mod n; count = (rear − front + n) mod n (when a slot is left empty)
Triangular matrix
n(n + 1)/2 stored elements
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Evaluate a postfix / convert infix to postfix
Run the stack by hand; track precedence and right-associative ^.
★★★
Stack/queue permutation or output sequence
Which output orders are possible from a given push order? Which cannot be produced?
★★★
Linked list code: what does it do?
Reversal, deleting nodes, finding the middle, cycle detection.
★★★
Implement a queue with stacks (or the reverse)
Counting push/pop operations for n enqueues and dequeues.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
14 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
14 questions · 0 correct of 0 attempted · marks 0 / 22
Year:
GATE 2025 CS2 · Q38MCQ2 marks
A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures: P: Unsorted doubly linked list with pointers to the head node and tail node of the list. Q: Min-heap implemented using an array. R: Binary Search Tree. Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size n of these data structures?
GATE 2025 CS2 · Q45MSQ2 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 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?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS2 · Q48MSQ2 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 (400 on top), whereas S2 is empty. 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?
One or more options may be correct. Select all that apply, then submit.
GATE 2023 · Q13MCQ1 mark
Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list. Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?
GATE 2023 · Q59NAT2 marks
Consider a sequence a of elements a0 = 1, a1 = 5, a2 = 7, a3 = 8, a4 = 9, and a5 = 2. The following operations are performed on a stack S and a queue Q, both of which are initially empty. I: push the elements of a from a0 to a5 in that order into S. II: enqueue the elements of a from a0 to a5 in that order into Q. III: pop an element from S. IV: dequeue an element from Q. V: pop an element from S. VI: dequeue an element from Q. VII: dequeue an element from Q and push the same element into S. VIII: Repeat operation VII three times. IX: pop an element from S. X: pop an element from S. The top element of S after executing the above operations is ______.
GATE 2022 · Q15MCQ1 mark
Consider the problem of reversing a singly linked list (head → a → b → c → d → e becomes head → e → d → c → b → a). Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?
GATE 2021 Set 1 · Q21NAT1 mark
Consider the following sequence of operations on an empty stack:
push(54);
push(52);
pop();
push(55);
push(62);
s = pop(). Consider the following sequence of operations on an empty queue: enqueue(21);
enqueue(24);
dequeue();
enqueue(28);
enqueue(32);
q = dequeue(). The value of s + q is ______.
GATE 2020 · Q16MCQ1 mark
What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?
GATE 2018 · Q3MCQ1 mark
A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer. Let n denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail. Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?
GATE 2016 Set 1 · Q10MCQ1 mark
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?
GATE 2016 Set 1 · Q34MCQ2 marks
The following function computes the maximum value contained in an integer array p[] of size n (n ≥ 1).
int max(int *p, int n) {
int a = 0, b = n − 1;
while (__________) {
if (p[a] <= p[b]) {
a = a + 1;
} else {
b = b − 1;
}
}
return p[a];
}
The missing loop condition is
GATE 2016 Set 1 · Q41NAT2 marks
Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm: while Q is not Empty do { if S is Empty OR Top(S) ≤ Head(Q) then { x := Dequeue(Q); Push(S, x); } else { x := Pop(S); Enqueue(Q, x); } }. The maximum possible number of iterations of the while loop in the algorithm is ______.
GATE 2013 Code A · Q44MCQ2 marks
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.
MultiDequeue(Q) {
m = k;
while (Q is not empty) and (m > 0) {
Dequeue(Q);
m = m − 1;
}
}
What is the worst case time complexity of a sequence of n queue operations on an initially empty queue?
GATE 2012 Code A · Q35MCQ2 marks
Suppose a circular queue of capacity (n − 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are
Common traps
In a stack-permutation question, the pattern 3 1 2 (a larger element out before a smaller one pushed earlier, with a smaller one still inside) is impossible.
Remember to subtract the lower bound when arrays do not start at 0.
Right-associative ^ is not popped by an equal-precedence ^.
Deleting the last node of a singly linked list is O(n) unless you keep a pointer to the previous node.