# 2021q1 Homework1 (lab0) contributed by < `fdfdd12345628` > ## 作業要求 * 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` 修改如下 ```clike= typedef struct { list_ele_t *head; int size; list_ele_t *tail; } queue_t; ``` 依序實作每個功能後，發現test case有些是測試空queue或是在q=NULL的情況，因此在每個function都會判斷指標是否為`NULL`，如下 ```clike= if (q == NULL) { return false; } ``` 藉此來增加程式的穩定性 由於在insert node時，需要同時判斷head與tail是不是指向正確的node，因此兩邊都針對size為零時，有特別的處理方式 ```clike= if (q->size == 0) { q->head = newh; q->tail = newh; } ``` 並且在remove node時，也會判斷是不是最後一個節點 ```clike= // temp is q->head if (temp == q->tail) { q->tail = NULL; } ``` 並且在最後修正了不少dereferencing null pointer，加入了很多情況的判斷 這份作業大概花費了8小時(沒有很認真記錄，僅參考) 在執行以下指令後跑出的 massif 圖形 ``` new ih RAND 10000 sort reverse sort free new ih RAND 50000 sort reverse sort free new ih RAND 100000 sort reverse sort free ``` ![](https://i.imgur.com/Dktlrzk.png)