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). A queue is generally seen as a fair way of allocating a resource where only one person can be allocated a resource at a time, either because of logistic constraints or because the demand is more than the supply at that time, and the price remaining a constant.

The end-points of a queue are of special interest. The person at the head of the queue is serviced first. The end of the queue is known as the tail. People enter the queue at the tail. 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.

The queue paradigm occurs often in design and implementation of algorithms. Like in real life, the queue in software systems also has two end points, its head and the tail. Initially, the queue is empty. As elements come in, 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) data structure.

We need a data structure to implement a queue in C. The size of a queue is not known a priori; it should be able to grow as much as required at runtime. So we need a dynamic data structure. A linked list is a suitable data structure for representing a queue because it can grow as much as is required at runtime and, also, it is easy to add and delete elements to it. 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.

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

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.

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

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

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.

The example program given below implements a queue using a linked-list. There are 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, starting at the head, and ending at 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
...