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