Queue in C programming with an example program

Because I defined the "queue" data structure in a separate post, this post only contains information about queue implementation in the C programming language. So, without further ado, let us begin with a brief introduction.

A queue in C programming is a linear list of information that is accessed in first-in, first-out (FIFO) order.

The first item placed in the queue is also the first item retrieved, followed by the second item, and so on. This is the only way to store and retrieve items from a queue. Random access to a particular item is not permitted.

In real life, queues are very common. There are lines at every restaurant and ticket counter where people stand in order to purchase a ticket. The first individual in line will be given the ticket first. To illustrate how a queue operates, consider the functions qstore() and qretrieve(). The qstore() function adds an item to the end of the queue, whereas the qretrieve() function removes the first item and returns its value.

The Operation of a Queue

The following table shows the effect of a series of these operations:

Note: Keep in mind that a retrieval operation removes an item from the queue and destroys it if it is not stored elsewhere. Therefore, a queue will be empty after all items have been removed.

Queues are used in many programming situations. The most common of all is in simulations. Queues are also used by the task scheduler of an operating system and for I/O buffering.

To demonstrate the operation of a queue, we will use a simple appointment-scheduling application. This program allows you to enter a number of appointments, which are then removed from the list as they are completed. Each appointment description will be limited to 255 characters for the sake of simplicity. In addition, 100 appointments are arbitrarily capped.

The qstore() and qretrieve() functions presented here are required for a simple scheduling program. They will store pointers to the string descriptions of appointments.

#define MAX 100
char *p[MAX];
int rpos = 0, spos = 0;

// store an appointment
void qstore(char *q)
{
   if (spos == MAX)
   {
      printf("List Full.\n");
      return;
   }
   p[spos] = q;
   spos++;
}

// retrieve an appointment
char *qretrieve()
{
   if (rpos == spos)
   {
      printf("No more appointments.\n");
      return '\0';
   }
   rpos++;
   return p[rpos - 1];

Notice that these functions require the two global variables, i.e., the spos (which holds the index of the next free storage location) and the rpos (which holds the index of the next item to retrieve). You can also use these functions to maintain a queue of other types of data by changing the base type of array that they operate on.

Here, the qstore() function places pointers to new appointments on the end of the list and checks to see if the list is full. And the qretrieve() function takes applications off the queue while there are events to perform. With each new appointment scheduled, the spos is incremented, and with each appointment completed, the  rpos is incremented. Essentially, the rpos follows the spos through the queue.If the rpos and the spos are equal, then there are no events left in the schedule. Even though the information stored in the queue is not actually destroyed by the qretrieve() call, it is effectively destroyed because it can never be accessed again.

Let's look at this figure to understand the concept of the C-queue:

Queue example program in C

Here is a simple C queue example program, which is the complete version of the appointment scheduler program:

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>

#define MAX 100

char *p[MAX];
char *qretrieve(void);
int spos = 0;
int rpos = 0;

void enter(void);
void qstore(char *q);
void review(void);
void delete_ap(void);

int main()
{
   char str[80];
   register int t;

   for (t = 0; t < MAX; t++)
   {
      p[t] = NULL;
   }
   while (1)
   {
      printf("Press E, L, R, or Q to enter, list, remove, or quit: ");
      gets(str);

      *str = toupper(*str);

      switch (*str)
      {
      case 'E':
         enter();
         break;
      case 'L':
         review();
         break;
      case 'R':
         delete_ap();
         break;
      case 'Q':
         return 0;
      default:
         printf("\nWrong choice.\n");
         return 0;
      }
   }

   return 0;
}

// Add appointments to the queue.
void enter(void)
{
   char str[256], *p;
   do
   {
      printf("Enter appointment %d: ", spos + 1);
      gets(str);
      if (*str == 0)       // no entry
      {
         break;
      }
      p = (char *)malloc(strlen(str) + 1);
      if (!p)
      {
         printf("\nOut of memory.\n");
         return;
      }
      strcpy(p, str);
      if (*str)
         qstore(p);
   } while (*str);
}

// See what is in the queue.
void review(void)
{
   register int t;

   for (t = rpos; t < spos; t++)
   {
      printf("%d. %s\n", t + 1, p[t]);
   }
   printf("\n");
}

// delete an appointment from the queue
void delete_ap(void)
{
   char *p;

   if ((p = qretrieve()) == NULL)
   {
      return;
   }
   printf("%s\n", p);
   printf("\n");
}

// store an appointment
void qstore(char *q)
{
   if (spos == MAX)
   {
      printf("List Full.\n");
      return;
   }
   p[spos] = q;
   spos++;
   printf("\n");
}

// retrieve an appointment
char *qretrieve(void)
{
   if (rpos == spos)
   {
      printf("No more appointments.\n");
      return NULL;
   }
   rpos++;
   return p[rpos - 1];
   printf("\n");
}

The following snapshot shows the initial output produced by the above program:

As shown in the output console, you must type any of the four characters "e", "l", "r", or "q" in the following order: type "e" or "E" and then hit the ENTER key to enter appointments or add items to the queue, type "l" or "L" and then hit the ENTER key to display the queue or all the appointments added to the queue, and type "r" or "R" and then hit the ENTER key to remove one item from the queue. Otherwise, type "q" or "Q" and hit the ENTER key to exit the program.

When you're finished entering appointments, simply hit the ENTER key without typing anything to stop entering more appointments. The snapshot below depicts the sample run with some user inputs.

As you can see, I began by typing "e" in order to enter the appointments. I entered "William," "Dave," and "Jack" for the first, second, and third appointments, then hit the ENTER key without typing anything. To see the queue items, I typed "l" and pressed the ENTER key. Then I hit the "r" key to remove the item from the queue. Always remember that the first item inserted will be the first item removed.

C Online Test