# 2020q1 Homework1 (lab0)
contributed by < `chao0502` >

## 實驗環境

$ uname -a
Linux chao-Aspire-V5-591G 4.15.0-70-generic #79~16.04.1-Ubuntu SMP Tue Nov 12 14:01:10 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version 
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609

## 作業要求
詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) ，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 `q_sort` 函式。

編輯 queue.c & queue.h
q new: 新增一個 empty queue
q free: 將 queue 用到的空間都釋放掉
q insert head: 插入一個新的 node 在 queue 的head(LIFO)
q insert tail: 插入一個新的 node 在 queue 的head(FIFO)
q remove head: 將 queue 的 head 移除
q size: 回傳 queue 的長度
q sort: 將 queue 由小到大排序

:::danger
作業說明中，已規範共筆書寫的慣例：中英文字元間以半形空白字元 ==` `== 區隔，請修正。
:notes: jserv
:::

## 實作流程

1. 先從老師的 [github](https://github.com/sysprog21/lab0-c) 將所需檔案 fork 到自己的帳號
2. 使用 `git clone` 將檔案下載到本地端

    $ git clone https://github.com/自己的帳號/自己的repository名稱

3. 嘗試 `make`，得到以下結果

    $ make
    CC	qtest.o
    CC	report.o
    CC	console.o
    CC	harness.o
    CC	queue.o
    CC	random.o
    CC	dudect/constant.o
    CC	dudect/fixture.o
    CC	dudect/ttest.o
    LD	qtest

4. 開始修改作業程式碼
* **queue.h**
由於要使 `q_insert_tail` 以及 `q_size` 可在`O(1)`時間複雜度完成
因此在`queue_t`中新增兩個變數

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

* **q_new**
當 `malloc fail` 時,會給予原本要賦予記憶體空間的變數 `NULL` 值
因此在使用 `queue_t *q` 的 `q` 之前要先判斷它是否是 `NULL`

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

* **q_free**
先用 `if(q)` 來確定 `queue` 是存在的,避免錯誤的使用
之後再一一 `free` 掉 `queue` 中的 `node`

    void q_free(queue_t *q)
    {
        /* TODO: How about freeing the list elements and the strings? */
        /* Free queue structure */
        if (q) {
            whlie (q->head) {
                if (q->head->next) {
                    list_ele_t *tem;
                    tem = q->head;
                    free(q->head->value);
                    q->head = q->head->next;
                    free(tem);
                } else {
                    free(q->head->value);
                    free(q->head);
                }
            }
            free(q);
        }
    }

* **q_insert_head**
* **q_insert_tail**
* **q_remove_head**
* **q_size**
* **q_reverse**
* **q_sort**