A Queue implemented as an array in C


Header file for a queue
//---------------------------------------------------------------
// File: Code130_Queue.h
// Purpose: Header file for a demonstration of a queue implemented 
//        as an array.  Data type: Character
// Programming Language: C
// Author: Dr. Rick Coleman
//---------------------------------------------------------------
#ifndef CODE130_QUEUE_H
#define CODE130_QUEUE_H

#include <stdio.h>

#define MAX_SIZE    25        // Define maximum length of the queue

// List Function Prototypes
void InitQueue();             // Initialize the queue
void ClearQueue();            // Remove all items from the queue
int Enqueue(char ch);         // Enter an item in the queue
char Dequeue();               // Remove an item from the queue
int isEmpty();                // Return true if queue is empty
int isFull();                 // Return true if queue is full

// Define TRUE and FALSE if they have not already been defined
#ifndef FALSE
#define FALSE (0)
#endif
#ifndef TRUE
#define TRUE (!FALSE)
#endif

#endif // End of queue header

Implementation (.c) file for a queue
//---------------------------------------------------------------
// File: Code130_Queue.c
// Purpose: Implementation file for a demonstration of a queue  
//		implemented as an array.    Data type: Character
// Programming Language: C
// Author: Dr. Rick Coleman
// Date: February 11, 2002
//---------------------------------------------------------------
#include "Code130_Queue.h"

// Declare these as static so no code outside of this source
// can access them.
static int head, tail;	// Declare global indices to head and tail of queue
static char theQueue[MAX_SIZE];	// The queue

//--------------------------------------------
// Function: InitQueue()
// Purpose: Initialize queue to empty.
// Returns: void
//--------------------------------------------
void InitQueue()
{
	head = tail = -1;
}

//--------------------------------------------
// Function: ClearQueue()
// Purpose: Remove all items from the queue
// Returns: void
//--------------------------------------------
void ClearQueue()
{
	head = tail = -1; // Reset indices to start over
}

//--------------------------------------------
// Function: Enqueue()
// Purpose: Enqueue an item into the queue.
// Returns: TRUE if enqueue was successful
//		or FALSE if the enqueue failed.
// Note: We let head and tail continuing 
//		increasing and use [head % MAX_SIZE] 
//		and [tail % MAX_SIZE] to get the real
//		indices.  This automatically handles
//		wrap-around when the end of the array
//		is reached.
//--------------------------------------------
int Enqueue(char ch)
{
	// Check to see if the Queue is full
	if(isFull()) return FALSE;

	// Increment tail index
	tail++;
	// Add the item to the Queue
	theQueue[tail % MAX_SIZE] = ch;
	return TRUE;
}

//--------------------------------------------
// Function: Dequeue()
// Purpose: Dequeue an item from the Queue.
// Returns: TRUE if dequeue was successful
//		or FALSE if the dequeue failed.
//--------------------------------------------
char Dequeue()
{
	char ch;

	// Check for empty Queue
	if(isEmpty()) return '\0';  // Return null character if queue is empty
	else
	{
		head++;
		ch = theQueue[head % MAX_SIZE];		// Get character to return
		return ch;				// Return popped character
	}
}

//--------------------------------------------
// Function: isEmpty()
// Purpose: Return true if the queue is empty
// Returns: TRUE if empty, otherwise FALSE
// Note: C has no boolean data type so we use
//	the defined int values for TRUE and FALSE
//	instead.
//--------------------------------------------
int isEmpty()
{
	return (head == tail);
}

//--------------------------------------------
// Function: isFull()
// Purpose: Return true if the queue is full.
// Returns: TRUE if full, otherwise FALSE
// Note: C has no boolean data type so we use
//	the defined int values for TRUE and FALSE
//	instead.
//--------------------------------------------
int isFull()
{
	// Queue is full if tail has wrapped around
	//	to location of the head.  See note in
	//	Enqueue() function.
	return ((tail - MAX_SIZE) == head);
}

Main file used to test the queue
//---------------------------------------------------------------
// File: QueueMain.c
// Purpose: Main file with tests for a demonstration of a queue 
//		as an array.
// Programming Language: C
// Author: Dr. Rick Coleman
// Date: February 11, 2002
//---------------------------------------------------------------
#include "Code130_Queue.h"
#include 

int main(int argc, char **argv)
{
	char	testString[MAX_SIZE + 2];
	int		i;
	char	ch;

	printf("Simple Queue Demonstration\n");
	printf("(Queue implemented as an Array - Queue data type is character.)\n\n");
	printf("Creating a queue\n");

	InitQueue();
	printf("Queue created...\n");

	// Test enqueuing and dequing item on a queue
	printf("Testing enqueue and dequeue of single item.\n");
	Enqueue('A');
	printf("Enqueued: %c\n", Dequeue());
	printf("...done\n\n");

	// Test queue by enqueing letters in a string
	strcpy(testString, "abcdefghijklmnopqrasuvwxyz"); 

	// Try to Enqueue all letters in the string
	i = 0;
	printf("Testing enqueuing of string: %s\n", testString);
	while(testString[i] != '\0')
	{
		if(!Enqueue(testString[i]))
		{
			printf("Queue is full. Unable to enqueue %c\n", testString[i]);
		}
		i++;
	}

	printf("\n\nDone testing enqueue.\n\nNow testing dequeue.\n");
	// Dequeue letters and print them
	printf("Dequeued letters are...\n");
	while((ch = Dequeue()) != '\0') // Dequeue returns null terminator 
		printf("%c", ch);			// when queue is empty
	
	printf("\nEnd of queue encountered...\n");

	printf("\n\n...done.\n");
	return 0;
}