首页 > 代码库 > 循环队列的实现模型

循环队列的实现模型

  前段时间在知乎上看到这样一个小题目:

  用基本类型实现一队列,队列要求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(后进先出)队列,当队列满时删除最旧的(即最早插入的)元素。

(完)

 

循环队列的实现模型