# 2020q3 Homework1 (lab0)
contributed by < `chou0513` >

## Outline

## 環境

$ uname -a
Linux ubuntu-VirtualBox 5.4.0-47-generic #51-Ubuntu SMP Fri Sep 4 19:50:52 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

## 作業要求
在 ``queue.[c/h]`` 中完成以下實作

* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* `q_sort`: 以==遞增順序==來排序鏈結串列的元素

## 實作流程

### queue.h
* 更改 `queue.h` 裡面 `queue_t` ，使得 `q_size()` 和 `q_insert_tail()` 有辦法在 $O(1)$ 的時間完成
* 依照作業教學，將 `queue.h` 中的 `queue_t` 增加成員 (`size`)
* 此舉能讓 `q_size()` 藉由直接讀取 `queue_t` 中的 `size`，不必每次重新計算 queue 的大小
* 缺點是必須在每次讓 queue 新增或刪除成員時，管理 queue 的 size 以及 `tail` 指標，也讓 queue 所需的記憶體空間增大 `sizeof(pointer) + sizeof(int)`

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

### queue.h
* **q_new**
* 初始化 queue_t 前，確認是否成功分配記憶體，避免操作到空的指標

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

* **q_free**
* 新增 tmp 作為釋放用的節點
* 藉由 q->head 的移動，遍歷整個 queue，並一一清除

        void q_free(queue_t *q)
    {
        if (!q)
            return;

        list_ele_t *tmp = q->head;
        while (q->head) {
            q->head = q->head->next;
            tmp->next = NULL;
            free(tmp->value);
            free(tmp);
            tmp = q->head;
        }
        free(q);
    } 

* **q_insert_head**
* 將新元素 (list_ele_t) 放入 queue 的前端
* 先判斷傳入的 q 是否為 NULL，避免分配記憶體後才發現 q 為 NULL，造成 memory leak
* 在分配記憶體給新的元素後，判斷是否分配成功，若失敗，則將之前分配的 newh 清除
* 以 C library <string.h> 的 strncpy 複製 s，放入新元素的 value
* 因為 strncpy 不會自動將其他位置設為 \0，所以使用 memset 將 newh->value 歸零
* 確保 q->tail 能夠正常運作，第一個 element 建立時，將 q->tail 指向 q->head，且隨著新增元素，位移到最後

    bool q_insert_head(queue_t *q, char *s)
    {
       if (!q)
            return false;

        // Check separately to avoid extra malloc cause memory leak
        list_ele_t *newh;  // newh means new element in head
        newh = malloc(sizeof(list_ele_t));
        if (!newh) {
            return false;
        }

        // Allocate space and copy the string
        newh->value = malloc(sizeof(char) * (strlen(s) + 1));
        if (!newh->value) {
            free(newh);
            return false;
        }
        memset(newh->value, '\0', strlen(s) + 1);
        strncpy(newh->value, s, strlen(s));

        newh->next = q->head;
        q->head = newh;

        // first time
        if (!q->tail) {
            q->tail = q->head;
        } else {
            while (q->tail->next) {
                q->tail = q->tail->next;
            }
        }

        q->size += 1;
        return true; 
    }

* **q_insert_tail**
* 與 q_insert_head 差不多
* 將新元素 (list_ele_t) 放入 queue 的尾端
* 若 queue 為空 (q->tail == NULL)，則將 head 和 tail 同時指向新元素 (newt)

        bool q_insert_tail(queue_t *q, char *s)
    {
        if (!q)
            return false;

        // Check separately to avoid extra malloc cause memory leak
        list_ele_t *newt;  // newt means new element in tail
        newt = malloc(sizeof(list_ele_t));
        if (!newt)
            return false;

        newt->value = malloc(sizeof(char) * strlen(s) + 1);
        if (!newt->value) {
            free(newt);
            return false;
        }
        memset(newt->value, '\0', strlen(s) + 1);
        strncpy(newt->value, s, strlen(s));
        newt->next = NULL;
        if (!q->tail) {
            q->tail = q->head = newt;
        } else {
            q->tail->next = newt;
            q->tail = newt;
        }

        q->size += 1;
        return true;
    }

* **q_remove_head**

* **q_size**
* **q_reverse**
* **q_sort**