# 2021q1 Homework1 (lab0)
contributed by < weihan1107 >

## 預備
1. 環境準備
2. 了解 [Makefile 語法和示範](https://hackmd.io/@sysprog/SySTMXPvl)

## 開始實作

### **q_insert_tail** 和 **q_size** 改為 O(1) 時間複雜度
* 根據**牛刀小試**的提示，在每次操作都記錄 size 及 tail ，如此一來需要 q_size 即可直接回傳，需要 insert_tail 即可直接找到 tail 並且 insert ，達到 O(1) 時間複雜度。故需要更改一下 queue_t 的結構，如下：

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

* 如此一來 q_size 即可完成。其中注意如果 queue 是 NULL 先回傳 0。

int q_size(queue_t *q)
{
    return q ? q->size : 0;
}

* 而 q_insert_tail 的部分，因每個操作都要注意紀錄 size 及 tail，且根據註解上的提示，須注意：
* Queue 是非為 NULL 。
* 需 allocte memory 給 list_ele_t 存放 value 。
* Allocate memory 失敗要有對應的處理。

bool q_insert_tail(queue_t *q, char *s)
{
    // Handle with if queue is NULL
    if (!q)
        return false;

    list_ele_t *newh;
    char *news;

    // Handle with allocate memory fail
    newh = malloc(sizeof(list_ele_t));
    if (!newh) return false;
    news = malloc(strlen(s) + 1);
    if (!news) {
        free(newh);
        return false;
    }

    // Copy string
    memcpy(news, s, strlen(s) + 1);

    // Insert to tail
    newh->value = news;
    newh->next = NULL;
    if (q->size == 0) {
        q->head = newh;
    } else {
        q->tail->next = newh;
    }

    // Record size and tail
    q->tail = newh;
    q->size += 1;

    return true;
}

### **q_insert_head**
* 根據註解上的提示，須注意：
* Queue 是非為 NULL 。
* 需 allocte memory 給 list_ele_t 存放 value 。
* Allocate memory 失敗要有對應的處理。
* 加上每個操作都要注意紀錄 size 及 tail

bool q_insert_head(queue_t *q, char *s)
{
    // Handle with if queue is NULL
    if (!q)
        return false;

    list_ele_t *newh;
    char *news;

    // Handle with allocate memory fail
    newh = malloc(sizeof(list_ele_t));
    if (!newh) return false;

    news = malloc(strlen(s) + 1);
    if (!news) {
        free(newh);
        return false;
    }

    // Copy string
    memcpy(news, s, strlen(s) + 1);

    // Insert to head
    newh->value = news;
    newh->next = q->head;
    q->head = newh;
    
    // Record size and tail
    if (q->size == 0)
        q->tail = newh;
    q->size += 1;

    return true;
}

### q_insert_tail
* 接著處理 q_insert_tail ， 這會跟 q_insert_head 很類似。
* 因為有記錄 tail ，所以可直接對 tail 來 insert ，達到 O(1) 時間複雜度。需注意的是，當 queue 是空的時候，應從 q->head 開始 insert 。

### q_new
* 前面 q_insert_head 和 q_insert_tail 會跟著記錄 size 及 tail ，所以在 q_new 裡面也要做相對應的初始化。
* 同樣根據註解提示，需考慮 queue 為 NULL 的情況。

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

## q_remove_head