# 2019q1 Homework1 (lab0)
contributted by < [`billqwer1687`](https://github.com/billqwer1687) >

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

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

## 開發環境

$ uname -a
Linux bill-X550JX 4.18.0-15-generic #16~18.04.1-Ubuntu SMP Thu Feb 7 14:06:04 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux


$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

## 作業要求
實作以下 LIFO FIFO Queue 之功能
* ***qnew:*** Create a new, empty queue.

* ***qfree:*** Free all storage used by a queue.
* ***qinserthead:*** Attempt to insert a new element at the head of the queue (LIFO discipline).
* ***qinserttail:*** Attempt to insert a new element at the tail of the queue (FIFO discipline).
* ***qremovehead:*** Attempt to remove the element at the head of the queue.
* ***qsize:*** Compute the number of elements in the queue.

* **詳細說明 :**

* [作業說明](https://hackmd.io/s/BJA8EgFB4)
* [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
## 實作
### queue structure

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

新增了指標tail與變數size,目的是為了讓insert from tail與計算size的時間複雜度為$O(1)$

### q_new

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

將queue初始化,且要記得malloc為NULL的狀況

### q_free

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    if (!q) {
        return;
    }
    while (q->head) {
        list_ele_t *temp;
        temp = q->head;
        q->head = q->head->next;
        free(temp->value);
        free(temp);
    }

    /* Free queue structure */
    free(q);
}

這邊要先free value才能free temp等到queue為空時再將queue給清空

### q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    if (!q) {
        return false;
    }
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }
    newh->value = malloc(strlen(s) + 1);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    if (q->head == NULL) {
        q->head = newh;
        q->tail = newh;
        q->tail->next = NULL;
        q->size++;
        return true;
    }
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;
    q->head = newh;
    q->size++;
    return true;
}

在寫作業的時候忘記將tail指向NULL所以出現了Bug

### q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    if (!q) {
        return false;
    }
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }
    newh->value = malloc(strlen(s) + 1);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    if (q->tail == NULL) {
        q->head = newh;
        q->tail = newh;
        q->tail->next = NULL;
        q->size++;
        return true;
    } else {
        q->tail->next = newh;
        q->tail = q->tail->next;
        q->tail->next = NULL;
        q->size++;
        /* Remember: It should operate in O(1) time */
        return true;
    }
}

這邊也是忘記將tail指向NULL

### q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (!q || q->head == NULL) {
        return false;
    }
    if (sp) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_ele_t *temp;
    temp = q->head;
    q->head = q->head->next;
    free(temp->value);
    free(temp);
    q->size--;
    return true;
}

sp[bufsize-1]是為了將'\0'放入字串的尾端,因為strncpy不會在尾端留'\0'

### q_size

int q_size(queue_t *q)
{
    /* You need to write the code for this function */
    if (!q) {
        return 0;
    }
    /* Remember: It should operate in O(1) time */
    return q->size;
}

因為有使用變數size儲存queue的大小所以在這裡可以以$O(1)$的時間複雜度求得queue的size

### q_reverse

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (!q || q->size < 2) {
        return;
    }
    list_ele_t *current = q->head;
    list_ele_t *prev = NULL;
    list_ele_t *rear;
    while (current != NULL) {
        rear = current->next;
        current->next = prev;
        prev = current;
        current = rear;
    }
    q->tail = q->head;
    q->head = prev;
}

此處queue的反轉參考了以下的資料[資料參考](https://www.geeksforgeeks.org/reverse-a-linked-list/),然後在q->tail = q->head的地方打反了,找了一下子

:::info
TOTAL 100/100
:::
## 自動評分系統運作的原理
在trace資料夾中有cmd命令檔案,test會依據這些cmd的命令所回傳的結果去判定程式執行是否正確
***待補完***
## ```qtest``` 的行為和裡頭的技巧
待補