Question 7 of 9: Pointer-Based Data Structures — Linked-List Queue

Question 7: Pointer-Based Data Structures — Linked-List Queue (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A queue ADT with four operations (make_empty, is_empty, enqueue, dequeue) to be backed by a singly linked list.

Find. A working implementation of all four operations, each $O(1)$.

Approach. Keep two pointers, front (head, the next element to dequeue) and rear (tail, where the next enqueued element is linked in); enqueue appends after rear, dequeue removes and frees front.

1. Write the corrected header, queue.h.

   #ifndef QUEUE_H
   #define QUEUE_H
   
   struct node {
       int data;
       struct node *next;
   };
   
   void make_empty(void);
   int  is_empty(void);
   void enqueue(int i);
   int  dequeue(void);
   
   #endif

2. Write the implementation, queue.c.

   #include <stdio.h>
   #include <stdlib.h>
   #include "queue.h"
   
   static struct node *front = NULL;   /* head: next to dequeue */
   static struct node *rear  = NULL;   /* tail: last enqueued   */
   
   void make_empty(void) {
       while (!is_empty()) dequeue();
   }
   
   int is_empty(void) {
       return front == NULL;
   }
   
   void enqueue(int i) {
       struct node *n = (struct node *)malloc(sizeof(struct node));
       n->data = i;
       n->next = NULL;
       if (rear == NULL) {              /* queue was empty */
           front = rear = n;
       } else {
           rear->next = n;
           rear = n;
       }
   }
   
   int dequeue(void) {
       struct node *old;
       int value;
       if (is_empty()) {
           fprintf(stderr, "Error: dequeue from empty queue\n");
           exit(1);
       }
       value = front->data;
       old = front;
       front = front->next;
       if (front == NULL) rear = NULL;   /* queue just became empty */
       free(old);
       return value;
   }

3. Trace enqueue(1), enqueue(2), enqueue(3), dequeue(), dequeue() to confirm FIFO order. After the three enqueues the list is $\text{front}\to1\to2\to3\leftarrow\text{rear}$. The first dequeue() returns 1 and advances front to the node holding 2; the second returns 2 and advances front to the node holding 3 — elements come out in the same order they went in, which is exactly the FIFO behaviour a queue (as opposed to a stack) requires. $$\boxed{\text{dequeue order for enqueue}(1,2,3) = 1,\,2,\,(3\text{ remains})}$$