Queue Implementation Using Linked List in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Enqueue and Dequeue Operations

What is the printed state of the queue after the following operations?

Enqueue 10, Enqueue 20, Dequeue, Enqueue 30

DSA C

struct Node {
    int data;
    struct Node* next;
};

struct Queue {
    struct Node *front, *rear;
};

void enqueue(struct Queue* q, int value) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = value;
    temp->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

int dequeue(struct Queue* q) {
    if (q->front == NULL) return -1;
    struct Node* temp = q->front;
    int val = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return val;
}

void printQueue(struct Queue* q) {
    struct Node* temp = q->front;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("null\n");
}

int main() {
    struct Queue q = {NULL, NULL};
    enqueue(&q, 10);
    enqueue(&q, 20);
    dequeue(&q);
    enqueue(&q, 30);
    printQueue(&q);
    return 0;
}

A 20 -> 30 -> null

B 10 -> 20 -> 30 -> null

C 30 -> null

D 10 -> 30 -> null

💡 Hint

Remember that dequeue removes from the front of the queue.

After enqueueing 10 and 20, the queue is 10 -> 20 -> null. Dequeue removes 10, so queue becomes 20 -> null. Enqueue 30 adds it to the rear, so queue is 20 -> 30 -> null.

❓ Predict Output

intermediate

Output after Multiple Dequeues

What is the output after these operations?

Enqueue 5, Enqueue 15, Enqueue 25, Dequeue, Dequeue, printQueue

DSA C

struct Node {
    int data;
    struct Node* next;
};

struct Queue {
    struct Node *front, *rear;
};

void enqueue(struct Queue* q, int value) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = value;
    temp->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

int dequeue(struct Queue* q) {
    if (q->front == NULL) return -1;
    struct Node* temp = q->front;
    int val = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return val;
}

void printQueue(struct Queue* q) {
    struct Node* temp = q->front;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("null\n");
}

int main() {
    struct Queue q = {NULL, NULL};
    enqueue(&q, 5);
    enqueue(&q, 15);
    enqueue(&q, 25);
    dequeue(&q);
    dequeue(&q);
    printQueue(&q);
    return 0;
}

A 25 -> null

B 5 -> 15 -> 25 -> null

C null

D 15 -> 25 -> null

💡 Hint

Two dequeues remove the first two elements.

After enqueueing 5, 15, 25, the queue is 5 -> 15 -> 25 -> null. Two dequeues remove 5 and 15, leaving 25 -> null.

🔧 Debug

advanced

Identify the Bug in Dequeue Function

What error will occur when running this dequeue function if the queue is empty?

DSA C

int dequeue(struct Queue* q) {
    struct Node* temp = q->front;
    int val = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return val;
}

A Compilation error due to missing return type

B No error, returns -1

C Memory leak error

D Segmentation fault due to dereferencing NULL pointer

💡 Hint

Check what happens if q->front is NULL before accessing temp->data.

If the queue is empty, q->front is NULL. Dereferencing temp->data causes a segmentation fault (crash). The function lacks a check for empty queue.

❓ Predict Output

advanced

Output after Enqueue and Dequeue Sequence

What is the printed queue after these operations?

Enqueue 1, Enqueue 2, Enqueue 3, Dequeue, Enqueue 4, Dequeue, Enqueue 5, printQueue

DSA C

struct Node {
    int data;
    struct Node* next;
};

struct Queue {
    struct Node *front, *rear;
};

void enqueue(struct Queue* q, int value) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = value;
    temp->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

int dequeue(struct Queue* q) {
    if (q->front == NULL) return -1;
    struct Node* temp = q->front;
    int val = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return val;
}

void printQueue(struct Queue* q) {
    struct Node* temp = q->front;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("null\n");
}

int main() {
    struct Queue q = {NULL, NULL};
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    dequeue(&q);
    enqueue(&q, 4);
    dequeue(&q);
    enqueue(&q, 5);
    printQueue(&q);
    return 0;
}

A 4 -> 5 -> null

B 3 -> 4 -> 5 -> null

C 1 -> 2 -> 3 -> 4 -> 5 -> null

D 2 -> 3 -> 4 -> 5 -> null

💡 Hint

Each dequeue removes the front element.

Queue after enqueue 1,2,3: 1->2->3->null. Dequeue removes 1: 2->3->null. Enqueue 4: 2->3->4->null. Dequeue removes 2: 3->4->null. Enqueue 5: 3->4->5->null.

🧠 Conceptual

expert

Why Use Linked List for Queue Implementation?

Which of the following is the best reason to implement a queue using a linked list instead of an array?

A Linked list operations are always faster than arrays

B Linked list uses less memory than arrays always

C Linked list allows dynamic size without wasting memory or resizing

D Linked list does not require pointers

💡 Hint

Think about how arrays and linked lists handle size changes.

Linked lists can grow or shrink dynamically without needing to allocate a fixed size or resize, unlike arrays which have fixed size or costly resizing.

Practice

1. What is the main advantage of implementing a queue using a linked list instead of an array?

easy

A. Uses less memory than arrays always

B. Faster access to elements by index

C. Simpler code with fewer pointers

D. Dynamic size allows efficient memory use without fixed limits

Solution

1. Step 1: Understand queue size constraints in arrays

   Arrays have fixed size, so queues implemented with arrays have a maximum capacity.

2. Step 2: Analyze linked list flexibility

   Linked lists can grow or shrink dynamically, so queues using linked lists can handle any number of elements limited only by memory.

3. Final Answer:

   Dynamic size allows efficient memory use without fixed limits -> Option D

4. Quick Check:

   Linked list queues grow dynamically = A [OK]

Hint: Linked list queues grow dynamically, arrays don't [OK]

Common Mistakes:

• Thinking arrays always use less memory
• Confusing access speed with size flexibility
• Assuming linked lists have simpler code

2. Which of the following is the correct way to declare a node structure for a queue using a linked list in C?

easy

A. typedef struct Node { int data; Node* next; };

B. struct Node { int data; int next; };

C. typedef struct Node { int data; struct Node* next; } Node;

D. struct Node { int data; struct Node next; };

Solution

1. Step 1: Check pointer usage in struct

   The next pointer must be a pointer to struct Node, so 'struct Node* next;' is correct.

2. Step 2: Validate typedef syntax

   Using typedef with struct Node allows using 'Node' as type directly, which is correct in typedef struct Node { int data; struct Node* next; } Node;.

3. Final Answer:

   typedef struct Node { int data; struct Node* next; } Node; -> Option C

4. Quick Check:

   Pointer to struct Node with typedef = A [OK]

Hint: Use 'struct Node* next;' for pointer inside struct [OK]

Common Mistakes:

• Using 'int next;' instead of pointer
• Omitting 'struct' keyword before Node*
• Declaring next as struct Node instead of pointer

3. Consider the following C code snippet implementing enqueue operation for a queue using linked list:

void enqueue(Node** front, Node** rear, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    if (*rear == NULL) {
        *front = *rear = newNode;
    } else {
        (*rear)->next = newNode;
        *rear = newNode;
    }
}

What will be the state of the queue after these operations? enqueue(&front, &rear, 10); enqueue(&front, &rear, 20); enqueue(&front, &rear, 30);

medium

A. 10 -> 20 -> 30 -> NULL

B. 30 -> 20 -> 10 -> NULL

C. 10 -> 30 -> 20 -> NULL

D. 20 -> 10 -> 30 -> NULL

Solution

1. Step 1: Trace first enqueue call

   Queue is empty, so front and rear point to new node with data 10.

2. Step 2: Trace second and third enqueue calls

   New nodes with 20 and 30 are added at rear, linked in order: 10 -> 20 -> 30 -> NULL.

3. Final Answer:

   10 -> 20 -> 30 -> NULL -> Option A

4. Quick Check:

   Enqueue adds at rear, order preserved = C [OK]

Hint: Enqueue adds at rear, so order is insertion order [OK]

Common Mistakes:

• Confusing enqueue with push (stack behavior)
• Reversing order of nodes
• Not updating rear pointer correctly

4. The following dequeue function for a queue using linked list has a bug. Identify the bug:

int dequeue(Node** front, Node** rear) {
    if (*front == NULL) {
        printf("Queue is empty\n");
        return -1;
    }
    Node* temp = *front;
    int value = temp->data;
    *front = (*front)->next;
    free(temp);
    return value;
}

medium

A. Does not free memory of dequeued node

B. Does not update rear when queue becomes empty

C. Returns wrong value after dequeue

D. Does not check if front is NULL before dequeue

Solution

1. Step 1: Analyze dequeue steps

   Function removes front node and updates front pointer correctly.

2. Step 2: Check rear pointer update

   If after dequeue front becomes NULL (queue empty), rear should also be set to NULL but this is missing.

3. Final Answer:

   Does not update rear when queue becomes empty -> Option B

4. Quick Check:

   Rear must be NULL if queue empty = B [OK]

Hint: Set rear to NULL when front becomes NULL after dequeue [OK]

Common Mistakes:

• Forgetting to update rear on empty queue
• Not freeing dequeued node memory
• Returning wrong data value

5. You want to implement a function reverseQueue that reverses the elements of a queue implemented using a linked list. Which approach is the most efficient and correct?

hard

A. Use a stack to push all elements, then enqueue them back to queue

B. Traverse the linked list and swap data of front and rear nodes repeatedly

C. Dequeue all elements and enqueue them back in the same order

D. Create a new linked list and copy elements in reverse order without modifying original

Solution

1. Step 1: Understand reversing queue with linked list

   Reversing requires changing order of elements, which is not straightforward by swapping nodes in singly linked list.

2. Step 2: Evaluate stack approach

   Using a stack to push all elements then enqueue back reverses order efficiently and correctly.

3. Step 3: Check other options

   Swapping data repeatedly is complex and error-prone; copying to new list wastes memory; re-enqueueing same order does nothing.

4. Final Answer:

   Use a stack to push all elements, then enqueue them back to queue -> Option A

5. Quick Check:

   Stack reverses order efficiently = D [OK]

Hint: Use stack to reverse queue elements easily [OK]

Common Mistakes:

• Trying to swap nodes in singly linked list
• Re-enqueueing without changing order
• Copying to new list wastes memory