加载中

手写数据结构·线性表05:循环顺序队列

循环顺序队列(CircularQueue)

template<class T, int MAXN>
class CircularQueue {
    T data[MAXN+1];              // 多一个槽,实际容量仍是 MAXN
    int frontIndex, rearIndex;   // 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 不能溢出。出队不搬动元素;清空只把首尾下标归零。

跳转

下一个:顺序串

上一个:普通顺序队列

本文作者:flowwalker之码艺Blog

本文链接:/coding-notes-blog/posts/436f552f/

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