---
tags: sysprog2020
---

# 2020q3 Homework1 (lab0)
contributed by < `mingjer` >

## Outline

## 環境

$ uname -a
Linux kdd179 5.4.0-47-generic #51-Ubuntu SMP Fri Sep 4 19:50:52 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

## 作業要求
在 ``queue.[c/h]`` 中完成以下實作

* `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`: 以==遞增順序==來排序鏈結串列的元素

## 實作流程

### queue.h
* 為了讓 `q_size` 和 `q_insert_tail` 兩個funtion能在 $O(1)$ 時間內完成
* 在 `queue_t` 中新增兩個參數 ( `tail`, `size` )

/* Queue structure */
typedef struct 
{
    /* Linked list of elements */
    /* TODO: You will need to add more fields to this structure
     *        to efficiently implement q_size and q_insert_tail.
     */
    /* TODO: Remove the above comment when you are about to implement. */
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

### queue.c

* **q_new**

* 先確認malloc有分配給記憶體
* 有分配 : 初始所有參數
* 沒分配 : 回傳 NULL

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

* **q_free**

* **q_insert_head**

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

* **q_insert_tail**

* **q_remove_head**

* **q_size**
* 因為要在 $O(1)$時間內完成，所以不能走訪每個節點來計算
* 直接從 `q->size` 中取值，就可以在 $O(1)$ 內完成

int q_size(queue_t *q)
{
    /* TODO: You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    /* TODO: Remove the above comment when you are about to implement. */
    if(q != NULL)
    {
        return q->size;
    }
    else
    {
        return 0;
    }
}

* **q_reverse**

* **q_sort**