Queue implementation in C using linked list

1.0 Queue



A queue is something we see often in our daily lives. People stand in a queue to get into a bus, to get food in a buffet, buy tickets from the ticket counter, etc. Queues are a fair solution of ordering people to get a resource; people are served in the chronological order of their arrival leading to the coinage of the phrase, first come, first served (FCFS). This appeals to people as being fair and nobody seems to be taking an unfair advantage.

The end-points of a queue are of special interest. The person at the head of the queue is genuinely happy because he or she would be served next. Then, there is the tail of the queue, where people join the queue. It is not unusual to find people joining the queue to be grim or have a perfunctory smile, aware of the pending wait in the queue. The important point is that a queue is a first-in first-out (FIFO) arrangement. If Alice comes to the queue before Bob, she is served and exits the queue before Bob.

2.0 Queue in software systems

Cut to the virtual world of software systems. Th queue paradigm occurs often in design and implementation of algorithms. Just like in real life, the queue in software systems has two end points, its head and the tail. Initially, the queue is empty. As elements come, they are added at the tail of the queue. Also, when an element from the queue is required, the element at the head of the queue is removed and given to the requester. 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) construct.

3.0 Queue in C

We need a data structure to implement a queue in C. A linked list is a suitable data structure for representing a queue. Suppose, we are making a queue of people. Each element of the queue represents a person. Each element of the queue is a structure containing a pointer to the person's name and a pointer to the next element in the queue.

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

We need to keep track of the head and tail of the queue. For this we have two pointers, head and tail. Initially, both head and tail are NULL.

Head and tail pointers

When the first element is added to the queue, both head and tail point to it.

Queue, with one element

Thereafter, to add an element, we add it behind the one pointed by the tail. We modify the next pointer of the last element to point to the new element. We also modify the tail to point to the new element.

Queue, after addition of second element

Similarly, when the element at the head of a queue element is deleted, the head pointer is modified.

Queue, after deletion of head element

So, our schematic representation of queue as a linked list is like this.

Schematic representation of a queue

On a closer look at the above diagram, we realize that we really do not need the head pointer. We have a pointer tail, pointing to the last element in the queue. We can 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

4.0 The example program

Enough of theory, it's time to put above concepts in the form of a program. So, here it is, a queue management program in C using linked list. We provide the two basic operations, enqueue and dequeue. Enqueue adds an element at the end of a queue. Dequeue deletes an element at the head of the queue. In addition, there is a facility to print the queue, from head to the tail.

/*
 *
 *     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
...