Queue Lab: Data Structures

Released: 12:00 AM Monday, February 10th, 2020.

Due: 11:59 PM Friday, February 21st, 2020.

Here, we will use our expertise of pointers to implement a simple linked list data structure.

Weight: 10% of your total 50% Lab Grade

Note: Start early enough to get through the more troublesome parts of debugging this one!

Note: You must use malloc and not use calloc nor realloc in this assignment!

Introduction

This assignment will give you practice in the finer aspects of C programming necessary to succeed in later assignments in this course. These skills include:

Explicit memory management (which C requires.)
Creating and manipulating data structures using pointers.
Working with strings.
Choosing an implementation of a data structure that has particular performance characteristics.
Properly handling error cases (such as when malloc returns NULL.)

To do this, we will implement a queue data structure. Such a data structure, as you should recall, supports fast insert and remove operations. In this case, we will implement the queue such that it provides both fast last-in-first-out (LIFO) and first-in-first-out (FIFO) capability.

As you might presume, to do this we will implement the queue using a singly linked list specifically implemented to make the queue operations efficient when we can.

Resources

Beyond the lecture material, which should help greatly, you may consult several online and offline resources.

C Programming - The C Programming Language (second edition) by Kernighan and Ritchie, which is a very recommended book. You may find copies on reserve in many libraries on campus. Chapters 5 and 6 are particularly relevant in the newest edition. A good online book is also C Programming by the editors of wikibooks.
Linked Lists - If you want alternative resources to my own lecture material, hunt down any current data structures course and review their notes there. For instance, the linked list slides by my friend Michael Lipschultz.
Asymptotic (big-Oh) notation - If you still need a refresher on what O(n) means, Vinicius recommends these Cornell lecture notes on the subject. It is indeed a great summation of the topic, albeit dense at the same time.
C Reference - Searching the internet for function names will get you a long way. Often it will point you to cppreference.com, which is a classic online manual for different functions.

Namely, you will want to refer to the specifics of the functions malloc and free. You are not permitted to use calloc or any alternative memory allocation function.

Also, be sure to review the behavior of string functions strlen, strcpy, and strncpy. This string guide lists each string function and a short description.

Hint: strncpy has strange behavior when truncating strings! It does not necessarily add a NULL terminator.

Note: Academic integrity means you cannot refer to any C linked-list implementation. If you submit a solution that resembles such an online example, you are likely in breach of that rule and may be subject to penalty.

Downloading

To get the boilerplate code and the testing harness for this assignment, use the following command on thoth:

wget https://wilkie.github.io/cs449/labs/03/queuelab-handout.zip

This will download the queuelab-handout.zip file to your (private) directory on the thoth Linux machine (make sure you are logged into this!) in which you will do your work.

Then issue the command:

unzip queuelab-handout.zip

This will cause a number of files to be unpacked in the directory queuelab-handout. Navigate to that directory and look at the files. The files you will be modifying are queue.c and queue.h. The queue.c file contains a skeleton for the functions that interact with your queue data structure. The queue.h file contains the function prototypes and the definition of the data structure.

Consult the README file for a more thorough description of the files and how to use them.

Implementation

The queue.h file contains declarations which define the following structures:

/* Linked list element */
typedef struct ELE {
    char* value;       /* The data held in our queue */
    struct ELE* next;  /* Next element in the list */
} list_ele_t;

/* Queue structure */
typedef struct {
    list_ele_t* head;  /* Linked list of elements */
} queue_t;

These two are combined to implement a queue of strings, as illustrated in the figure below. The top-level representation of a queue is a structure of type queue_t. In the starter code, this structure contains only a single field head, but you will likely want to add other fields. The queue contents are represented as a singly-linked list, with each element represented by the list_ele_t structure having fields value and next. The value field stores a pointer to a string. The next field storing the pointer to another list_ele_t element representing the next item in the list, or NULL when representing the end of the list. You may add fields to the list_ele_t structure, but there is not a need to do so to complete this lab for full credit.

The queue structure showing a queue with a head field pointing to several list nodes. Each node has a string pointer with some random string value. The final node, labelled tail, is pointing to NULL.

Recall that a string is represented in C as an array of char values. In essentially every modern machine, a char is represented as a single byte. To store a string of length l the array must be at least l + 1 in size. The first l elements storing the data of the string itself and the final element storing the null-terminator (a byte with the explicit value of 0.)

The value field of the list_ele_t is a pointer to such an array. The figure above shows the strings cab, bead, and cab represented as separate arrays. The values for each character come from the ASCII encoding where letters a through e are represented as hexadecimal values 0x61 through 0x65. Each list element should have its own unique copy of each string.

In our C code, a queue is a pointer of type queue_t*. We distinguish two special cases.

A NULL queue is one where the pointer has a value of NULL.
An empty queue is one where the queue pointer itself is valid, but the head field points to NULL.

Your code must deal with being passed a queue of either of these types along with, of course, a valid queue with one or more items.

Your turn

Your task is to modify both the queue.c and queue.h files to fully implement the following functions:

q_new - Create a new, empty queue.
q_free - Deallocate everything associated with the given queue.
q_insert_head - Attempt to add a new node to the beginning of the queue. (LIFO)
q_insert_tail - Attempt to add a new node to the end of the queue in O(1) time. (FIFO)
q_remove_head - Removes the head (first node) in the queue.
q_size - Returns the number of items currently in the queue in O(1) time.
q_reverse - Reverse the contents of the queue in place. That is, you cannot use any of the other functions nor deallocate/allocate nodes in the list.

Refer to the comments within queue.c for any guidance and rules for special cases for each function.

For functions that provide strings as arguments, you are expected to allocate and copy those strings to the list. You will use malloc to create the space required for the string and you can assume that the given string is well-formed (contains a null terminator). Therefore, you do not need to assume any upper-bound on the string size. Just write your code to work for any arbitrary string length.

Remember to account for null terminators in your string allocation!

Two functions, as indicated above, require an implementation that provides the performance characteristic of constant time: O(1). Doing this likely requires some thoughtful changes to the queue_t structure and careful additional work in other functions.

Your program will be tested on queues of over 1,000,000 elements. Therefore, recursive functions will not work because you will exhaust the alloted size of the stack. The OS only gives you so much of it! Instead, you will have to always use loops to traverse the items in your list.

Testing

We have graciously provided a Makefile for this lab. As such, you can compile your work as so:

make

If there are no errors, the compiler will generate several programs. One program is qtest which gives you an interactive interface in which to test your queue. You can create, modify, and examine a queue. Documentation on commands can be seen by running the qtest application and typing help:

./qtest
cmd> help

The following file (traces/trace-eg.cmd) illustrates an example command sequence:

# Demonstration of queue testing framework
# Use help command to see list of commands and options
# Initial queue is NULL.
show
# Create empty queue
new
# Fill it with some values.  First at the head
ih dolphin
ih bear
ih gerbil
# Now at the tail
it meerkat
it bear
# Reverse it
reverse
# See how long it is
size
# Delete queue.  Goes back to a NULL queue.
free
# Exit program
quit

You can use these commands yourself line-by-line with qtest or you can batch them from a file list this:

./qtest -f traces/trace-eg.cmd

With the starter code, you will see that many of these operations are not implemented properly.

The traces directory contains 15 trace files, with names of the form trace-k-cat.txt, where k is the trace number and cat specifies the category of properties being tested. Each trace consists of a sequence of commands, similar to those shown above. They test different aspects of the correctness, robustness, and performance of your program. You can use these, your own trace files, and direct interactions with qtest to test and debug your program.

Evaluation

Your program will be evaluated using the fifteen traces described above found in the traces directory of your handout package. You will be given credit (either 6 or 7 points, depending on the trace) for each one that executes correctly, summing to a maximum score of 100. This will be your score for the assignment, the grading being done completely automatically.

The driver program driver.py runs qtest on the traces and computes the score. This is the same program that will be used to compute your score with Gradescope. You can invoke the driver with the command:

make test

Submission

In a change of pace, you will upload two files: queue.c and queue.h and only these two files to Gradescope. You may submit as many times as you like until the due date.

Reflection

It is good to start this assignment early. C, like many things in life, takes practice. This assignment stresses the importance of careful and deliberate programming. Write short statements, do less on each line, and comment your code very liberally.

If you find yourself frustrated, take an hour away from it. Come back to it with a fresh point of view. Read the code over and what it does. Remember that the computer is going to do exactly what it is told, so do not read back what you think you wrote. Read what is actually there and if that is what you intended.

It may help to draw out a diagram of the data structure as you trace your own code. You might find yourself, as I did, going,

“Ah, right, I can’t assign cur = cur->next after I have done cur->next = last! I need to keep that pointer in a temp variable somewhere.”

Mastery does not mean you always get it right on the first try.