# 2018q3 Homework2 (lab0)
contributed by < [brad84622](https://github.com/brad84622/lab0-c) >

## 實驗目標為實作 queue

- first in, first out (FIFO)
- last in, first out (LIFO)

## 開發環境設定
- 設定好 GitHub 帳號同步, vim
- 安裝以下開發工具

## 目標
- new
- insert head
- insert tail
- remove head
- reverse
- free
- size

## 結構

digraph {
node[shape=box]
tail [shape=plaintext,label=tail]
head [shape=plaintext,label=head]
{rank=same;a,b,c,NULL}
a->b
b->c
NULL[shape=plaintext]
c->NULL
head->a
tail->c
}

### insert head

digraph {
node[shape=box]
tail [shape=plaintext,label=tail]
head [shape=plaintext,label=head]
{rank=same;a,b,c,NULL,newh}
newh->a
a->b
b->c
NULL[shape=plaintext]
c->NULL
head->newh
tail->c
}

### insert tail

digraph {
node[shape=box]
tail [shape=plaintext,label=tail]
head [shape=plaintext,label=head]
{rank=same;a,b,c,NULL,newt}
a->b
b->c
c->newt
NULL[shape=plaintext]
newt->NULL
head->a
tail->newt
}

### remove head

digraph {
node[shape=box]
tail [shape=plaintext,label=tail]
head [shape=plaintext,label=head]
{rank=same;b,c,NULL}

b->c
NULL[shape=plaintext]
c->NULL
head->b
tail->c
}

### reverse

digraph {
node[shape=box]
tail [shape=plaintext,label=tail]
head [shape=plaintext,label=head]
{rank=same;a,b,c,NULL}
b->a
c->b
NULL[shape=plaintext]
a->NULL
head->c
tail->a
}

### 遭遇的錯誤

$ make test
scripts/driver.py
...
# Test of truncated strings
ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer
--- trace-06-string 0/7
...
--- TOTAL 93/100

- 觀察trace-06-string做了什麼？

# Test of truncated strings
option fail 0
option malloc 0
new
ih aardvark_bear_dolphin_gerbil_jaguar 5
it meerkat_panda_squirrel_vulture_wolf 5
rh aardvark_bear_dolphin_gerbil_jaguar
reverse
rh meerkat_panda_squirrel_vulture_wolf
option length 30
rh meerkat_panda_squirrel_vulture
reverse
option length 28
rh aardvark_bear_dolphin_gerbil
option length 21
rh aardvark_bear_dolphin
reverse
option length 22
rh meerkat_panda_squirrel
option length 7
rh meerkat
reverse
option length 8
rh aardvark
option length 100
rh aardvark_bear_dolphin_gerbil_jaguar
reverse
rh meerkat_panda_squirrel_vulture_wolf
free
quit

- 照著執行發現最後一個reverse(27行)發生錯誤
回頭檢查reverse

void q_reverse(queue_t *q) {
/* You need to write the code for this function */
if (q == NULL || q->size == 0) {
} else {
list_ele_t *prev, *cur, *nt;
prev = q->head;
cur = prev->next;
nt = cur->next;
prev->next = NULL;
cur->next = prev;
prev = cur;
cur = nt;
int i;
for (i = 0; i < (q->size) - 2; i++) {
nt = nt->next;
cur->next = prev;
prev = cur;
cur = nt;
}
q->tail = q->head;
q->head = prev;
}
}

- 發現自己預設考慮3個以上及q=NULL還有size=0的情況
忽略掉1&2個點的情況
- 修改成

void q_reverse(queue_t *q) {
/* You need to write the code for this function */
if (q == NULL || q->size == 0||q->size==1) {
} else if(q->size==2) {
q->tail->next=q->head;
q->head->next=NULL;
q->head=q->tail;
q->tail=q->tail->next;
} else {
list_ele_t *prev, *cur, *nt;
prev = q->head;
cur = prev->next;
nt = cur->next;
prev->next = NULL;
cur->next = prev;
prev = cur;
cur = nt;
int i;
for (i = 0; i < (q->size) - 2; i++) {
nt = nt->next;
cur->next = prev;
prev = cur;
cur = nt;
}
q->tail = q->head;
q->head = prev;
}
}

## 結果

$ make test
gcc -O0 -g -Wall -Werror -c queue.c
gcc -O0 -g -Wall -Werror -o qtest qtest.c report.c console.c harness.c queue.o
scripts/driver.py
--- Trace Points
...
--- TOTAL 100/100