前段時間在知乎上看到這樣一個小題目：
用基本類型實現一隊列，隊列要求size是預先定義好的的。而且要求不可以使用語言自帶的api，如C++的STL。普通的實現很簡單，但是現在要求要盡可能的時間和空間復雜度的優化，要和語言自帶的api比較時間和空間。這個隊列還要支持如下的操作：
constructor: 初始化隊列
enqueue:入隊
dequeue:出隊
隊列是一種基本的數據結構，在平常的應用中十分廣泛，多數情況隊列都是用鏈表實現的。但是對於本題而言，用鏈表實現就有這樣一個問題：由於每個結點都存在至少一個指向前一個結點或後一個結點的指針，這就帶來了空間復雜度的加大，所以並不太適合要求。
這個時候我想到了boost中的boost::circular_buffer，它是通過類似於數組的底層結構實現的一個循環buffer。而數組的優點是空間復雜度夠小(除去維持數據結構的索引項，空間復雜度為線性)，再實現成循環結構可以最大化的利用空間。而且在隊列這樣一種只在前後端插入刪除的情況下，其push和pop的時間復雜度也只有O(1)。
基本實現如下：
1 #ifndef __CIRCULAR_QUEUE_H__
2 #define __CIRCULAR_QUEUE_H__
3
4 #include <stddef.h>
5
6 template<typename T>
7 class circular_queue
8 {
9 public:
10 explicit circular_queue(size_t maxsize)
11 : maxsize_(maxsize + 1), head_(0), rear_(0)
12 {
13 array_ = new T[maxsize_];
14 }
15
16 circular_queue(size_t maxsize, const T& val)
17 : maxsize_(maxsize + 1), head_(0), rear_(0)
18 {
19 array_ = new T[maxsize_];
20 for (size_t i = 0; i != maxsize; ++i)
21 {
22 array_[i] = val;
23 }
24 rear_ = maxsize;
25 }
26
27 circular_queue(const circular_queue& rhs)
28 : maxsize_(rhs.maxsize_), head_(rhs.head_), rear_(rhs.rear_)
29 {
30 array_ = new T[maxsize_];
31 for (int i = 0; i != maxsize_; ++i)
32 {
33 array_[i] = rhs.array_[i];
34 }
35 }
36
37 ~circular_queue()
38 {
39 delete [] array_;
40 }
41
42 circular_queue& operator=(const circular_queue& rhs)
43 {
44 if (this == &rhs)
45 {
46 return *this;
47 }
48 delete [] array_;
49 maxsize_ = rhs.maxsize_;
50 head_ = rhs.head_;
51 rear_ = rhs.rear_;
52 array_ = new T[maxsize_];
53 for (int i = 0; i != maxsize_; ++i)
54 {
55 array_[i] = rhs.array_[i];
56 }
57 return *this;
58 }
59
60 bool empty() const
61 {
62 return head_ == rear_;
63 }
64
65 size_t size() const
66 {
67 return (rear_ - head_ + maxsize_) % maxsize_;
68 }
69
70 T& front()
71 {
72 return array_[head_];
73 }
74
75 const T& front() const
76 {
77 return array_[head_];
78 }
79
80 void push(const T& val)
81 {
82 if ((rear_ + 1) % maxsize_ != head_)
83 {
84 array_[rear_] = val;
85 rear_ = (rear_ + 1) % maxsize_;
86 }
87 }
88
89 void pop()
90 {
91 if (head_ != rear_)
92 {
93 head_ = (head_ + 1) % maxsize_;
94 }
95 }
96
97 private:
98 size_t maxsize_;
99 int head_;
100 int rear_;
101 T* array_;
102 };
103
104 #endif
隊列長度 = 數組長度 - 1
預留了一個單位的數組元素空間作為隊尾標記。
這個只是簡陋的實現，沒有考慮到一些情況，比如線程安全、STL算法，函數對象的兼容等。代碼只是簡單的測試了一下，如有錯誤歡迎指正:)
總的來說，這種思路的循環隊列有以下優點：
1、使用固定的內存，不需要隱式或意外的內存分配。
2、從前端或後端進行快速的常量時間的插入和刪除元素。
3、快速的常量時間的對元素進行隨機訪問。(如果需要的話可以定義operator[])
4、適用於實時和對性能有嚴格要求的應用程序。
還可以進一步擴展，當隊列滿的時候，從一端插入則覆蓋沖洗掉另一端的數據，這樣的一個模型可以應用於這些場合：
（完）
