# 2019q1 Homework1 (lab0)
contributted by < [`chengWei1123`](https://github.com/chengWei1123) >
## 開發環境

$ uname -a
Linux wei-X550JX 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

$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

## 作業要求
實作以下 LIFO FIFO Queue 之功能
* ***q_new***
* Create empty queue.
* Return NULL if could not allocate space.

* ***q_free***
* Free ALL storage used by queue.
* No effect if q is NULL.

* ***q_insert_head***
* Attempt to insert element at head of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.

* ***q_insert_tail***
* Attempt to insert element at tail of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
* ***q_remove_head***
* Attempt to remove element from head of queue.
* Return true if successful.
* Return false if queue is NULL or empty.
* If sp is non-NULL and an element is removed, copy the removed string to sp
(up to a maximum of bufsize-1 characters, plus a null terminator.)
* The space used by the list element and the string should be freed.
* ***q_size***
* Return number of elements in queue.
* Return 0 if q is NULL or empty

* ***q_reverse***
* Reverse elements in queue
* No effect if q is NULL or empty
* This function should not allocate or free any list elements
(e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
* It should rearrange the existing ones.

* **詳細說明 :**

* [作業說明](https://hackmd.io/s/BJA8EgFB4)
* [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
## 實作
### queue structure

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

為了讓 q_insert_tail 和 q_size 能有題目要求的 $O(1)$ 時間複雜度，所以要增加 tail
和 size 兩個feild
:::danger
「時間複雜度」和「時間」是兩件事，請改善用語，工程人員說話要精準明確
:notes: jserv
:::

### q_new

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

要記得考慮 malloc 失敗的情況

### q_free

void q_free(queue_t *q)
{
    if (!q)
        return;
    while (q->head) {
        q_remove_head(q, NULL, 0);
    }
    free(q);
}

直接使用 q_remove_head 直到 queue 變空

### q_insert_head

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

    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->value = malloc((strlen(s) + 1) * sizeof(char));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);

    if (q->size == 0)
        q->tail = newh;

    newh->next = q->head;
    q->head = newh;
    q->size++;
    return true;
}

strlen 回傳長度不包含 '\0'，所以第13行中 strlen 後面要加1
此外我發現我分不太清楚 strcpy 和 strdup 之間的差別
參考 [strcpy vs strdup](https://stackoverflow.com/questions/14020380/strcpy-vs-strdup) 後，我的理解是 strdup 是 malloc + strcpy，也因為 strdup 有 hidden malloc，所以使用完字串後 progammer 特別容易忘記 free 掉此空間
### q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL)
        return false;
    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    if (newt == NULL)
        return false;
    newt->value = malloc((strlen(s) + 1) * sizeof(char));
    if (newt->value == NULL) {
        free(newt);
        return false;
    }
    strcpy(newt->value, s);
    if (q->size == 0) {
        q->head = newt;
    } else {
        q->tail->next = newt;
    }
    q->tail = newt;
    newt->next = NULL;
    q->size++;
    return true;
}

### q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;
    if (sp) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;
    return true;
}

我原本以為是如果 buffer 放不下被刪除的資料，就直接不放，但後來發現我理解錯題意了

### q_size

int q_size(queue_t *q)
{
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    return (!q) ? 0 : q->size;
}

記得考慮 q 為 NULL 的狀況

### q_reverse

void q_reverse(queue_t *q)
{
    if (!q || q->size < 2)
        return;

    list_ele_t *front = NULL;
    list_ele_t *mid = q->head;
    list_ele_t *rear;
    while (mid) {
        rear = mid->next;
        mid->next = front;
        front = mid;
        mid = rear;
    }
    q->tail = q->head;
    q->head = front;
}

程式最後一行，我原本寫 ```q->head = mid;```
讓我 debug 很久，最後才發現執行完 while loop 後 mid pointer 指到的是 NULL

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