使用STL队列实现循环队列？

Question

我在互联网上搜索了一段时间，但似乎找不到答案。

我打算使用stl::queue进行一些模拟。我想知道是否可以使用stl::queue创建循环队列？据我所知，stl::queue是线性的，不是默认的循环队列？

如果可能，有人有任何实现参考资料可以提供吗？

谢谢。

- user3118602

---

正确，std::queue就是它的作用。但是你希望你的“循环队列”如何工作呢？ - Sam Varshavchik

你可以通过使用 std::deque 并在每次添加新项时删除第一个元素来模拟循环缓冲区，以防其大小超过指定的缓冲区限制。虽然不如真正的循环缓冲区便宜，但编写起来非常简单。 - user4581301

你的意思是你想要一个环形（也称为循环）缓冲区吗？你事先知道最大尺寸吗？Boost库有一个环形缓冲区：https://www.boost.org/doc/libs/1_73_0/doc/html/circular_buffer.html。 - John Zwinck

我再说一遍，std::queue就是std::queue。它不是循环队列，也没有变成循环队列的方法。 - Sam Varshavchik

如果你关心的是浪费的内存空间，那么你应该询问有关浪费的内存空间的问题。你所假设的 std::queue 浪费内存空间的想法可能是错误的，你可能在打错了方向（参见 XY 问题）。此外，在这里要求引用（你所陈述的问题，但不是你真正的问题）是明确不符合主题的... - JaMiT

Answer 1

std::deque被定义为一个线性队列，并且经过精心设计，不适用于循环队列。

具体而言，它将队列分成多个相等大小的块，因此，如果队列是相当平衡的（即平均来说，数据的生产速度与消费速度大致相同），通常会有一些块被丢弃并准备重用，因此你可以使用一个块进行长时间操作而最小化堆碎片。

为了实现这个目标，deque（至少通常）使用了双层存储机制。也就是说，它有一个可扩展的指针数组，每个指针指向包含实际数据的相等大小的块。

然而，对于循环缓冲区来说，这是无意义和不必要的。在循环缓冲区中，通常在创建它时分配一块内存，并继续使用同一块内存直到销毁它。在这种情况下，deque使用的两级存储机制只是增加了每个访问的额外间接层，但却没有完成任何有用的事情。

对于循环缓冲区，你可以使用单个、扁平的内存块来保存数据，并在该内存块中创建/销毁对象。以下是我一段时间前编写的一个简单实现:

#ifndef CBUFFER_H_INC
#define CBUFFER_H_INC

template <class T>
class circular_buffer {
    T *data;
    unsigned read_pos;
    unsigned write_pos;
    unsigned in_use;
    const unsigned capacity;
public:
    circular_buffer(unsigned size) :
        data((T *)operator new(size * sizeof(T))),
        read_pos(0),
        write_pos(0),
        in_use(0),
        capacity(size)
    {}

    void push(T const &t) {
        // ensure there's room in buffer:
        if (in_use == capacity) 
            pop();

        // construct copy of object in-place into buffer
        new(&data[write_pos++]) T(t);
        // keep pointer in bounds.
        write_pos %= capacity;
        ++in_use;
    }

    // return oldest object in queue:
    T front() {
        return data[read_pos];
    }

    // remove oldest object from queue:
    void pop() { 
        // destroy the object:
        data[read_pos++].~T();

        // keep pointer in bounds.
        read_pos %= capacity;
        --in_use;
    }
  
~circular_buffer() {
    // first destroy any content
    while (in_use != 0)
        pop();

    // then release the buffer.
    operator delete(data); 
}

};

#endif

- Jerry Coffin

---

std::list 将会 - SoronelHaetir

Answer 2

如果您可以使用 Boost 库，那么已经有一个名为 boost::circular_buffer 的类模板实现了 front()、back()、push_back() 和 pop_front() 成员函数，因此可以用作 std::queue 容器适配器的底层容器。

#include <queue>
#include <boost/circular_buffer.hpp>
#include <cassert>

template<typename T>
using Queue = std::queue<T, boost::circular_buffer<T>>;

auto main() -> int {
   Queue<int> q(boost::circular_buffer<int>(3)); // capacity of the queue is 3

   q.push(0);
   q.push(1);
   q.push(2);
   assert(q.front() == 0);
   assert(q.back() == 2);

   q.push(3);
   assert(q.front() == 1);
   assert(q.back() == 3);

   q.pop();
   assert(q.front() == 2); 
   assert(q.back() == 3);
}

- JFMR

---

无关紧要，但 auto main() -> int 是一种可怕的语义。 - Quest

@Quest 我只是用它来暗示代码至少已经编译为C++11。 - JFMR

Answer 3

你可以在https://github.com/torrentg/cqueue找到一个C++20实现的循环队列

• 符合STL容器标准（分配器、迭代器等）
• 不需要固定容量
• 仅需头文件

注意：我是该项目的维护者。

- Gerard Torrent