CS 127, Assignment #2

This assignment is due by 11:10 AM, Wednesday, January 17. Submit it using HSP.

The Assignment

For this assignment, you will implement a simple queue abstract data type. An object of type Queue will consist of a structure containing two pointers, named front and back. If both front and back are NULL, then the queue is empty. Otherwise, front will point to the first node in a linked list of nodes of type QueueNode, and back will point to the last node in the same linked list.

The following function prototypes will be your Queue.h file. Your job is to write (and debug and test, of course) the corresponding Queue.c file. You may not add to Queue.h. (This does not mean that you may not create extra functions to help you implement the functions listed in Queue.h, only that those extra functions are internal only, and invisible to the program that #include's Queue.h.) Like last time, I do not want you to hand in a main() function, even one that is commented out. Since you will use the same Queue.h that I am using, you should only hand in Queue.c.

Note that I have made the queue in this assignment be a queue of characters (since QueueData is defined as a synonym for char). This is for simplicity only. Your code should assume nothing about the nature of QueueData.


typedef      char         QueueData;
 
typedef struct QueueNode
{
      QueueData           data;
      struct QueueNode    *next;
} QueueNode;
 
typedef struct
{
      QueueNode           *front;
      QueueNode           *back;
} Queue;
 
 
 
/*  InitializeQueue() initializes the queue to empty.  */
 
void InitializeQueue( Queue *theQueue );
 
 
/*  FlushQueue() frees all the nodes in the queue, and sets
    the queue to empty. */
 
void FlushQueue( Queue *theQueue );
 
 
/*  AddToQueue() creates a new node with data equal to
    newItem, and adds that node to the end of the queue. */
    
void AddToQueue( Queue *theQueue, QueueData newItem );
 
 
/*  ServeFromQueue() deletes the node at the front of the
    queue, frees the memory associated with that node,
    and returns the data from that node.  If the queue started
    out empty,  ServeFromQueue() will not crash the program,
    but it will feel free to return garbage.  The calling routine
    is responsible for checking to make sure the queue is not
    empty before calling ServeFromQueue().  */
    
QueueData ServeFromQueue( Queue *theQueue );
 
 
/*  QueueLength() returns the number of nodes in the queue. */
 
int QueueLength( const Queue *theQueue );
 
 
/*  QueueIsEmpty() returns 0 (false) if the queue is not empty, and
    some non-zero value (true) if the queue is empty.  */
 
int QueueIsEmpty( const Queue *theQueue );

Advice

Before you sit down and start typing, you should think about the order in which you plan to implement the pieces of your project, and how you are going to test those pieces. I usually write down an implementation and testing schedule for myself. The first thing on the schedule is always some function that allows me to look at the data structure I am manipulating, so for this project, I would first write a PrintQueue() function so I could see the state of my queue at any time, and I'd test this function by setting up a queue in the same way I did in class Friday. Then I would implement InitializeQueue() and AddToQueue(), and test them. Then ServeFromQueue(), and test its interaction with AddToQueue(). Finally, I'd knock off the last three functions, which by now would be comparatively easy.

Note that FlushQueue() will be tough to test. There's no simple way to determine whether you have properly freed all the memory you allocated, though putting a printf() next to every malloc(), and another printf() next to every free() gives you a pretty good idea.

Save copies of your work. If you get a function working, hide a copy of it far away from your impulsively editing fingers. Save copies of your work. Save copies of your work.

There's an old saying about marriage that you should never go to bed angry with each other. This is good advice, though pretty much impossible to hold to perfectly. I would say something similar about working on a programming project. Never go to bed with a program that doesn't compile and run, even if it doesn't do much.

That said, let me add that I recommend starting the project early enough that there is time for going to bed before the due date.

Start early, keep in touch, and have fun.

Jeff Ondich, Department of Mathematics and Computer Science, Carleton College, Northfield, MN 55057
(507) 663-4364, jondich@carleton.edu