算法8.环形队列

算法8.环形队列// 08_环形队列.cpp : 此文件包含 main 函数。程序执行将在此处开始并结束。//#includeiostreamusingnamespacestd;// 环形队列 queue push pop front back empty sizeclassQueue{public:Queue(intsize10):cap_(size),front_(0),rear_(0),size_(0){pQue_newint[cap_];}~Queue(){delete[]pQue_;pQue_nullptr;}public:// 入队 O(1)voidpush(intval){if((rear_1)%cap_front_){expand(2*cap_);}pQue_[rear_]val;rear_(rear_1)%cap_;size_;}// 出队 O(1)voidpop(){if(front_rear_)throwqueue is empty!;front_(front_1)%cap_;size_--;}// 队头元素intfront()const{if(front_rear_)throwqueue is empty!;returnpQue_[front_];}// 队尾元素intback()const{if(front_rear_)throwqueue is empty!;returnpQue_[(rear_-1cap_)%cap_];}// 队空boolempty()const{returnfront_rear_;}// 队列元素的个数intsize()const{// return size; O(1)// 遍历一遍统计队列元素个数 O(n)intsize0;for(intifront_;i!rear_;i(i1)%cap_){size;}returnsize;}private:// 扩容接口voidexpand(intsize){int*pnewint[size];inti0;intjfront_;for(;j!rear_;i,j(j1)%cap_){p[i]pQue_[j];}delete[]pQue_;pQue_p;cap_size;front_0;rear_i;}private:int*pQue_;intcap_;// 空间容量intfront_;// 队头intrear_;// 队尾intsize_;// 队列元素个数};intmain(){intarr[]{12,4,56,7,89,31,53,75};Queue que;for(intv:arr){que.push(v);}coutque.front()endl;coutque.back()endl;que.push(100);que.push(200);que.push(300);coutque.front()endl;coutque.back()endl;while(!que.empty()){coutque.front() que.back()endl;que.pop();}}