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

## 作業說明

[作業要求](https://hackmd.io/@sysprog/linux2020-lab0#-%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)
[Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
[作業區](https://hackmd.io/@sysprog/linux2020-homework1)

### 作業要求

* 實作以下 queue 之相關操作
* `q_new` - 建立一個空的 queue
* `q_free` - 清空一個已創造的 queue
* `q_insert_head` - 在 queue head 新增元素 (LIFO)
* `q_insert_tail` - 在 queue tail 新增元素 (FIFO)
* `q_remove_head` - 移除 queue 的開頭元素
* `q_size` - return queue 之 元素個數
* `q_reverse` - 反轉 queue 中的順序
* 注意事項
* 須處理無效操作 (如，從空佇列或 `NULL` 佇列中刪除)
* `q_insert_tail` 和 `q_size` 需在 $O(1)$ 完成

## queue.h 實作

### 在`queue_t` 增加 `size` 及 `tail`

typedef struct {
    list_ele_t *head, *tail; /* Head and tail of this queue */
    unsigned long size; /* Size of queue_t */
} queue_t;

1. `size`欄位可使 `q_size` 在 $O(1)$ 內完成
2. `tail` 指向 queue 之末端元素

## queue.c 實作
### q_new

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

這裡檢查 `malloc` 是否成功分配記憶體空間，以及初始化賦值。
### q_free

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

釋放 queue 裡頭的每個元素 以及它的 `value` 欄位。
### q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* If q is NULL, return false */
    if (!q)
        return false;
    newh = (list_ele_t *)malloc(sizeof(list_ele_t));
    /* Check whether the space is enough or not */
    if (!newh)
        return false;
    size_t length = strlen(s) + 1;
    newh->value = (char *)malloc(length * sizeof(char));
    /* Check whether the space is enough or not */
    if (!newh->value) {
        free(newh);
        return false;
    }
    memcpy(newh->value, s, length);
    newh->next = q->head;
    /* If the queue is empty, let the tail pointer point to the new head */
    if (q->size == 0)
        q->head = q->tail = newh;
    else {
        q->head = newh;
    }
    q->size++;
    return true;
}

1. 如果 `queue` 為 `NULL`，回傳 `false`
2. 如果新增元素時 `malloc` 失敗，回傳 `false`
4. 如果新增 `value` 時 `malloc` 失敗，回傳 `false` ，且記得釋放先前 `malloc` 的元素，不然會有 memory leak 問題
5. 記得最後檢查當前是否只有一個元素，將 `head` 及 `tail` 指向它
### q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newt;
    /* If q is NULL, return false */
    if (!q)
        return false;
    newt = (list_ele_t *)malloc(sizeof(list_ele_t));
    /* Check whether the space is enough or not */
    if (!newt)
        return false;
    size_t length = strlen(s) + 1;
    newt->value = (char *)malloc(length * sizeof(char));
    /* Check whether the space is enough or not */
    if (!newt->value) {
        free(newt);
        return false;
    }
    memcpy(newt->value, s, length);
    /* If the queue is empty, let the head pointer point to the new tail */
    if (q->size == 0)
        q->head = q->tail = newt;
    else {
        q->tail->next = newt;
        q->tail = newt;
    }
    q->size++;
    return true;
}

1. 幾乎和 `q_insert_head` 實作相同，但需注意當前只有 1 個元素時， head 與 tail 的指標要修改
### q_remove_head

### q_size

int q_size(queue_t *q)
{
    return (q == NULL) ? 0 : q->size;
}

1. 需注意 queue 是否為 `NULL` ，如果不是，才可以 access 它的欄位
### q_reverse