This page was last updated June 12, 2001

The Queue Abstract Data Type

The Abstract Data Type (ADT) of a queue is like a line in which items are added at the end of the line with a function called Enqueue() and removed from the front of the line with a function called Dequeue().

This code example illustrates the use of a queue. There are three different implementations given. The first implements the queue as an array, the second as a linked data structure, and the third as a C++ class.

QInterface.h

/************************************************************/
/* File: QInterface.h                                       */
/*                                                          */
/* Interface file for a queue implemented as an array.      */
/************************************************************/
#include "QTypes.h"

void QInitialize(Queue *Q);
int  QueueEmpty(Queue *Q);
int  QueueFull(Queue *Q);
void Enqueue(Queue *Q, int ival, char *str);
QueueItem *Dequeue(Queue *Q);
void PrintQueue(Queue *Q);

QTypes.h

Array Implementation

/************************************************************/
/* File: QTypes.h                                           */
/*                                                          */
/* Header file for a queue implemented as an array.         */
/************************************************************/
#define MAXQUEUE	25

typedef struct QueueItemType
	{
	int	ivar;
	char	dataArray[25];
	} QueueItem;

typedef struct QueueType
	{
	int          head;
	int          tail;
	QueueItem    QArray[MAXQUEUE];
	} Queue;

#ifndef FALSE
#define FALSE (0)
#endif

#ifndef TRUE
#define TRUE (!FALSE)
#endif

Queue.c

Array Implementation

/************************************************************/
/* File: Queue.c                                            */
/*                                                          */
/* Implementation file for array queue demonstration.       */
/* Author: Dr. Rick Coleman, CS 207 Instructor              */
/* Date: June 2001                                          */
/************************************************************/
#include "QTypes.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/***********************************/
/* QInitialize()                   */
/* Initialize a queue as an empty  */
/*    linked list.                 */
/***********************************/
void QInitialize(Queue *Q)
{
	Q->head = Q->tail = 0;
}

/***********************************/
/* QueueEmpty()                    */
/* Check to see if the queue is    */
/*      empty.                     */
/***********************************/
int QueueEmpty(Queue *Q)
{
	return(Q->tail == Q->head);
}

/***********************************/
/* QueueFull()                     */
/* Check to see if the queue is    */
/*    full.                        */
/***********************************/
int QueueFull(Queue *Q)
{
	return((Q->tail - Q->head) >= (MAXQUEUE - 1));
}

/***********************************/
/* Enqueue()                       */
/* Add an item to the queue.       */
/***********************************/
void Enqueue(Queue *Q, int ival, char *str)
{
	if(QueueFull(Q))
		printf("Queue is full.  Cannot enqueue item.\n");
	else
	{
		Q->QArray[Q->tail % MAXQUEUE].ivar = ival;
		strcpy(Q->QArray[Q->tail % MAXQUEUE].dataArray, str);
		Q->tail++;
	}
}

/***********************************/
/* Dequeue()                       */
/* Return a char * to the first    */
/*   task in the list.             */
/***********************************/
QueueItem *Dequeue(Queue *Q)
{
	QueueItem *temp;

	if(QueueEmpty()) return(NULL);	/* Queue is empty */
	else
	{
		/* Create a structure to return the values in */
		temp = (QueueItem *)malloc(sizeof(QueueItem));
		/* Copy whole data structure */
		*temp = Q->QArray[Q->head % MAXQUEUE]; 
		Q->head++;
		return(temp);
	}
}

/***********************************/
/* PrintQueue()                    */
/* Print all items in the queue.   */
/***********************************/
void PrintQueue(Queue *Q)
{
	int i;

	if(QueueEmpty())
		printf("There are no items in the queue.\n");	
	else
	{
		printf("\nQueue Contents:\n");
		printf("-----------------------------------------\n");
		printf("Int Value    String\n");
		for(i=Q->head; itail; i++)
		{
			printf("%d\t\t%s\n", Q->QArray[i % MAXQUEUE].ivar, 
						Q->QArray[i % MAXQUEUE].dataArray);
		}
		printf("\n");
	}
}

QueueMain.c

Main program used in both array and linked implementation

/************************************************************/
/* File: QueueMain.c                                        */
/*                                                          */
/* Implementation of a simple Queue abstract data type as a */
/*    linked ADT.                                           */
/* Author: Dr. Rick Coleman, CS 207 Instructor              */
/* Date: June 2001                                          */
/************************************************************/
#include "QInterface.h"
#include <stdio.h>
#include <stdlib.h>

void PrintQItem(QueueItem *QItem);

main()
{
	Queue		theQ;
	QueueItem	*QI;
	
	/* Initialize the queue */
	QInitialize(&theQ);

	/* Enqueue some items */
	Enqueue(&theQ, 1, "Queue Item 1");
	Enqueue(&theQ, 2, "Queue Item 2");
	Enqueue(&theQ, 3, "Queue Item 3");

	/* Print what is in the queue */
	PrintQueue(&theQ);
	printf("Press Enter to continue");
	getchar();	/* Pause, let user see display before going on */

	/* Enqueue some more items */
	Enqueue(&theQ, 4, "Queue Item 4");
	Enqueue(&theQ, 5, "Queue Item 5");

	/* Print what is in the queue */
	PrintQueue(&theQ);
	printf("Press Enter to continue");
	getchar();

	/* Dequeue and print some items */
	QI = Dequeue(&theQ);
	PrintQItem(QI);
	QI = Dequeue(&theQ);
	PrintQItem(QI);
	printf("Press Enter to continue");
	getchar();

	/* Print what is in the queue */
	PrintQueue(&theQ);
	printf("Press Enter to continue");
	getchar();

	/* Dequeue and print some more items */
	QI = Dequeue(&theQ);
	PrintQItem(QI);
	QI = Dequeue(&theQ);
	PrintQItem(QI);

	/* Print what is in the queue */
	PrintQueue(&theQ);
	printf("Press Enter to continue");
	getchar();

	/* Empty the queue */
	QI = Dequeue(&theQ);
	PrintQItem(QI);
	QI = Dequeue(&theQ);
	PrintQItem(QI);

	/* Print what is in the queue */
	PrintQueue(&theQ);

	return(0);
}

/********************************************************/
/* Function: PrintQItem()                               */
/* Purpose:  Print data in a single item from a queue.  */
/* Args:     QItem - Pointer to a QueueItem structure.  */
/* Returns:  void                                       */
/********************************************************/
void PrintQItem(QueueItem *QItem)
{
	if(QItem == NULL)
		printf("Queue item is empty.\n");
	else
		printf("Queue data: %d - %s\n", QItem->ivar, 
				QItem->dataArray);
}
The code shown above implements a queue as an array. The code below shows how the same queue, using the same interface file and main() can be implemented as a linked structure.

QTypes.h

Linked Implementation

/************************************************************/
/* File: QTypes.h                                           */
/*                                                          */
/* Header file for a Queue implemented as a linked list.    */
/************************************************************/

typedef struct QueueItemType
	{
	int                    ivar;
	char                   dataArray[25];
	struct  QueueItemType  *next;
	} QueueItem;

typedef struct QueueType
	{
	QueueItem	*head;
	QueueItem	*tail;
	} Queue;

#ifndef FALSE
#define FALSE (0)
#endif

#ifndef TRUE
#define TRUE (!FALSE)
#endif

Queue.c

Linked Implementation

/************************************************************/
/* File: Queue.c                                            */
/*                                                          */
/* Implementation file for linked queue demonstration.      */
/* Author: Dr. Rick Coleman, CS 207 Instructor              */
/* Date: June 2001                                          */
/************************************************************/
#include "QTypes.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/***********************************/
/* QInitialize()                   */
/* Initialize a queue as an empty  */
/*    linked list.                 */
/***********************************/
void QInitialize(Queue *Q)
{
	QueueItem *temp;

	if(Q->head != NULL) /* Free any existing list */
	{
		temp = Q->head;
		while(temp != NULL)
		{
			temp = Q->head->next;
			free(Q->head);
			Q->head = temp;
		}  
	}
	Q->head = Q->tail = NULL;
}

/***********************************/
/* QueueEmpty()                    */
/* Check to see if the queue is    */
/*     empty.                      */
/***********************************/
int QueueEmpty(Queue *Q)
{
	return(Q->head == NULL);
}

/***********************************/
/* QueueFull()                     */
/* Check to see if the queue is    */
/*     full.                       */
/***********************************/
int QueueFull(Queue *Q)
{
	return(FALSE); /* Assume linked queue can't be full */
}

/***********************************/
/* Enqueue()                       */
/* Add an item to the queue.       */
/***********************************/
void Enqueue(Queue *Q, int ival, char *str)
{
	QueueItem *temp;

	/* Create a new QueueItem and set the fields */
	temp = (QueueItem *)malloc(sizeof(QueueItem));
	temp->ivar = ival;
	strcpy(temp->dataArray, str);
	temp->next = NULL;

	/* Insert into the queue */
	if(Q->head == NULL)	/* Insert as first in the queue */
		Q->head = Q->tail = temp;
	else /* Insert at tail of the queue */
	{
		Q->tail->next = temp;
		Q->tail = temp;
	}
}

/***********************************/
/* Dequeue()                       */
/* Return a char * to the first    */
/*   task in the list.             */
/***********************************/
QueueItem *Dequeue(Queue *Q)
{
	QueueItem *temp;

	if(QueueEmpty(Q)) return(NULL);	/* Queue is empty */
	else
	{
		temp = Q->head;
		Q->head = Q->head->next;
		if(Q->head == NULL) Q->tail = NULL;
		return(temp);
	}
}

/***********************************/
/* PrintQueue()                    */
/* Print all items in the queue.   */
/***********************************/
void PrintQueue(Queue *Q)
{
	QueueItem *temp;

	if(QueueEmpty(Q))
		printf("There are no items in the queue.\n");
	else
	{
		printf("\nQueue Contents:\n");
		printf("-----------------------------------------\n");
		printf("Int Value    String\n");
		temp = Q->head;
		while(temp != NULL)
		{
			printf("%d\t\t%s\n", temp->ivar, temp->dataArray);
			temp = temp->next;
		}
		printf("\n");
	}
}
The code shown below shows how the linked implementation of the same queue can be modified to create a C++ Queue Class. The two header files have been combined into a single Class interface definition header file. All standard I/O using printf(), scanf(), gets(), and getch() has been replaced with stream I/O using cin (pronounced "cee-in") and cout (pronounced "cee-out").

Queue.h

C++ Linked Implementation

/************************************************************/
/* File: Queue.h                                            */
/*                                                          */
/* Header file for a queue implemented as a C++ class.      */
/************************************************************/
#ifndef QUEUE_H
#define QUEUE_H

typedef struct QueueItemType
	{
	int                    ivar;
	char                   dataArray[25];
	struct  QueueItemType  *next;
	} QueueItem;

class Queue
{
	private:
		QueueItem  *head;
		QueueItem  *tail;

	private:
		char *PQStringDup(char *source);
	public:
		Queue();
		~Queue();
		int  QueueEmpty();
		int  QueueFull();
		void Enqueue(int ival, char *str);
		QueueItem *Dequeue();
		void PrintQueue();
};

#ifndef FALSE
#define FALSE (0)
#endif

#ifndef TRUE
#define TRUE (!FALSE)
#endif

#endif

Queue.cpp

C++ Linked Implementation

/************************************************************/
/* File: Queue.c                                            */
/*                                                          */
/* Implementation file for C++ queue demonstration.         */
/* Author: Dr. Rick Coleman, CS 207 Instructor              */
/* Date: June 2001                                          */
/************************************************************/
#include "Queue.h"
#include <iostream.h>
#include <stdlib.h>
#include <string.h>

/***********************************/
/* Queue                           */
/* Class constructor.              */
/***********************************/
Queue::Queue()
{
	head = tail = NULL;
}

/***********************************/
/* ~Queue                          */
/* Class destructor.               */
/***********************************/
Queue::~Queue()
{
	QueueItem *temp;

	if(head != NULL) /* Free any existing list */
	{
		temp = head;
		while(temp != NULL)
		{
			temp = head->next;
			free(head);
			head = temp;
		}  
	}
}

/***********************************/
/* QueueEmpty()                    */
/* Check to see if the queue is    */
/*     empty.                      */
/***********************************/
int Queue::QueueEmpty()
{
	return(head == NULL);
}

/***********************************/
/* QueueFull()                     */
/* Check to see if the queue is    */
/*     full.                       */
/***********************************/
int Queue::QueueFull()
{
	return(FALSE); /* Assume linked queue can't be full */
}

/***********************************/
/* Enqueue()                       */
/* Add an item to the queue.       */
/***********************************/
void Queue::Enqueue(int ival, char *str)
{
	QueueItem *temp;

	/* Create a new QueueItem and set the fields */
	temp = (QueueItem *)malloc(sizeof(QueueItem));
	temp->ivar = ival;
	strcpy(temp->dataArray, str);
	temp->next = NULL;

	/* Insert into the queue */
	if(head == NULL)	/* Insert as first in the queue */
		head = tail = temp;
	else /* Insert at tail of the queue */
	{
		tail->next = temp;
		tail = temp;
	}
}

/***********************************/
/* Dequeue()                       */
/* Return a pointer to a the first */
/*   item in the list.  Note that  */
/*   the next field is set to NULL */
/*   before returning to avoid     */
/*   giving the caller access to   */
/*   the queue.                    */
/***********************************/
QueueItem *Queue::Dequeue()
{
	QueueItem *temp;

	if(QueueEmpty()) return(NULL);	/* Queue is empty */
	else
	{
		temp = head;
		head = head->next;
		if(head == NULL) tail = NULL;
		temp->next = NULL;
		return(temp);
	}
}

/***********************************/
/* PrintQueue()                    */
/* Print all items in the queue.   */
/***********************************/
void Queue::PrintQueue()
{
	QueueItem *temp;

	if(QueueEmpty())
		cout << "There are no items in the queue.\n";	
	else
	{
		cout << "\nQueue Contents:\n";
		cout << "-----------------------------------------\n";
		cout << "Int Value    String\n";
		temp = head;
		while(temp != NULL)
		{
			cout << temp->ivar << "\t\t" << temp->dataArray 
						<< "\n";
			temp = temp->next;
		}
		cout << "\n";
	}
}

QueueMain.cpp

C++ Linked Implementation

/************************************************************/
/* File: QueueMain.c                                        */
/*                                                          */
/* Implementation of a simple Queue abstract data type as a */
/*    linked ADT.                                           */
/* Author: Dr. Rick Coleman, CS 207 Instructor              */
/* Date: June 2001                                          */
/************************************************************/
#include "Queue.h"
#include <iostream.h>
#include <stdlib.h>

void PrintQItem(QueueItem *QItem);

main()
{
	Queue		*theQ;
	QueueItem	*QI;
	char		ch;
	
	/* Initialize the queue */
	theQ = new(Queue);

	/* Enqueue some items */
	theQ->Enqueue(1, "Queue Item 1");
	theQ->Enqueue(2, "Queue Item 2");
	theQ->Enqueue(3, "Queue Item 3");

	/* Print what is in the queue */
	theQ->PrintQueue();
	cout << "Press any key then Enter to continue";
	cin >> ch;	 /* Pause, let user see display before going on */

	/* Enqueue some more items */
	theQ->Enqueue(4, "Queue Item 4");
	theQ->Enqueue(5, "Queue Item 5");

	/* Print what is in the queue */
	theQ->PrintQueue();
	cout << "Press any key then Enter to continue";
	cin >> ch;	

	/* Dequeue and print some items */
	QI = theQ->Dequeue();
	PrintQItem(QI);
	QI = theQ->Dequeue();
	PrintQItem(QI);
	cout << "Press any key then Enter to continue";
	cin >> ch;	

	
	/* Print what is in the queue */
	theQ->PrintQueue();
	cout << "Press any key then Enter to continue";
	cin >> ch;	

	/* Dequeue and print some more items */
	QI = theQ->Dequeue();
	PrintQItem(QI);
	QI = theQ->Dequeue();
	PrintQItem(QI);

	/* Print what is in the queue */
	theQ->PrintQueue();
	cout << "Press any key then Enter to continue";
	cin >> ch;	

	/* Empty the queue */
	QI = theQ->Dequeue();
	PrintQItem(QI);
	QI = theQ->Dequeue();
	PrintQItem(QI);

	/* Print what is in the queue */
	theQ->PrintQueue();

		return(0);
}

/********************************************************/
/* Function: PrintQItem()                               */
/* Purpose:  Print data in a single item from a queue.  */
/* Args:     QItem - Pointer to a QueueItem structure.  */
/* Returns:  void                                       */
/********************************************************/
void PrintQItem(QueueItem *QItem)
{
	if(QItem == NULL)
		cout << "Queue item is empty.\n";
	else
		cout << "Queue data: " << QItem->ivar
				<< QItem->dataArray << "\n";
}