JMU logo

Homework 3

The goal of this homework is to give you practice with stacks, queues, and linked lists. All of the problems are from labs 9 and 10, so if you completed those labs you should be able to just copy/paste your solutions into the provided hw3.c file.

Starter Files

You should put your code for this homework into a file named hw3.c, that should compile against our hw3.h. If you wish, you may start from our boilerplate files:

The boilerplate archives include a main.c and a testsuite.c (for testing your other functions). You will only need to submit hw3.c.

For the palindrome problem you will use two dynamic arrays, one as a stack and one as a queue. These are already implemented for you in the dynarray_t type:

Here is a quick reference to the functions we provided for dealing with dynamic arrays:

typedef dynarray_t;                                     
// dynamic array struct

/* Basic/common operations */

void   dynarray_init    (dynarray_t *a);                
// initialize struct

void   dynarray_free    (dynarray_t *a);                
// free struct
size_t dynarray_size    (dynarray_t *a);                
// return element count
size_t dynarray_is_empty(dynarray_t *a);                
// return true if empty

/* Stack operations */

void   dynarray_push(dynarray_t *a, data_t item);       
// add to back
data_t dynarray_pop (dynarray_t *a);                    
// remove from back
data_t dynarray_top (dynarray_t *a);                    
// return back

/* Queue operations */

void   dynarray_enqueue(dynarray_t *a, data_t item);    
// add to back
data_t dynarray_dequeue(dynarray_t *a);                 
// remove from front
data_t dynarray_front  (dynarray_t *a);                 
// return front

In addition, you may find the following function from ctype.h useful:


Use a stack and queue (using the dynarray_t structure) to implement a more powerful version of the is_palindrome()function from an earlier lab. As a reminder, this function implements simple palindome verification. Here is the signature and documentation for the function which is declared in hw3.c:

For this homework, you should make the function more flexible than the version you wrote for the earlier lab. Your new solution should ignore whitespace and punctuation, and all comparisons should be case-insensitive. Include some tests in your main function. Examples of valid palindromes:

Singly-Linked List Exercises

For the remaining exercises you will implement the following singly-linked list functions which use the sllist_t and slnode_t types defined in hw3.h:

Contact chaoaj[at] for more information about this page or Twitter: @chaoaj