# 2020q3 Homework1 (lab0)
contributed by < `fdfdd12345628` >
## 作業要求
參閱[此處](https://hackmd.io/@sysprog/2020-lab0#-%E9%A0%90%E6%9C%9F%E7%9B%AE%E6%A8%99)
* 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: 「進階電腦系統理論與實作」課程所新增，以遞增順序來排序鏈結串列的元素，可參閱 Linked List Sort 得知實作手法

## 實作過程
由於 `q_insert_tail` 與 `q_size`都需要 $O(1)$ 時間，因此在 `queue.h` 修改如下

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

依序實作每個功能後，發現test case有些是測試空queue或是在q=NULL的情況，因此在每個function都會判斷指標是否為`NULL`，如下

if (q == NULL) {
    return false;
}

藉此來增加程式的穩定性

由於在insert node時，需要同時判斷head與tail是不是指向正確的node，因此兩邊都針對size為零時，有特別的處理方式

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

並且在remove node時，也會判斷是不是最後一個節點

// temp is q->head
if (temp == q->tail) {
    q->tail = NULL;
}

並且在最後修正了不少dereferencing null pointer，加入了很多情況的判斷

這份作業大概花費了8小時(沒有很認真記錄，僅參考)

## massif-visualizer
下圖為執行`make valgrind`後，visualizer的圖型

下圖為執行`trace-02-ops.cmd`後，visualizer的圖型(考慮到此test case執行操作簡單，可以很清楚的看到不同操作造成的影響)
可以看到remove head會突然增加記憶體用量，可能是測試程式所吃掉的，很快就會釋放回來。