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

## 實驗環境

$ uname -a
Linux DESKTOP-GPGA00G 4.4.0-17763-Microsoft #253-Microsoft Mon Dec 31 17:49:00 PST 2018 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 8.1.0-1ubuntu3~16.04.york0) 8.1.0

## 作業要求
修改 `queue.h` `queue.c` 來實作一個支援 FIFO 和 LIFO 的 queue

`q_new()` : 建立一個空的 queue
`q_free()` : 釋放 queue 的所有記憶體資源
`q_insert_head()` : 在 queue 的頭插入一個元素 (LIFO)
`q insert tail()` : 在 queue 的尾插入一個元素 (FIFO)
`q_remove_head()` : 在 queue 的頭移除一個元素
`q_size()` : 回傳 queue 的元素個數
`q_reverse()` : 反轉 queue 中元素的順序，必須是 in-place，不能呼叫 `malloc()` 和 `free()`

Note:
- `value` 必須使用動態分配
- `q_insert_tail()` 和 `q_size()` 的時間複雜度必須是 $O(1)$

## 實作

### `struct queue_t`
`queue_t` 裡新增兩個 field : `tail` 和 `size` 以達成 $O(1)$ 的時間複雜度。

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    size_t size;
    /*
    You will need to add more fields to this structure
    to efficiently implement q_size and q_insert_tail
    */
} queue_t;

### `q_new()`
建立一個空的 queue，同時也需要檢查 malloc 是否成功。

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (!q)
        return 0;

    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

### `q_free()`
釋放傳入 queue 所有元素的記憶體資源，value 因為是動態分配的所以也必須同時釋放。

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    list_ele_t *curr, *temp;

    if (!q)
        return;

    curr = q->head;
    while (curr) {
        temp = curr;
        curr = curr->next;
        free(temp->value);
        free(temp);
    }

    free(q);
}

### `q_insert_head()`
在 queue 的頭插入一個元素，這裡也要檢查 malloc 是否成功。但在用 qtest 在評分時 trace-11-malloc 一直回傳 Attempt to free NULL，這部分一直沒辦法拿分，事實上根據 cppreference.com 對 [free()](https://en.cppreference.com/w/c/memory/free) 的描述:
> If ptr is a null pointer, the function does nothing.

一般在實作如果傳入 NULL 是沒問題的，這裡 `q_insert_head()` 的實作因應這項評分而修改。

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    char *new_value;

    /* What should you do if the q is NULL? */
    if (!q)
        return false;

    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    new_value = strdup(s);
    if (!new_value) {
        free(newh);
        return false;
    }

    newh->value = new_value;
    newh->next = q->head;
    q->head = newh;
    if (q->size == 0)
        q->tail = newh;
    q->size++;

    return true;
}

### `q_insert_tail()`
在 queue 的尾插入一個元素，需要區別 queue 的大小是 0 或大於 0 兩種情況。

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 */
    list_ele_t *newh;
    char *new_value;

    if (!q)
        return false;

    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    new_value = strdup(s);
    if (!new_value) {
        free(newh);
        return false;
    }

    newh->value = new_value;
    newh->next = NULL;
    if (q->size == 0) {
        q->head = newh;
        q->tail = newh;
    } else {
        q->tail->next = newh;
        q->tail = newh;
    }
    q->size++;

    return true;
}

### `q_remove_head`
從 queue 的頭移除一個元素，並且複製 `bufsize - 1` 個字元到 `sp` ，最後一個字元必須是空字元。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    list_ele_t *elem;

    if (!q || !q->head)
        return false;

    elem = q->head;
    q->head = q->head->next;
    if (bufsize != 0) {
        strncpy(sp, elem->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    free(elem->value);
    free(elem);
    q->size--;
    return true;
}

### `q_size()`
回傳 queue 的大小。

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

### `q_reverse()`
反轉一個 queue ，一開始需要檢查 queue 是否為 NULL 且有 2 個以上個元素，再利用三個指標 `prev curr next` 來走訪 queue ，避免因為方向對調後存取不到剩餘的元素。
參考 : [Linked List: 新增資料、刪除資料、反轉](http://alrightchiu.github.io/SecondRound/linked-list-xin-zeng-zi-liao-shan-chu-zi-liao-fan-zhuan.html)

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    list_ele_t *prev, *curr, *next;

    if (!q || q->size <= 1)
        return;

    prev = NULL;
    curr = q->head;
    next = q->head->next;

    while (next) {
        curr->next = prev;
        prev = curr;
        curr = next;
        next = next->next;
    }

    curr->next = prev;
    q->tail = q->head;
    q->head = curr;
}

## [TODO]自動評分系統運作的原理

## [TODO]qtest 的行為和裡頭的技巧