C++循环队列的简单实现

#include <iostream>

template <typename T>
class queue {
 public:
  queue(size_t size) : size_(size), front_(0), end_(0) { data_ = new T[size]; }
  ~queue() { delete[] data_; }
  queue(const queue& other) = delete;
  queue(queue&& other) = delete;
  queue operator=(const queue& other) = delete;
  queue operator=(queue&& other) = delete;

  bool is_empty() { return front_ == end_; }
  bool is_full() { return front_ = (end_ + 1) % size_; }

  const T& front() const { return data_[front_]; }

  void push(const T& val) {
    if ((end_ + 1) % size_ != front_) {
      data_[end_] = val;
      end_ = (end_ + 1) % size_;
    }
  }

  void pop() {
    if (front_ != end_) {
      front_ = (front_ + 1) % size_;
    }
  }

 private:
  size_t front_;
  size_t end_;
  size_t size_;
  T* data_;
};

int main() {
  queue<int> q(5);
  q.push(1);
  q.push(2);
  q.push(3);
  q.push(4);
  q.push(5);
  q.pop();
  q.pop();
  q.push(6);
  q.push(7);
  q.push(8);
  while (!q.is_empty()) {
    std::cout << q.front() << std::endl;
    q.pop();
  }
  return 0;
}

不采用哨兵值，使用状态来实现

spdlog 循环队列实现

template <typename T>
class circular_q {
  size_t max_items_ = 0;
  typename std::vector<T>::size_type head_ = 0;
  typename std::vector<T>::size_type tail_ = 0;
  size_t overrun_counter_ = 0;
  std::vector<T> v_;

 public:
  using value_type = T;

  // empty ctor - create a disabled queue with no elements allocated at all
  circular_q() = default;

  explicit circular_q(size_t max_items)
      : max_items_(max_items + 1)  // one item is reserved as marker for full q
        ,
        v_(max_items_) {}

  circular_q(const circular_q &) = default;
  circular_q &operator=(const circular_q &) = default;

  // move cannot be default,
  // since we need to reset head_, tail_, etc to zero in the moved object
  circular_q(circular_q &&other) noexcept {
    copy_moveable(std::move(other));
  }

  circular_q &operator=(circular_q &&other) noexcept {
    copy_moveable(std::move(other));
    return *this;
  }

  // push back, overrun (oldest) item if no room left
  void push_back(T &&item) {
    if (max_items_ > 0) {
      v_[tail_] = std::move(item);
      tail_ = (tail_ + 1) % max_items_;

      if (tail_ == head_)  // overrun last item if full
      {
        head_ = (head_ + 1) % max_items_;
        ++overrun_counter_;
      }
    }
  }

  // Return reference to the front item.
  // If there are no elements in the container, the behavior is undefined.
  const T &front() const { return v_[head_]; }

  T &front() { return v_[head_]; }

  // Return number of elements actually stored
  size_t size() const {
    if (tail_ >= head_) {
      return tail_ - head_;
    } else {
      return max_items_ - (head_ - tail_);
    }
  }

  // Return const reference to item by index.
  // If index is out of range 0…size()-1, the behavior is undefined.
  const T &at(size_t i) const {
    assert(i < size());
    return v_[(head_ + i) % max_items_];
  }

  // Pop item from front.
  // If there are no elements in the container, the behavior is undefined.
  void pop_front() { head_ = (head_ + 1) % max_items_; }

  bool empty() const { return tail_ == head_; }

  bool full() const {
    // head is ahead of the tail by 1
    if (max_items_ > 0) {
      return ((tail_ + 1) % max_items_) == head_;
    }
    return false;
  }

  size_t overrun_counter() const { return overrun_counter_; }

 private:
  // copy from other&& and reset it to disabled state
  void copy_moveable(circular_q &&other) noexcept {
    max_items_ = other.max_items_;
    head_ = other.head_;
    tail_ = other.tail_;
    overrun_counter_ = other.overrun_counter_;
    v_ = std::move(other.v_);

    // put &&other in disabled, but valid state
    other.max_items_ = 0;
    other.head_ = other.tail_ = 0;
    other.overrun_counter_ = 0;
  }
};