# 2019q1 Homework1 (lab0)
contributed by < `dianarolien` >

## 開發環境

Linux dianarolien-Aspire-E5-575G 4.18.0-15-generic #16~18.04.1-Ubuntu SMP Thu Feb 7 14:06:04 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

## 作業要求

:::danger
作業要求寫得很多，不是只有下方這件事，請重新閱讀指定材料並摘要
:notes: jserv
:::
[作業說明](https://hackmd.io/s/BJA8EgFB4) / [cprogramminglab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)

* 實驗目標為實作 queue

* first in, first out (FIFO)
* last in, first out (LIFO)

* 實作以下function:
* q_new : Create a new, empty queue.
* q_free : Free all storage used by a queue.
* q_insert_head : Attempt to insert a new element at the head of the queue.
* q_insert_tail : Attempt to insert a new element at the tail of the queue.
* q_remove_head : Attempt to remove the element at the head of the queue.
* q_size : Compute the number of elements in the queue.
* q_reverse : Reorder the list so that the queue elements are reversed in order.


* 解釋自動評分系統運作的原理
* 提及 qtest 的行為和裡頭的技巧
## 實作
### Queue structure

typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

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

### q_new
Create a new, empty queue.

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q != NULL) {
        q->head = NULL;
        q->tail = q->head;
        q->size = 0;
    }
    return q;
}

### q_free
Free all storage used by a queue.

void q_free(queue_t *q)
{
    if (q == NULL)
        return;

    /* How about freeing the list elements and the strings? */
    if (q->head != NULL) {
        list_ele_t *p = q->head;
        list_ele_t *n = q->head->next;
        while (p != NULL) {
            free(p->value);
            free(p);
            p = n;
            if (n != NULL)
                n = n->next;
        }
    }
    /* Free queue structure */
    free(q);
}

### q_insert head
Attempt to insert a new element at the head of the queue (LIFO discipline).

bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if (q == NULL)
        return false;
   
   /* What if either call to malloc returns NULL? */
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    newh->value = (char *) malloc((strlen(s) + 1) * sizeof(char));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s) + 1);
    newh->next = q->head;
    q->head = newh;
    q->size += 1;
    if (q->tail == NULL)
        q->tail = newh;
    return true;
}

### q_insert_tail
Attempt to insert a new element at the tail of the queue (FIFO discipline).

bool q_insert_tail(queue_t *q, char *s)
{
    /* Remember: It should operate in O(1) time */
    if (q == NULL)
        return false;

    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    newh->value = (char *) malloc((strlen(s) + 1) * sizeof(char));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s) + 1);
    newh->next = NULL;
    if (q->tail != NULL)
        q->tail->next = newh;
    q->tail = newh;
    if (q->head == NULL)
        q->head = newh;
    q->size += 1;
    return true;
}

### q_remove_head
Attempt to remove the element at the head of the queue.

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL)
        return false;
    if (q->head == NULL)
        return false;

    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    if (sp != NULL) {
        strncpy(sp, tmp->value, bufsize - 1);
        sp[bufsize - 1] = 0;
    }
    free(tmp->value);
    free(tmp);
    q->size -= 1;
    if (q->size == 0)
        q->tail = NULL;
    return true;
}

### q_size
Compute the number of elements in the queue.

int q_size(queue_t *q)
{
    if (q != NULL)
        return q->size;
    return 0;
}

### q_reverse
Reorder the list so that the queue elements are reversed in order.
This function should not allocate or free any list elements ( either directly or via calls to other functions that allocate or free list elements.).
Instead, it should rearrange the existing elements.

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q == NULL)
        return;
    if (q->head == NULL)
        return;

    list_ele_t *p = NULL;
    list_ele_t *t = q->head;
    list_ele_t *r = q->head->next;
    while (t != NULL) {
        t->next = p;
        p = t;
        t = r;
        if (r != NULL)
            r = r->next;
    }
    q->tail = q->head;
    q->head = p;
}

## 自動評分系統運作的原理
## qtest 的行為和裡頭的技巧