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
  Initializes count as 0, first as 0, and last as MaxQueue-1.
• create
  Create a new, empty queue object.
• 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.
• dequeue
  Remove an element from the front of the queue and return it. (This operation cannot be performed if the queue is empty.)
• 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, and this leads to the following declarations for queues:

/* size of all queue arrays */
#define MaxQueue 50

typedef struct {
  int first;
  int last;
  int count;
  char* items[MaxQueue];
} stringQueue;

With this framework, the signatures for the various queue operations might be as follows:

void
initialize(stringQueue* queue);

int
isEmpty(const stringQueue* queue);

int
isFull(const stringQueue* queue);

int
enqueue(stringQueue* queue, char* item);
/* returns length of string added or -1 if queue is full */

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

0. Create a directory for this lab in your directory for this class, and move to the lab directory. For example:

   mkdir queues
   cd queues

1. 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
2. Write an implementation of a queue of strings by implementing these operations in a program file called arrayQueue.c.
3. Perhaps using the Makefile from the previous reading on program management as an example, create a Makefile with a rule for compiling an object file (.o) of your array-based queue. Be sure to include all the relevant file dependencies.
4. After writing functions, it is important to test your code to ensure that it works as you expected and accounts for unusual cases.
   1. Create a test driver program called testArrayQueue.c with a main function.
   2. 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 that make properly compiles and links all three targets.
   3. Complete thorough tests of each operation in your code.
5. 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.
6. When calling dequeue In our current formulation, we cannot distinguish an empty queue from an null string pointer (which may have been enqueued). An alternative approach for the dequeue function would add a parameter item to the list of parameters and change the return type to an int type. The idea is that the string would be returned as a parameter char* item and the procedure would return the length of the string item or -1 if the queue was empty. The relevant procedure signature might be:

   int
   dequeue(stringQueue* queue, char** item)

   and this procedure would be called within the context:

   char* frontItem;
   int returnValue;
   stringQueue myQueue;
   ...
   returnValue = dequeue (&myQueue, &frontItem)

   1. The parameter item has type char**, and the call to queue includes &frontItem. Explain why ** and & are needed here.
   2. Write this alternative version of the dequeue operation.