CS 2213/2211 -- Recitation 10

CS 2213/2211
Advanced Programming
Spring 2005
Recitation 10: Linked list queue
    Week 10: Mar 29-31
Due (on time): 2005-04-05  23:59:59
Due (late):        2005-04-10  23:59:59

Recitation 10 should be submitted following directions at: submissions with deadlines

2005-04-05 23:59:59 (that's Tuesday, 5 April 2005, 11:59:59 pm) for full credit.
2005-04-10 23:59:59 (that's Sunday, 10 April 2005, 11:59:59 pm) for 75% credit.

Introduction: This recitation works on areas:

Structs and pointers to structs.
Self-reference in structs.
Creating and using linked lists.
Use of recursion.

Overview: This recitation asks you to create a queue using linked lists, rather than a circular array. For reference, you can refer to an implementation of a stack using a linked list: Linked List Stack. You will also be asked to write several recursive functions.

A. Create a queue using linked lists: Here are the requirements for this part:

Requirements for Part A

Requirements for Part A
Use an implementation file `queue.c` and a header file `queue.h`, along with a program to test the queue `queue_test.c`. Use linked lists for the implementation in `queue.c`, but there should be no way to know the method of implementation from outside this file. I suggest that you use two pointers to list nodes: `front` and `rear` to represent the queue itself. An empty queue might be signified by the initial condition `front == NULL`. (It is permissible to determine an empty queue in a different way if you want.) Items are inserted in the queue at the rear, so that in the picture below, the character `'d'` was the last item inserted. Items are removed from the queue at the front, so `'a'` would be the next item removed from the queue below. In case of a deletion, the storage for the node should be freed. You should check for underflow, that is, attempting to remove an item from an empty queue. You can partly model your code after the linked list stack above. You will probably need to handle insertion into an empty queue as a special case. As in the stack above, you should check whether the `malloc` function fails to get storage, signalled by returning a null pointer. (In practice, we would not expect this to happen.)

Use an implementation file queue.c and a header file queue.h, along with a program to test the queue queue_test.c.
Use linked lists for the implementation in queue.c, but there should be no way to know the method of implementation from outside this file.
I suggest that you use two pointers to list nodes: front and rear to represent the queue itself. An empty queue might be signified by the initial condition front == NULL. (It is permissible to determine an empty queue in a different way if you want.)
Items are inserted in the queue at the rear, so that in the picture below, the character 'd' was the last item inserted. Items are removed from the queue at the front, so 'a' would be the next item removed from the queue below.
In case of a deletion, the storage for the node should be freed.
You should check for underflow, that is, attempting to remove an item from an empty queue.
You can partly model your code after the linked list stack above. You will probably need to handle insertion into an empty queue as a special case.
As in the stack above, you should check whether the malloc function fails to get storage, signalled by returning a null pointer. (In practice, we would not expect this to happen.)

Here is a diagram showing what the queue should look like:

B. Add printing functions and a test program: Here are the requirements for this part:

Requirements for Part B

Requirements for Part B
Add three functions to the `queue.c` file that will print the queue: from front to rear, recursively from front to rear, and recursively from rear to front. For this you can mimic similar functions in the stack implementation above. Add a file `queue_test.c` that will test the queue using a command interpreter similar to the one in the stack implementation. Use essentially the same inputs used to test the stack.

Add three functions to the queue.c file that will print the queue:
- from front to rear,
- recursively from front to rear, and
- recursively from rear to front.
For this you can mimic similar functions in the stack implementation above.
Add a file queue_test.c that will test the queue using a command interpreter similar to the one in the stack implementation.
Use essentially the same inputs used to test the stack.

What you should submit: Refer to the submissions directions and to deadlines at the top of this page. The text file that you submit should first have Your Name, the Course Number, and the Recitation Number. The rest of the file should have the following in it, in the order below, and clearly labeled, including at the beginning the appropriate item letters: a, b, c, etc.

Contents of email submission for Recitation 10:
Last Name, First Name; Course Number; Recitation Number.
a. Give code for the three files queue.c, queue.h and queue_test.c.
b. Give results of a run similar to the run for the stack.

Revision date: 2005-03-31. (Please use ISO 8601, the International Standard.)