Array-Based Queues
Summary: This laboratory exercise introduces the concept of the queue abstract data type and provides experience implementing this ADT with an array.
Queues ADT
The reading on queues describes the queue ADT with the following operations:
-
initialize
Initializescount
as 0,first
as 0, andlast
asMAX_QUEUE_SIZE-1
. (See enqueue for why you setlast
to this value and not -1.) -
isEmpty
Determine whether the queue is empty; return true if it is and false if it is not. -
isFull
Determine whether the queue is full; return true if it is and false if it is not. -
enqueue
Add a new element at the rear of a queue. (When you add a new element, you will first incrementlast
and may need to reset to 0 if last equalsMAX_QUEUE_SIZE
. Or use modular arithmetic to keep the value within range. ) -
dequeue
Remove an element from the front of the queue and return it. (This operation cannot be performed if the queue is empty. You will also need to keep the value within range, similar to the enqueue function.) -
front
Return the element at the front of the queue without removing it from the queue. (Again, this operation cannot be performed if the queue is empty.)
In this lab, we will focus on arrays of strings, which leads to the following declarations for queues:
#define MAX_QUEUE_SIZE 50
/* size of all queue arrays */
typedef struct {
int first;
int last;
int count;
char * queueArray[MAX_QUEUE_SIZE];
} stringQueue;
With this framework, the signatures for the various queue operations might be as follows:
void
initialize (stringQueue * queue);
bool
isEmpty (const stringQueue * queue);
bool
isFull (const stringQueue * queue);
bool
enqueue (stringQueue * queue, char * item);
/* returns whether item was successfully enqueued */
char *
dequeue (stringQueue * queue);
/* returns string removed from queue */
char *
front (const stringQueue* queue);
Additional implementation notes are found in the reading on queues.
Exercises
-
Create a directory for this lab in your directory for this class, and
move to the lab directory. For example:
mkdir queues cd queues
-
Copy the declarations the array-based queue ADT given above to a
header file called
arrayQueue.h
.- Remember to cite the origin of your code.
-
Add an
#ifndef
include "guard" to avoid repeated declarations
-
Write an implementation of a queue of strings by implementing
these operations in a program file called
arrayQueue.c
. -
Perhaps using the
Makefile
from the previous reading on program management as an example, create aMakefile
with a rule for compiling an object file (.o
) of your array-based queue. Be sure to include all the relevant file dependencies. -
After writing functions, it is important to test your code to
ensure that it works as you expected and accounts for unusual
cases.
-
Create a test driver program
called
testArrayQueue.c
with amain
function. -
Add two more rules to your
Makefile
: one to compile an object file for your driver, and another to link the two object files. Test thatmake
properly compiles and links all three targets. - Complete thorough tests of each operation in your code.
-
Create a test driver program
called
-
Add to your queue ADT an additional function
print
that displays each of the elements of the queue on a separate line (without actually removing any of them from the queue). Add code to your driver program that tests the functionality of the new function. -
Frequently we wish to clear the contents of a data structure like a
queue.
-
Implement the following function to remove all the items from the
queue.
void clear (stringQueue * queue);
-
Write tests to verify your
clear
procedure seems to function properly.
-
Implement the following function to remove all the items from the
queue.
-
Run
AddressSanitizer
over your test program to verify it does not have any memory problems. Eliminate any it finds.