實作Queue

現在不論使用何種語言，基本的資料結構大都不用再自己動手實作。有可能語言本身就有提供不錯用的資料結構物件，或是多多少少也都可以拿到免費的實作完成版本。

不過，說真的有時你還真的會需要自己去動手實作某種資料結構物件。

最近，我就有一個需求需要自己動手做一個Queue。姑且不論我的需求是什麼，單是要實作一個基本型的Queue就花了我一些時間。主要的問題就在於：

1. 如何判斷Queue是空的，還是滿的：基本上在實作Queue時，一般都是先配置一個固定大小的空間，這空間可能是以陣列的方式實作的。接著就是用兩個指標的代表可放置資料的索引值(TailIndex)，以及要取得第一份資料的索引值(HeadIndex)。這兩個索引值在這個固定大小的空間中，基本上就是巡迴使用的。也就是當某個指標移動到所配置空間的結尾時，就要再移到第一個位置，從頭再來。所以有可能HeadIndex會是<TailIndex的。這樣你要如何才能判斷資料是空的，還是滿的呢?


2. 當空間不足時，你如果決定採用自動增加空間的演算法的話，那你要如何配置空間，以及將舊資料移到新的空間呢?

這些問題是我在實作一個Queue時遇到且花了一些時間思考的。雖然，終就是實作出我自己的一個Queue版本，而且也再接續改良出我所需的Queue。但還是覺得自己的實作版本可能有缺陷。

於是就上網查了一下資料，沒想到就查到兩篇看起來像是學術性的文章。一篇是用陣列來實作Queue；另一篇是用linked-list來實作Queue的。有興趣的人可參考一下囉。