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;
}