加载中

手写数据结构·线性表04:普通顺序队列

普通顺序队列(LinearQueue)

template<class T, int MAXN>
class LinearQueue {
    T data[MAXN];
    int frontIndex, rearIndex;   // 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 必须大于零。

跳转

下一个:循环顺序队列

上一个:顺序栈

本文作者:flowwalker之码艺Blog

本文链接:/coding-notes-blog/posts/346865b9/

版权声明:本文采用 CC BY-NC-SA 4.0 许可协议