Stacks, Queues and Linked Lists PYQs for GATE CS

Solve 11+ Stacks, Queues and Linked Lists previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Stacks, Queues, and Linked Lists

Chapter Journey

1. Stack Operations and Augmented Stacks

Current Topic

Focus: Mastering the Last-In-First-Out (LIFO) principle and step-by-step tracing.

Key Skill: Optimizing stacks for constant-time minimum queries.

2. Queue Operations, Reversal and Stack-Queue Interaction

Focus: First-In-First-Out (FIFO) principle and simulating queues with stacks.

Key Skill: Reversal algorithms and data structure interactions.

3. Linked List Manipulation, Recursion and Complexity

Focus: Pointer manipulation and recursive traversal.

Key Skill: Time-space tradeoffs in linear data structures.

Exam Weightage Hint: Stacks (0.41), Queues (0.41), Linked Lists (0.55). Linked lists carry the highest weight, but stack augmentation is a frequent, high-value target.

Hero Concept: The Stack and Its Core Operations

The Core Intuition

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The element added most recently is the first one to be removed.

push(x) Inserts element $x$ at the top.
pop() Removes and returns the top element.
peek() Returns the top element without removing it.
isEmpty() Checks if the stack contains no elements.

Complexity: All standard stack operations execute in $O (1)$ time complexity, regardless of the number of elements

n

. This makes stacks indispensable for function call management, expression evaluation, and backtracking.

Stacks, Queues and Linked Lists: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Programming and Data Structures · 2026_Set2 MSQ

Consider a stack

S

and a queue

Q

. Both of them are initially empty and have the capacity to store ten elements each. The elements 1, 2, 3, 4, and 5 arrive one by one, in that order. When an element arrives, it is assigned either to

S

(pushed on

S

) or to

Q

(enqueued to

Q

). Once all the five elements are stored, the output is generated in two steps. First, stack S is emptied by popping all elements. Then queue

Q

is emptied by dequeueing all elements. The output obtained by following this process is 4 3 1 2 5 .
Given the output, the objective is to predict whether an element was assigned to

S

Q

.

Which of the following options is/are possible valid assignment(s) of the elements?

Note: In the options, the notation

x_{S}

denotes that element

x

was assigned to

S

and

y_{Q}

denotes that element

y

was assigned to

Q

A.
$1_{S}, 2_{Q}, 3_{S}, 4_{S}, 5_{Q}$
B.
$1_{Q}, 2_{Q}, 3_{S}, 4_{S}, 5_{Q}$
C.
$1_{Q}, 2_{Q}, 3_{Q}, 4_{S}, 5_{S}$
D.
$1_{S}, 2_{S}, 3_{S}, 4_{Q}, 5_{Q}$

Correct Answer:

["A","B"]

Step-by-Step Solution

Insight: This is a stack-queue stream splitting question, recognizable because it asks to deduce the routing of elements into a stack and a queue given the final concatenated output.

Exam route: Partition the output into a stack segment (reversed arrival) and a queue segment (original arrival), then interleave them to match 1, 2, 3, 4, 5.

Learning route:

Step 1: The final output is 4, 3, 1, 2, 5. This is formed by emptying the stack (LIFO) followed by emptying the queue (FIFO).

Step 2: We must partition the output into a stack segment and a queue segment.

Partition A: Stack outputs 4, 3, 1. Queue outputs 2, 5.

For the stack to output 4, 3, 1, the elements must have been pushed in the order 1, 3, 4.

For the queue to output 2, 5, the elements must have been enqueued in the order 2, 5.

Interleaving 1, 3, 4 and 2, 5 to match the arrival order 1, 2, 3, 4, 5 gives: 1->S, 2->Q, 3->S, 4->S, 5->Q. This matches option A.

Partition B: Stack outputs 4, 3. Queue outputs 1, 2, 5.

For the stack to output 4, 3, the elements must have been pushed in the order 3, 4.

For the queue to output 1, 2, 5, the elements must have been enqueued in the order 1, 2, 5.

Interleaving 3, 4 and 1, 2, 5 to match 1, 2, 3, 4, 5 gives: 1->Q, 2->Q, 3->S, 4->S, 5->Q. This matches option B.

Step 3: Verify other partitions. If stack outputs 4, queue outputs 3, 1, 2, 5. The queue arrival order would be 3, 1, 2, 5, which violates the increasing arrival order. Thus, only A and B are valid.

Question 2 · Programming and Data Structures · 2026_Set1 MCQ

Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head.

struct node{
   int elt;
   struct node *next;
};

int getListSize (struct node *head)
{
  if( E1 ) return 1;
  return E2;
}

Which one of the following options gives the correct replacements for the expressions E1 and E2?

A. E1: head == NULL
E2: 1 + getListSize(head)
B. E1: head->next == NULL
E2: 1 + getListSize(head->next)
C. E1: head == NULL
E2: 1 + getListSize(head->next)
D. E1: head->next == NULL
E2: 1 + getListSize(head)

Correct Answer:

Step-by-Step Solution

Insight: This is a recursive linked list traversal question, recognizable because it provides a code snippet with missing base case and recursive step expressions for computing the size of a list.

Exam route: Base case for a non-empty list is head->next == NULL (return 1). Recursive step is 1 + getListSize(head->next).

Learning route:

Step 1: Analyze the problem constraints. The problem states the list is "non-empty", meaning head is never NULL initially. The function should return the total number of nodes.

Step 2: Determine the base case (E1). The recursion should stop when we reach the last node. For a non-empty list, the last node is identified by its next pointer being NULL. Therefore, the condition head->next == NULL correctly identifies a single remaining node, and the function should return 1.

Step 3: Determine the recursive step (E2). If the list has more than one node, the total size is 1 (for the current head node) plus the size of the rest of the list. The rest of the list starts at head->next. Therefore, the recursive call should be 1 + getListSize(head->next).

Step 4: Verify the options. Option B provides E1: head->next == NULL and E2: 1 + getListSize(head->next), which perfectly matches our derivation.

Question 3 · Programming and Data Structures · 2025_Set2 MSQ

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?

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

Correct Answer:

["A"]

Step-by-Step Solution

Insight: This is an augmented data structure question, recognizable because it asks how to add a new operation (MIN) to a stack without degrading the O(1) time complexity of existing operations (PUSH, POP).

Exam route: Storing a pointer to the minimum record below allows O(1) MIN, PUSH, and POP. Other options introduce O(n) or O( $lo g n$ ) overhead.

Learning route:

Step 1: Analyze the requirements. We need MIN in O(1) time. PUSH and POP must remain O(1).

Step 2: Evaluate Option A (Pointer to min below). When pushing a new record, we compare its key with the minimum key of the record currently at the top of the stack. We set the new record's min-pointer to point to whichever is smaller (itself or the top's min-record). This takes O(1) time. When popping, we simply remove the top record. The new top record already contains the correct min-pointer for the remaining stack. MIN operation just follows the top record's min-pointer, taking O(1) time. This approach works perfectly.

Step 3: Evaluate Option B (Single min pointer). Pushing can update this pointer in O(1) time. However, if we POP the record that the min-pointer points to, we must scan the entire remaining stack to find the new minimum. This makes POP O(n), violating the constraint.

Step 4: Evaluate Option C (Sorted auxiliary array). Inserting a new key into a sorted array requires shifting elements, which takes O(n) time. This violates the O(1) PUSH constraint.

Step 5: Evaluate Option D (Min-Heap). Inserting into or deleting from a heap takes O( $lo g n$ ) time. Furthermore, deleting a specific element from the heap when it is popped from the stack requires finding it, which is not O(1).

Question 4 · Programming and Data Structures · 2025_Set1 NAT

Let LIST be a datatype for an implementation of linked list defined as follows:

typedef struct list {
    int data;
    struct list *next;
} LIST;

Suppose a program has created two linked lists, L1 and L2, whose contents are given in the figure below (code for creating L1 and L2 is not provided here). L1 contains 9 nodes, and L2 contains 7 nodes.

Consider the following C program segment that modifies the list L1. The number of nodes that will be there in L1 after the execution of the code segment is _______. (Answer in integer)

int find (int query, LIST *list) {
    while (list != NULL){
        if(list->data == query) return 1;
        list = list->next;
    }
    return 0;
}
int main () {
    … … …
    ptr1=L1; ptr2=L2;
    while (ptr1->next != NULL){
        query = ptr1->next->data;
        if (find (query, L2))
            ptr1->next = ptr1->next->next;
        else ptr1 = ptr1->next;
    }
    … … …
    return 0;
}

Correct Answer:

5.00

Step-by-Step Solution

Insight: This is a linked list traversal and conditional deletion question, recognizable because it uses two pointers to iterate through one list while checking membership in another list to decide whether to bypass a node.

Exam route: Trace the while loop step-by-step. Note that ptr1 only advances when a node is not found in L2. When a node is deleted, ptr1 stays put to evaluate the new ptr1->next.

Learning route:

Step 1: Understand the initial state. L1 has 9 nodes: 1 -> 7 -> 12 -> 3 -> 9 -> 5 -> 11 -> 15 -> 8. L2 has 7 nodes: 1 -> 11 -> 6 -> 9 -> 15 -> 12 -> 4.

Step 2: Analyze the loop condition and logic. The loop runs while ptr1->next != NULL. It checks if ptr1->next->data exists in L2 using the find function.

Step 3: Trace the execution.

ptr1 at 1. next is 7. 7 not in L2. ptr1 advances to 7.
ptr1 at 7. next is 12. 12 is in L2. Delete 12: ptr1->next becomes 3. ptr1 stays at 7.
ptr1 at 7. next is 3. 3 not in L2. ptr1 advances to 3.
ptr1 at 3. next is 9. 9 is in L2. Delete 9: ptr1->next becomes 5. ptr1 stays at 3.
ptr1 at 3. next is 5. 5 not in L2. ptr1 advances to 5.
ptr1 at 5. next is 11. 11 is in L2. Delete 11: ptr1->next becomes 15. ptr1 stays at 5.
ptr1 at 5. next is 15. 15 is in L2. Delete 15: ptr1->next becomes 8. ptr1 stays at 5.
ptr1 at 5. next is 8. 8 not in L2. ptr1 advances to 8.
ptr1 at 8. next is NULL. Loop terminates.

Step 4: Count the remaining nodes. The final L1 is 1 -> 7 -> 3 -> 5 -> 8. This is exactly 5 nodes.

Question 5 · Programming and Data Structures · 2024_Set2 MSQ

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.

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?

A.
100, 200, 400, 300
B.
200, 300, 400, 100
C.
400, 200, 100, 300
D.
300, 200, 400, 100

Correct Answer:

["B","C","D"]

Step-by-Step Solution

Insight: This is a stack interaction and capacity constraint question, recognizable because it involves two stacks with strict capacity limits and specific allowed transfer operations.

Exam route: Simulate the operations for each option, strictly enforcing the capacity of S2 (max 2 elements). If an option requires moving a 3rd element to S2, it is impossible.

Learning route:

Step 1: Understand the initial state. S1 has [100, 200, 300, 400] (400 is top, capacity 4, currently full). S2 is empty (capacity 2).

Step 2: Analyze the operations. We can only move elements S1 $\to$ S2 (max 2 elements), S2 $\to$ S1, or output from S1. We cannot output directly from S2.

Step 3: Test Option A (100, 200, 400, 300). To output 100 first, we must remove 400, 300, and 200 from S1. This requires pushing 3 elements into S2. However, S2 capacity is 2. This is impossible. Option A is invalid.

Step 4: Test Option B (200, 300, 400, 100).

PushToS2 twice: S1=[100, 200], S2=[400, 300] (300 top).
GenerateOutput: pops 200 from S1. Output: 200.
PushToS1: moves 300 to S1. GenerateOutput: pops 300. Output: 200, 300.
PushToS1: moves 400 to S1. GenerateOutput: pops 400. Output: 200, 300, 400.
GenerateOutput: pops 100. Output: 200, 300, 400, 100. Valid.

Step 5: Test Option C (400, 200, 100, 300).

GenerateOutput: pops 400. S1=[100, 200, 300].
PushToS2: S1=[100, 200], S2=[300].
GenerateOutput twice: pops 200, then 100. S1=[], S2=[300].
PushToS1: S1=[300]. GenerateOutput: pops 300. Valid.

Step 6: Test Option D (300, 200, 400, 100).

PushToS2: S1=[100, 200, 300], S2=[400].
GenerateOutput twice: pops 300, then 200. S1=[100], S2=[400].
PushToS1: S1=[100, 400]. GenerateOutput twice: pops 400, then 100. Valid.

Question 6 · Programming and Data Structures · 2023 NAT

Consider a sequence

a

of elements

a_{0} = 1

a_{1} = 5

a_{2} = 7

a_{3} = 8

a_{4} = 9

, and

a_{5} = 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

a_{0}

a_{5}

in that order into

S

.

II: enqueue the elements of

a

from

a_{0}

a_{5}

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 __________.

Correct Answer:

8.00

Step-by-Step Solution

Insight: This is a stack-queue stream splitting and tracing question, recognizable because it provides a sequence of elements and a specific sequence of push/pop/enqueue/dequeue operations.

Exam route: Track the state of S and Q step-by-step. S acts as LIFO, Q acts as FIFO.

Learning route:

Step 1: Initial state. S = [], Q = []. Sequence a = [1, 5, 7, 8, 9, 2].

Step 2: Operations I & II. Push all to S: S = [1, 5, 7, 8, 9, 2] (top is 2). Enqueue all to Q: Q = [1, 5, 7, 8, 9, 2] (front is 1).

Step 3: Operations III & IV. Pop S (removes 2). S = [1, 5, 7, 8, 9]. Dequeue Q (removes 1). Q = [5, 7, 8, 9, 2].

Step 4: Operations V & VI. Pop S (removes 9). S = [1, 5, 7, 8]. Dequeue Q (removes 5). Q = [7, 8, 9, 2].

Step 5: Operation VII. Dequeue Q (removes 7) and push to S. Q = [8, 9, 2], S = [1, 5, 7, 8, 7].

Step 6: Operation VIII. Repeat VII three times.

Repeat 1: Dequeue 8, push to S. Q = [9, 2], S = [1, 5, 7, 8, 7, 8].
Repeat 2: Dequeue 9, push to S. Q = [2], S = [1, 5, 7, 8, 7, 8, 9].
Repeat 3: Dequeue 2, push to S. Q = [], S = [1, 5, 7, 8, 7, 8, 9, 2].

Step 7: Operations IX & X. Pop S (removes 2). S = [1, 5, 7, 8, 7, 8, 9]. Pop S (removes 9). S = [1, 5, 7, 8, 7, 8].

Step 8: Final state. The top element of S is 8.

Question 7 · Programming and Data Structures · 2023 MCQ

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?

A.
$SLLdel$ is $O (1)$ and $DLLdel$ is $O (n)$
B.
Both $SLLdel$ and $DLLdel$ are $O (lo g (n))$
C.
Both $SLLdel$ and $DLLdel$ are $O (1)$
D.
$SLLdel$ is $O (n)$ and $DLLdel$ is $O (1)$

Correct Answer:

Step-by-Step Solution

Insight: This is a linked list deletion complexity question, recognizable because it asks for the worst-case time complexity of deleting a node given specific pointers.

Exam route: SLL requires $O (n)$ to find the predecessor from the head in the worst case (last node). DLL provides $O (1)$ access to the predecessor via the prev pointer.

Learning route:

Step 1: Analyze SLLdel. We are given a pointer to the node to be deleted and a pointer to the head. To delete a node in a singly linked list, we must update the next pointer of its predecessor. Since we only have the target node's pointer, we must traverse from the head to find the predecessor. In the worst case (deleting the last node, where the copy-data trick fails), this traversal takes $O (n)$ time.

Step 2: Analyze DLLdel. We are given a pointer to the node to be deleted. In a doubly linked list, every node has a prev pointer. We can directly access the predecessor in $O (1)$ time, update its next pointer, and update the successor's prev pointer. This entire process takes $O (1)$ time, regardless of the node's position.

Step 3: Compare the complexities. SLLdel is $O (n)$ and DLLdel is $O (1)$ .

Question 8 · Programming and Data Structures · 2022 NAT

Consider the queues

Q_{1}

containing four elements and

Q_{2}

containing none (shown as the Initial State in the figure). The only operations allowed on these two queues are Enqueue(Q,element) and Dequeue(Q). The minimum number of Enqueue operations on

Q_{1}

required to place the elements of

Q_{1}

Q_{2}

in reverse order (shown as the Final State in the figure) without using any additional storage is___________.

Correct Answer:

0.00

Step-by-Step Solution

Insight: This is a two-queue reversal operation counting question, recognizable because it asks for the minimum number of specific operations (Enqueue on Q1) to reverse a queue using only two queues.

Exam route: Recall the standard two-queue reversal algorithm. The source queue (Q1) only ever undergoes Dequeue operations. All Enqueue operations are performed on the destination queue (Q2). Therefore, Enqueue operations on Q1 is exactly 0.

Learning route:

Step 1: Understand the goal. We must reverse Q1 into Q2 using only Enqueue and Dequeue operations, with no additional storage.

Step 2: Recall the algorithm. To move the last element of Q1 to the front of Q2, we must cycle the preceding elements. This involves dequeuing from Q1 and enqueuing into Q2 (or a temporary holding area, which is Q2 itself in the optimized version).

Step 3: Analyze the operations on Q1. In every step of the reversal, elements are removed from Q1 via Dequeue. No element is ever added back to Q1.

Step 4: Conclude. Since Q1 acts strictly as the source from which elements are extracted, the number of Enqueue operations on Q1 is exactly 0.

Question 9 · Programming and Data Structures · 2022 MCQ

Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

the reversed linked list should look like

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in

O (1)

space?

A.
The best algorithm for the problem takes $θ (n)$ time in the worst case.
B.
The best algorithm for the problem takes $θ (n lo g n)$ time in the worst case.
C.
The best algorithm for the problem takes $θ (n^{2})$ time in the worst case.
D.
It is not possible to reverse a singly linked list in $O (1)$ space.

Correct Answer:

Step-by-Step Solution

Insight: This is a linked list reversal complexity question, recognizable because it asks for the time complexity of reversing a singly linked list under a strict $O (1)$ space constraint.

Exam route: Iterative reversal uses 3 pointers and visits each node exactly once, yielding $θ (n)$ time and $O (1)$ space.

Learning route:

Step 1: Understand the constraints. We must reverse a singly linked list of $n$ nodes using only $O (1)$ extra space (i.e., a constant number of pointers, no recursion stack, no auxiliary arrays).

Step 2: Recall the standard iterative reversal algorithm. We maintain three pointers: prev (initially NULL), curr (initially head), and next_temp (initially NULL).

Step 3: Traverse the list. In each iteration, we store curr->next in next_temp, reverse the link by setting curr->next = prev, and then advance prev and curr by one step.

Step 4: Analyze the complexity. The algorithm visits each of the $n$ nodes exactly once, performing a constant number of pointer assignments per node. Therefore, the time complexity is strictly $θ (n)$ . The space complexity is $O (1)$ because only three pointers are used.

Question 10 · Programming and Data Structures · 2021_Set2 MCQ

Consider the following ANSI C program:

#include <stdio.h>
#include <stdlib.h>
struct Node{
        int value;
        struct Node *next;};
int main(){
    struct Node *boxE, *head, *boxN; int index = 0;
    boxE = head = (struct Node *) malloc(sizeof(struct Node));
    head->value = index;
    for (index = 1; index <= 3; index++){
        boxN = (struct Node *) malloc(sizeof(struct Node));
        boxE->next = boxN;
        boxN->value = index;
        boxE = boxN; }
    for (index = 0; index <= 3; index++) {
        printf("Value at index %d is %d\n", index, head->value);
        head = head->next;
        printf("Value at index %d is %d\n", index+1, head->value); } }

Which one of the statements below is correct about the program?

A.
Upon execution, the program creates a linked-list of five nodes.
B.
Upon execution, the program goes into an infinite loop.
C.
It has a missing return which will be reported as an error by the compiler.
D.
It dereferences an uninitialized pointer that may result in a run-time error.

Correct Answer:

Step-by-Step Solution

Insight: This is a linked list traversal and pointer initialization question, recognizable because it involves a C program building a linked list and then traversing it, with a potential flaw in pointer setup.

Exam route: Trace the list creation. Notice the last node's next pointer is never set to NULL. The traversal loop will dereference this garbage pointer.

Learning route:

Step 1: Analyze list creation. The loop runs for index = 1, 2, 3. It allocates boxN, links boxE->next = boxN, sets boxN->value, and updates boxE = boxN. This creates 4 nodes total (indices 0, 1, 2, 3).

Step 2: Identify the flaw. After the loop terminates, boxE (which points to the last node, value 3) has its next pointer uninitialized. malloc does not zero out memory, so it contains a garbage value, not NULL.

Step 3: Analyze the traversal loop. It runs for index = 0 to 3.

index=0: prints head->value (0), head becomes node 1, prints head->value (1).
index=1: prints head->value (1), head becomes node 2, prints head->value (2).
index=2: prints head->value (2), head becomes node 3, prints head->value (3).
index=3: prints head->value (3), head becomes head->next (which is garbage), then attempts to print head->value.

Step 4: Conclude. Dereferencing this uninitialized garbage pointer results in undefined behavior, typically a segmentation fault (run-time error).

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Stacks, Queues and Linked Lists PYQs for GATE CS

Chapter Roadmap: Stacks, Queues, and Linked Lists

Chapter Journey

Hero Concept: The Stack and Its Core Operations

The Core Intuition

Stacks, Queues and Linked Lists: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit