概述
利用 C 语言实现一个队列的基本功能，包括：
- 创建队列
- 销毁队列
- 头部入队
- 尾部入队
- 头部出队
- 获取队列长度
- 反转队列
核心在于每次对队列操作前都要考虑是否为空的情况，保证代码的鲁棒性。
头文件
#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);可以看到，在源文件的基础上，新增了尾节点和队列大小两个属性，当然也可以不加，但如果没有这两个变量，计算队列大小或者进行尾部入队操作的时间复杂度就不是常量了，而是线性增长的。
下面我们具体看每个函数的实现。
创建队列
/** * @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; }}这一步没什么问题，主要就是分配队列空间并初始化队列的各个属性。
销毁队列
/** * @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}如上所述，判断完队列是否为空，还需要判断队列的属性是否为空。
头部入队
/** * @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; } }}除了判断队列及队列元素是否为空，还要判断malloc()是否成功，
正常来讲，内存分配成功的话，会返回一个可以指向任意类型的指针，但该指针必须通过free()或者realloc()回收。
如果分配失败了，会返回一个空指针，我们需要对其进行判断。
尾部入队
/** * @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; } }}这一步和头部入队类似，不同点在于需要对尾节点是否存在进行判断，而头部入队时是不需要判断头节点是否存在的，因为必然要进行重新分配且不需要对其执行查找下一个节点的操作。
头部出队
/** * @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;}这里注意一下strncpy的用法就好了，要保证buf是 C-Style 的字符数组。
获取队列长度
/** * @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; }}这没什么好说的，在前面执行入队、出队的时候不要忘记修改size的值就可以，这里只需要直接返回，而不需要通过遍历队列的方式去计算。
反转队列
/** * @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; }}经典的反转链表，这里就不赘述了。
测试
一共是提供了十五组测试用例，满分一百，包括了对各个函数及其性能的测试(测试尾部入队 10000 个元素) ，还有鲁棒性测试（释放空队列的空间，从空队列中移除头部元素等），还是比较全面的。