Overview

Implement basic queue functionality using C language, including:

Create queue
Destroy queue
Insert at head
Insert at tail
Remove from head
Get queue length
Reverse queue

The key is to consider whether the queue is empty before each operation to ensure code robustness.

Header File

#include <stdbool.h>
#include <stddef.h>

/* element struct in queue */
typedef struct list_ele {
    char *value;
    struct list_ele *next;
} list_ele_t;

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size; // use the above two variable to record the size of the queue to avoid traversal
} queue_t;

/* Create empty queue. */
queue_t *queue_new(void);

/* Free ALL storage used by queue. */
void queue_free(queue_t *q);

/* Attempt to insert element at head of queue. */
bool queue_insert_head(queue_t *q, const char *s);

/* Attempt to insert element at tail of queue. */
bool queue_insert_tail(queue_t *q, const char *s);

/* Attempt to remove element from head of queue. */
bool queue_remove_head(queue_t *q, char *sp, size_t bufsize);

/* Return number of elements in queue. */
size_t queue_size(queue_t *q);

/* Reverse elements in queue */
void queue_reverse(queue_t *q);

As you can see, based on the source file, two new attributes were added: tail node and queue size. Of course, these could be omitted, but without these two variables, calculating queue size or performing tail insertion operations would not have constant time complexity, but linear growth.

Let’s look at the implementation of each function.

Create Queue

/**
 * @brief Allocates a new queue
 * @return The new queue, or NULL if memory allocation failed
 */
queue_t *queue_new(void) {
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL) {
        return NULL;
    } else {
        q->head = NULL;
        q->tail = NULL;
        q->size = 0;
        return q;
    }
}

This step is straightforward - mainly allocating queue space and initializing the queue’s attributes.

Destroy Queue

/**
 * @brief Frees all memory used by a queue
 * @param[in] q The queue to free
 */
void queue_free(queue_t *q) {
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if (q == NULL) {
        return;
    } else {
        list_ele_t *tmp;
        while (q->head != NULL) {
            tmp = q->head;
            q->head = q->head->next;
            free(tmp->value); // free element's value
            free(tmp) // free element itself
        }
    }
    free(q); // free queue
}

As mentioned above, after checking if the queue is empty, we also need to check if the queue’s attributes are empty.

Insert at Head

/**
 * @brief Attempts to insert an element at head of a queue
 *
 * This function explicitly allocates space to create a copy of `s`.
 * The inserted element points to a copy of `s`, instead of `s` itself.
 *
 * @param[in] q The queue to insert into
 * @param[in] s String to be copied and inserted into the queue
 *
 * @return true if insertion was successful
 * @return false if q is NULL, or memory allocation failed
 */
bool queue_insert_head(queue_t *q, const char *s) {
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    if (q == NULL) {
        return false;
    }
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        return false;
    } else {
        newh->value = malloc(sizeof(char) * (strlen(s) + 1));
        if (newh->value == NULL) {
            free(newh); // must free the space if malloc failed
            return false;
        } else {
            strcpy(newh->value, s);
            newh->next = q->head;
            q->head = newh;

            if (q->tail == NULL) {
                q->tail = newh;
            }
            ++q->size;
            return true;
        }
    }
}

Besides checking if the queue and queue elements are empty, we also need to check if malloc() succeeded. Normally, if memory allocation succeeds, it returns a pointer that can point to any type, but this pointer must be freed through free() or realloc(). If allocation fails, it returns a null pointer, which we need to check for.

Insert at Tail

/**
 * @brief Attempts to insert an element at tail of a queue
 *
 * This function explicitly allocates space to create a copy of `s`.
 * The inserted element points to a copy of `s`, instead of `s` itself.
 *
 * @param[in] q The queue to insert into
 * @param[in] s String to be copied and inserted into the queue
 *
 * @return true if insertion was successful
 * @return false if q is NULL, or memory allocation failed
 */
bool queue_insert_tail(queue_t *q, const char *s) {
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    list_ele_t *newt;
    /* What should you do if the q is NULL? */
    if (q == NULL) {
        return false;
    }
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newt = malloc(sizeof(list_ele_t));
    if (newt == NULL) {
        return false;
    } else {
        newt->value = malloc(sizeof(char) * (strlen(s) + 1));
        if (newt->value == NULL) {
            free(newt);
            return false;
        } else {
            strcpy(newt->value, s);
            newt->next = NULL;

            if (q->tail != NULL) {
                q->tail->next = newt;
                q->tail = newt;
            } else {
                q->head = newt;
                q->tail = newt;
            }
            ++q->size;
            return true;
        }
    }
}

This step is similar to head insertion, with the difference being that we need to check if the tail node exists. For head insertion, we don’t need to check if the head node exists because we always need to reallocate and don’t need to perform a search for the next node operation.

Remove from Head

/**
 * @brief Attempts to remove an element from head of a queue
 *
 * If removal succeeds, this function frees all memory used by the
 * removed list element and its string value before returning.
 *
 * If removal succeeds and `buf` is non-NULL, this function copies up to
 * `bufsize - 1` characters from the removed string into `buf`, and writes
 * a null terminator '\0' after the copied string.
 *
 * @param[in]  q       The queue to remove from
 * @param[out] buf     Output buffer to write a string value into
 * @param[in]  bufsize Size of the buffer `buf` points to
 *
 * @return true if removal succeeded
 * @return false if q is NULL or empty
 */
bool queue_remove_head(queue_t *q, char *buf, size_t bufsize) {
    if (q == NULL) {
        return false;
    }
    if (q->head == NULL) {
        return false;
    } else {
        list_ele_t *temp = q->head;
        q->head = q->head->next;
        if (buf != NULL) {
            strncpy(buf, temp->value, bufsize - 1);
            buf[bufsize - 1] = '\0';
        }
        free(temp->value);
        free(temp);
        --q->size;
    }
    return true;
}

Just pay attention to the usage of strncpy here - ensure that buf is a C-style character array.

Get Queue Size

/**
 * @brief Returns the number of elements in a queue
 *
 * This function runs in O(1) time.
 *
 * @param[in] q The queue to examine
 *
 * @return the number of elements in the queue, or
 *         0 if q is NULL or empty
 */
size_t queue_size(queue_t *q) {
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL) {
        return 0;
    } else {
        return q->size;
    }
}

Nothing special here - just don’t forget to modify the size value when performing enqueue and dequeue operations. Here we just need to return directly without calculating by traversing the queue.

Reverse Queue

/**
 * @brief Reverse the elements in a queue
 *
 * This function does not allocate or free any list elements, i.e. it does
 * not call malloc or free, including inside helper functions. Instead, it
 * rearranges the existing elements of the queue.
 *
 * @param[in] q The queue to reverse
 */
void queue_reverse(queue_t *q) {
    /* You need to write the code for this function */
    if (q == NULL || q->head == NULL) {
        return;
    } else {
        list_ele_t *oldHead = q->head;
        list_ele_t *oldTail = q->tail;

        list_ele_t *temp = q->head;
        list_ele_t *prev = NULL;
        list_ele_t *next = NULL;
        while (temp != NULL) {
            next = temp->next;
            temp->next = prev;
            prev = temp;
            temp = next;
        }
        q->head = oldTail;
        q->tail = oldHead;
    }
}

Classic linked list reversal - no need to elaborate.

Testing

Fifteen test cases were provided with a total score of 100, including tests for each function and their performance (testing tail insertion of 10,000 elements), as well as robustness tests (freeing space of empty queue, removing head element from empty queue, etc.). It’s quite comprehensive.

John Wick

CMU 15-213 Lab0