首页 > 代码库 > 循环队列的一种实现模型
循环队列的一种实现模型
前段时间在知乎上看到这样一个小题目：
用基本类型实现一队列，队列要求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、适用于实时和对性能有严格要求的应用程序。
还可以进一步扩展，当队列满的时候，从一端插入则覆盖冲洗掉另一端的数据，这样的一个模型可以应用于这些场合：
- 保存最近接收到的取样数据，在新的取样数据到达时覆盖最旧的数据。
- 一种用于保存特定数量的最后插入元素的快速缓冲。
- 高效的固定容量FIFO(先进先出)或LIFO(后进先出)队列，当队列满时删除最旧的(即最早插入的)元素。
（完）
循环队列的一种实现模型