C Queue

« Previous Tutorial Next Tutorial »

In C programming, a queue is a linear list of information that is accessed in first-in, first-out order, that is also called as FIFO.

The first item placed on the queue is the first item retrieved, the second item put in is the second item retrieved, and so on. This is the only means of storage and retrieval in a queue. Random access of any specific item is not allowed.

In real life, Queues are very common. For example, lines at any fast-food restaurant are queues. To visualize that how a queue works. Consider the two functions named qstore() and qretrieve(). The qstore() function places an item onto the end of queue, and the qretrieve() function removes the first item from the queue and returns its value.

Working of Queue

Following table shows the effect of a series of these operations :

Action	Queue Contents
qstore(A)	A
qstore(B)	A B
qstore(C)	A B C
qretrieve() returns A	B C
qstore(D)	B C D
qretrieve() returns B	C D
qretrieve() returns C	D

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

To see an example of a queue in action, here we will use a simple appointment-scheduler program. This program allows you to enter a number of appointments; then, as each appointment is met, it is taken of the list. For the sake of simplicity, each appointment description will be limited to 255 characters. And the number of appointments is arbitrarily limited to 100.

First, the qstore() function and the qretrieve() function shown here are needed for simple scheduling program. They will store pointers to the strings that describe the 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 function require the two global variables i.e. the spos ( which holds the index of 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 data type by changing the base type of array that they operate on.

Here, the qstore() function places pointers to new appointments on the end of list and checks to see if 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. In essence, the rpos chases the spos through the queue. If the rpos and the spos are equal, then there are no events left in schedule. Even through the information stored in the queue is not actually destroyed by the qretrieve(), it is effectively destroyed because it can never be accessed again.

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

C Queue Example

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

/* C Queue - This is a Simple
 * Mini Appointment-Scheduler
 */

#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.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);

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

	for(t=0; t<MAX; t++)
	{
		p[t] = NULL;   // initializing array to nulls
	}
	for(;;)
	{
		printf("Press E, L, R, or Q for 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' :
				exit(1);
			default :
				printf("Wrong choice..!!\n");
				printf("Press any key to exit...");
				getch();
				exit(2);
		}
	}
	getch();
}

// enter appointments to 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("Out 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]);
	}
}

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

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

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

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

This program ask to press any of the four key, i.e., press E or e to enter, press L or l to list or display the queue, press R or r to remove from the queue, or press Q or q to quit the program. After pressing E or e, enter some items (enter names here). After entering some names, just press enter without entering any name to tell that no more item will enter now. After entering the names, just press L or l to watch the entered names. Or press R to remove item (name) from the queue. Or press Q or q to quit. Here is the sample run of this program.

After removing all the items from the queue, you will got a message tells "no more appointments..!!". Here is the sample output:

C Online Test

« Previous Tutorial Next Tutorial »