普通顺序队列(LinearQueue)
template<class T, int MAXN>
class LinearQueue {
T data[MAXN];
int frontIndex, rearIndex;
public:
LinearQueue(){ frontIndex=rearIndex=0; }
bool empty() const { return frontIndex==rearIndex; }
bool full() const { return rearIndex==MAXN; }
int size() const { return rearIndex-frontIndex; }
bool enqueue(const T& x){
if(full()) return false;
data[rearIndex++]=x;
return true;
}
bool dequeue(){
if(empty()) return false;
frontIndex++;
return true;
}
T& front(){
if(empty()) throw underflow_error("LinearQueue::front on empty queue");
return data[frontIndex];
}
T& back(){
if(empty()) throw underflow_error("LinearQueue::back on empty queue");
return data[rearIndex-1];
}
void clear(){ frontIndex=rearIndex=0; }
};
工程细节
frontIndex 指向当前队首,rearIndex 指向下一插入位置;队尾元素在 rearIndex - 1,不是 rearIndex。
rearIndex == MAXN 就拒绝入队,即使前端已经空出位置:这就是假溢出。全部出队后仍可能同时 empty() 和 full(),调用 clear() 才复位。
- 空队列不能访问首尾。模板容量
MAXN 必须大于零。
跳转
下一个:循环顺序队列
上一个:顺序栈