Queue implementation in C using linked list

1.0 Queue

A queue is a data structure with two end points, its head and the tail. Initially, the queue is empty. There are two basic operations available for a queue, enqueue and dequeue. The enqueue operation adds an element to the queue. Elements are added to a queue at its tail. The dequeue operation takes an element off the queue. The element at the head of a queue is dequeued. The elements are dequeued in the order they are enqueued making queue as a first-in, first-out (FIFO) data structure.

Schematic representation of a queue

2.0 Data Structure

In an example program, we will develop a queue of persons. Each element of the queue represents a person. Each element contains a pointer to the person's name and a pointer to the next element in the queue. Since the size of a queue is not known beforehand, we will use a linked list as the basic data structure for the queue. The element structure is,

struct element { char *name; struct element *next; };

We have a pointer tail, pointing to the last element in the queue. We don't really need a pointer to the head of the queue as we make the next element of the last element (pointed by tail) point to the first element (head) of the queue. So tail -> next always points to the head of the queue. Our schematic diagram for the queue implementation looks like this.

Schematic representation of queue implementation

3.0 The example program

/* * * queue.c: program for queue implementation in C using linked list * */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define BUFSIZE 256 struct element { char *name; struct element *next; }; struct element *tail; void init_queue (void); void enqueue (char *name); int dequeue (char *name); void print_queue (void); void error (char *msg); int main (int argc, char **argv) { char buf [BUFSIZE]; init_queue (); while (1) { printf ("\n1: Enqueue\n2: Dequeue\n3: Print queue\n0: Quit\n\nEnter your choice: "); if (fgets (buf, BUFSIZE, stdin) == NULL) break; if (buf [0] == '1') { // Enqueue // Get name printf ("Name: "); if (fgets (buf, BUFSIZE, stdin) == NULL) break; int len = strlen (buf); if (buf [len - 1] == '\n') buf [len - 1] = '\0'; enqueue (buf); } else if (buf [0] == '2') { // Dequeue if (dequeue (buf) != -1) printf ("%s dequeued\n", buf); } else if (buf [0] == '3') print_queue (); else if (buf [0] == '0') break; else fprintf (stderr, "Error in input\n"); } exit (0); } void init_queue (void) { tail = NULL; } void enqueue (char *name) { struct element *ptr; char *cp; if ((ptr = (struct element *) malloc (sizeof (struct element))) == NULL) error ("malloc"); if ((cp = (char *) malloc (strlen (name) + 1)) == NULL) error ("malloc"); strcpy (cp, name); ptr -> name = cp; if (tail == NULL) { ptr -> next = ptr; } else { ptr -> next = tail -> next; tail -> next = ptr; } tail = ptr; } int dequeue (char *name) // returns -1 on error { struct element *ptr; char *cp; if (!tail) { fprintf (stderr, "Queue is empty\n"); return -1; } // get the head ptr = tail -> next; cp = ptr -> name; if (ptr == tail) tail = NULL; else tail -> next = ptr -> next; free (ptr); strcpy (name, cp); free (cp); return 0; } void print_queue (void) { struct element *ptr, *head; if (!tail) { fprintf (stderr, "Queue is empty\n"); return; } printf ("Queue: \n"); // get the head head = ptr = tail -> next; int i = 1; do { printf ("%d. %s\n", i, ptr -> name); ptr = ptr -> next; i++; } while (ptr != head); } void error (char *msg) { perror (msg); exit (1); }

We can compile and run the above program.

$ gcc queue.c -o queue $ ./queue 1: Enqueue 2: Dequeue 3: Print queue 0: Quit Enter your choice: 1 Name: Alice 1: Enqueue 2: Dequeue 3: Print queue 0: Quit Enter your choice: 1 Name: Bob ... ... 1: Enqueue 2: Dequeue 3: Print queue 0: Quit Enter your choice: 3 Queue: 1. Alice 2. Bob 3. Carol 4. Dave 5. Erin 1: Enqueue 2: Dequeue 3: Print queue 0: Quit Enter your choice: 2 Alice dequeued 1: Enqueue 2: Dequeue 3: Print queue 0: Quit Enter your choice: 3 Queue: 1. Bob 2. Carol 3. Dave 4. Erin ...

Software: