C++循环队列实现模型
本文实例讲述了C++循环队列实现模型。分享给大家供大家参考。具体分析如下：
前段时间在知乎上看到这样一个小题目：
用基本类型实现一队列，队列要求size是预先定义好的的。而且要求不可以使用语言自带的api，如C++的STL。普通的实现很简单，但是现在要求要尽可能的时间和空间复杂度的优化，要和语言自带的api比较时间和空间。这个队列还要支持如下的操作：
constructor:初始化队列
enqueue:入队
dequeue:出队
队列是一种基本的数据结构，在平常的应用中十分广泛，多数情况队列都是用链表实现的。但是对于本题而言，用链表实现就有这样一个问题：由于每个结点都存在至少一个指向前一个结点或后一个结点的指针，这就带来了空间复杂度的加大，所以并不太适合要求。
这个时候我想到了boost中的boost::circular_buffer，它是通过类似于数组的底层结构实现的一个循环buffer。而数组的优点是空间复杂度够小(除去维持数据结构的索引项，空间复杂度为线性)，再实现成循环结构可以最大化的利用空间。而且在队列这样一种只在前后端插入删除的情况下，其push和pop的时间复杂度也只有O(1)。
基本实现如下：
#ifndef__CIRCULAR_QUEUE_H__ #define__CIRCULAR_QUEUE_H__
#include<stddef.h>
template<typenameT> classcircular_queue { public: explicitcircular_queue(size_tmaxsize) :maxsize_(maxsize+1),head_(0),rear_(0) { array_=newT[maxsize_]; }
circular_queue(size_tmaxsize,constT&val) :maxsize_(maxsize+1),head_(0),rear_(0) { array_=newT[maxsize_]; for(size_ti=0;i!=maxsize;++i) { array_[i]=val; } rear_=maxsize; }
circular_queue(constcircular_queue&rhs) :maxsize_(rhs.maxsize_),head_(rhs.head_),rear_(rhs.rear_) { array_=newT[maxsize_]; for(inti=0;i!=maxsize_;++i) { array_[i]=rhs.array_[i]; } }
~circular_queue() { delete[]array_; }
circular_queue&operator=(constcircular_queue&rhs) { if(this==&rhs) { return*this; } delete[]array_; maxsize_=rhs.maxsize_; head_=rhs.head_; rear_=rhs.rear_; array_=newT[maxsize_]; for(inti=0;i!=maxsize_;++i) { array_[i]=rhs.array_[i]; } return*this; }
boolempty()const { returnhead_==rear_; }
size_tsize()const { return(rear_-head_+maxsize_)%maxsize_; }
T&front() { returnarray_[head_]; }
constT&front()const { returnarray_[head_]; }
voidpush(constT&val) { if((rear_+1)%maxsize_!=head_) { array_[rear_]=val; rear_=(rear_+1)%maxsize_; } }
voidpop() { if(head_!=rear_) { head_=(head_+1)%maxsize_; } }
private: size_t maxsize_; int head_; int rear_; T* array_; };
#endif