QUESTION 19

Why maintain both front and rear for a linked queue?

2 marks

Answer

front gives the next item to remove; rear lets enqueue attach at the end without a full-list search.

Explain a queue implemented using a singly linked list.

5 marks

Answer in brief

A linked queue keeps front and rear pointers so its FIFO operations need only constant link updates.

Enqueue

Allocate and initialise a new node with next = NULL.
On allocation failure, leave the queue unchanged and report failure.
If empty, set front to the new node; otherwise link rear->next to it.
Set rear to the new node.

Dequeue

Reject an empty front.
Save the front node and value, then advance front.
If front becomes NULL, set rear = NULL too.
Free the removed node and return its value.

Example

Enqueue 10 and 20 produces front → 10 → 20 ← rear. Dequeue returns 10. Removing 20 then makes both pointers NULL. A later enqueue must correctly recreate both ends rather than using a dangling old rear.

Resource management

A linked queue is not literally unlimited: every new node requires available storage. Its owner should destroy all remaining nodes before abandoning the queue. A missing rear update on the final removal is a common correctness error.

Complexity

Enqueue and dequeue use O(1) link work, excluding allocator internals. Without rear, enqueue could need O(n) traversal. The n nodes occupy O(n) data and link storage, with fixed queue-descriptor space.

Complete C example

main.c

Download main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
struct Queue { struct Node *front, *rear; };
int enqueue(struct Queue *q, int value)
{
    struct Node *node = malloc(sizeof *node);
    if (node == NULL) { return 0; }
    node->data = value; node->next = NULL;
    if (q->rear == NULL) { q->front = node; } else { q->rear->next = node; }
    q->rear = node; return 1;
}
int dequeue(struct Queue *q, int *out)
{
    if (q->front == NULL) { return 0; }
    struct Node *old = q->front; *out = old->data; q->front = old->next;
    if (q->front == NULL) { q->rear = NULL; }
    free(old); return 1;
}

int main(void)
{
    struct Queue q = {NULL, NULL}; int value;
    if (!enqueue(&q, 10) || !enqueue(&q, 20)) {
        while (dequeue(&q, &value)) { }
        puts("Allocation failed"); return 1;
    }
    while (dequeue(&q, &value)) { printf("%d\n", value); }
    return 0;
}

Sample input and output

The example uses values in the code.

Output

10
20