循环顺序队列(CircularQueue)
template<class T, int MAXN>
class CircularQueue {
T data[MAXN+1];
int frontIndex, rearIndex;
int next(int i) const { return (i+1)%(MAXN+1); }
public:
CircularQueue(){ frontIndex=rearIndex=0; }
bool empty() const { return frontIndex==rearIndex; }
bool full() const { return next(rearIndex)==frontIndex; }
int size() const { return (rearIndex-frontIndex+MAXN+1)%(MAXN+1); }
int capacity() const { return MAXN; }
bool enqueue(const T& x){
if(full()) return false;
data[rearIndex]=x;
rearIndex=next(rearIndex);
return true;
}
bool dequeue(){
if(empty()) return false;
frontIndex=next(frontIndex);
return true;
}
T& front(){
if(empty()) throw underflow_error("CircularQueue::front on empty queue");
return data[frontIndex];
}
T& back(){
if(empty()) throw underflow_error("CircularQueue::back on empty queue");
int pos=(rearIndex-1+MAXN+1)%(MAXN+1);
return data[pos];
}
void clear(){ frontIndex=rearIndex=0; }
};
工程细节
frontIndex 是当前队首,rearIndex 是下一插入位置,所有指针推进都对缓冲区大小 (MAXN + 1) 取模。
- 内部保留一个空槽:
frontIndex == rearIndex 判空,next(rearIndex) == frontIndex 判满。实际分配 MAXN + 1 个槽,因此可用容量仍是 MAXN。
back() 要取 rearIndex 的前一个槽,并处理回绕;长度也要按环形距离计算。不要只写 rearIndex - frontIndex。
- 容量必须大于零,且
MAXN + 1 不能溢出。出队不搬动元素;清空只把首尾下标归零。
跳转
下一个:顺序串
上一个:普通顺序队列