申論題

二、假設我們有一個下列的 C/C++語言的資料結構。 struct node_type { int value; struct node_type *next; }; 請用這個資料結構，設計一個 queue 的 enqueue 與 dequeue 程序。 struct node_type *enqueue(struct node_type *q, int v); 這個程序會把 v 加到 q 指到的 queue 的尾端，並且把新的 queue 傳回。 struct node_type *dequeue(struct node_type *q, int *vp); 這個程序會把 q 指到的 queue 頭的值，寫到*vp 中，然後把這個頭去掉，再把新的 queue 傳回。這兩個程序的 complexity 都必須是 O(1)，而且必須能處理空的 queue。 你只能使用一個 static pointer 變數。（25 分）