# 2019q1 Homework1 (lab0)
contributed by < `Laurora` >

* [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
* [F01: lab0](https://hackmd.io/s/BJA8EgFB4#%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)

:::danger
認真看作業要求，除了提及如何逐步達到要求，還需要進行:
1. 改善程式效能
2. 解釋自動評分系統運作的原理
3. 提及 qtest 的行為和裡頭的技巧

還未達成符合預期目標，請繼續付出！
:notes: jserv
:::

## 作業要求

### 透過 link list 實做 LIFO 與 FIFO queue

* q new: 新增一個空的 queue
* q free: 將 queue 清空
* q insert head: 從 queue 的 head 插入新的元素 ( 實做 LIFO )
* q insert tail: 從 queue 的 tail 插入新的元素 ( 實做 FIFO )
* q remove head: 從 queue 的 head 移除元素
* q size: 紀錄 queue 中有幾個元素
* q reverse: 反轉 queue 中所有元素的順序，不得另外配置元素空間協助反轉，過程必須直接針對原來存在的元素執行。

**注意**
* q_insert_tail 和 q_size 的時間複雜度須為 $O(1)$
* 須透過呼叫 malloc() 針對各個 string 的長度分配相應的空間，使用完該空間以後要記得 free()

## 實作過程

### queue.h

typedef struct {
    list_ele_t *head, *tail; 
    size_t qsize;
} queue_t;

* 額外新增 `qsize` 即時紀錄 queue 空間大小，讓 q_size 可在 $O(1)$ 時間內完成，不須每次呼叫 q_size 便從 queue 的第一個元素開始數，此時所需時間為 $O(n)$ 。
* 同理，新增 `*tail` 紀錄 queue 的 tail element 使 q_insert_tail 可在 $O(1)$ 時間內完成。

### q_new

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

* 配置新增的 queue 空間
* 對新增的 queue 做 initialization

### q_free
:::danger
程式碼縮排和風格已有規範，請確保 HackMD 頁面所有程式碼列表都符合
:notes: jserv
:::

void q_free(queue_t *q)
{
    if (q == NULL)
        return;
    while (q->head) {
        list_ele_t *temp = q->head->next;
        free(q->head);
        q->head = temp;
        }
    free(q);
}

* 清空整個 queue
* 若 queue = NULL ，則跳出函式，避免 `dangling pointers`

### q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    
    list_ele_t *newh = NULL;
    newh = malloc(sizeof(list_ele_t));
    
    if (!newh) {
        free(newh);
        return false;
    }

    if (q->qsize == 0) {
        newh->next = NULL;
        q->tail = newh;
    }
    newh->value = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh->value);
        newh = NULL;
        return false;
    }
    strcpy(newh->value, s);
    newh->next = q->head;
    q->head = newh;
    q->qsize++;

    free(newh->value);
    newh = NULL;
    return true;
}

* 在 queue 的 head 插入新元素
* 要記得 allocate 新的空間給 `newnode （ newh ）` 以及新增 queue 的元素空間（ `strlen(s)+1` ）
* 新增元素之後要把暫存 newnode 的空間釋出（ `free(new->value)` ）

### q_insert_tail

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

    list_ele_t *newt = NULL;
    newt = malloc(sizeof(list_ele_t));

    if (newt == NULL) {
        free(newt);
        return false;
    } 
    newt->value = malloc(strlen(s) + 1);  // define newt

    if (newt->value)
        strcpy(newt->value, s);

    newt->next = NULL;

    if (q->qsize == 0)
        q->head = newt;  //考慮 queue 原來為空

    q->tail->next = newt;
    q->tail = newt;
    q->qsize++;

    free(newt->value);
    newt = NULL;
    return true;
}

* 在 queue 的 tail 插入新元素

### q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
   
    if (!q || q->qsize == 0) {
        return false;
    }

    if (q->qsize == 1) {
        q->qsize--;
        q->head = q->tail = NULL;
        q->head->value = NULL;
        return true;
    }
    list_ele_t *temp = q->head;
    q->head = q->head->next;
    if (sp) {  
        memset(sp, '\0', bufsize);//將 sp 空間初始化
        strncpy(sp, temp->value, bufsize - 1);
    }
    q->qsize--;
    return true;
}

* 須考慮 queue 為空，避免 `dangling pointers`
* strncpy 可指定 copy 的字串長度，由於 remove 使得需要 copy 的字串少一個，因此在這裡使用 `strncpy` 而非 `strcpy`

### q_size

int q_size(queue_t *q)
{
    if (!q)
        return 0;
    else
        return q->qsize;
}

* 回傳 queue 空間大小
### q_reverse

void q_reverse(queue_t *q)
{
    list_ele_t *next, *prev, *current;
    current = NULL;
    prev = NULL;
    if (q->qsize == 0)  
        return;
    current = q->head;
    q->tail = current;  // tail turns out to be head
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
        q->head = prev;
    }
}

* 將 queue 中的所有元素反轉
### 實作過程整理與總結
* 過程中犯了最大的一個錯誤就是未考慮 queue 為空的條件，平常很少接觸指標的寫法，因此在分配指標之前經常忽略這個條件，到 `./qtest` 時才發現此盲點。
* `strdup()` 的轉換
+ strdup() 可將字串複製到指定位址，然而並非標準 C 語言函式，是由 `malloc()` 和 `strcpy()` 兩個指令實作而來，最後使用完指定位址的 pointer 空間要記得釋放。常見轉換方式如下：

     char *d = malloc(strlen(s) + 1);
     strcpy(d, s);
     /* some instructions here */
     free(d);

## 解釋自動評分系統運作的原理
待補

## qtest 的行為與技巧
待補