Homework 6 - Implementing a queue as a linked list

Homework 6
Implementing a queue as a linked list

Due: Tuesday, December 11 at 11:59pm

Outcomes

After successfully completing this assignment, you will be able to...

Implement a data structure using several levels of abstraction
Construct a makefile for a program with multiple dependencies
Demonstrate an understanding of linked list and queue operations

Before Starting

Read Chapter 12 (12.1 - 12.6)

The Assignment

For this assignment, you are provided with a library of linked list operations defined in the files linktool.h and linktool.c. You should use the linked list operations defined in this library to implement the queue operations enqueue, dequeue, and isEmpty. You should demonstrate that your implementations work by defining a short test program that allows the user to enqueue and dequeue items, and to test to see if a queue is empty or not. I suggest you follow these steps:

Create a directory to hold your hw6 files, and make that directory your current one. Copy the Homework 6 files into your directory with this Unix command:
```
cp /cs/cs2301-b07/hw/hw6/* .
```
Compile linktool.c.
Make sure you understand the code in the files linktool.h and linktool.c before proceeding.
Create two new files, queue.h and queue.c. queue.h should contain the pre- and post-conditions, and the prototypes, for the three queue operations enqueue, dequeue, and isEmpty. queue.c should contain the function definitions for the three queue operations. Your functions should be defined in terms of linked list operations as much as possible (in other words, make calls to the functions defined in linktool.h and linktool.c instead of duplicating that code in your queue function definitions). Compile queue.c.
Create a short test program called hw6.c that calls each of the queue operations. Your test program should show that the queue behaves properly (for example, if you enqueue several items, then dequeue and print each item, the items should be printed in the same order as they were enqueued). Compile hw6.c.
Now is probably a good time to define your makefile for this program. It's usually helpful to draw a dependency diagram first. Create your makefile and use it to create your executable file.
Test your program, and turn it in once you get it to run correctly.

Include files

stdio.h
stdlib.h provides malloc, free

You will also need to include header files that you define for this project.

Deliverables

You should turn in your queue files, your test program, and your makefile. Submit your files using the following turnin command:

/cs/bin/turnin submit cs2301 hw6 makefile queue.h queue.c hw6.c

Programs submitted after 11:59pm on December 11 will be tagged as late, and will be subject to the late homework policy.

Grading

This assignment will be graded on the following areas: documentation (including pre- and post-conditions for any functions), correctness of the makefile, use of linked list functions in the queue implementations, and correctness. Programs must compile successfully in order to receive points for correctness.