有没有办法做一个循环堆栈？

Question

下午好 ！

我正在尝试制作某种圆形堆栈。它应该像一个普通的 LIFO 堆栈，但没有明显的限制。它应该消除或跳过当时引入的第一个元素，而不是达到最大容量！

例如：

假设我们有一个包含 3 个元素的堆栈：stack[3]

我们通过将 3 个元素“推入”内部来填充它：push[a], push[b], push[c]。

但随后我们需要添加第四个和第五个元素：push[d], push[e]。

标准堆栈会说堆栈已达到极限，无法添加更多元素。

但我想要一个循环堆栈，它将消除或跳过aand b，记住c，dande并输出e，dand c；

该项目是在 ESP32 上的 PlatformIO 中完成的，因此我无法访问 C++ STL，即使可以访问，我也认为仅为 1 个堆栈编译这么大的库是没有意义的。即使曾经有一段时间我认为我应该编译一个类似的库来让我访问stackor deque，但那个时候已经过去了，因为现在我感觉自己像一个无法解决数学问题的白痴。这已经困扰我一个多星期了。

我在网上找到的只是以下 FIFO 循环缓冲区：

class circular_buffer {
public:
    explicit circular_buffer(size_t size) :
        buf_(std::unique_ptr<T[]>(new T[size])),
        max_size_(size)
    {

    }

    void put(T item)
    {
        std::lock_guard<std::mutex> lock(mutex_);

        buf_[head_] = item;

        if(full_) {
            tail_ = (tail_ + 1) % max_size_;
        }

        head_ = (head_ + 1) % max_size_;

        full_ = head_ == tail_;
    }

    T get()
    {
        std::lock_guard<std::mutex> lock(mutex_);

        if(empty())
        {
            return T();
        }

        //Read data and advance the tail (we now have a free space)
        auto val = buf_[tail_];
        full_ = false;      
        tail_ = (tail_ + 1) % max_size_;

        return val;
    }

    void reset()
    {
        std::lock_guard<std::mutex> lock(mutex_);
        head_ = tail_;
        full_ = false;
    }

    bool empty() const
    {
        //if head and tail are equal, we are empty
        return (!full_ && (head_ == tail_));
    }

    bool full() const
    {
        //If tail is ahead the head by 1, we are full
        return full_;
    }

    size_t capacity() const
    {
        return max_size_;
    }

    size_t size() const
    {
        size_t size = max_size_;

        if(!full_)
        {
            if(head_ >= tail_)
            {
                size = head_ - tail_;
            }
            else
            {
                size = max_size_ + head_ - tail_;
            }
        }

        return size;
    }

private:
    std::mutex mutex_;
    std::unique_ptr<T[]> buf_;
    size_t head_ = 0;
    size_t tail_ = 0;
    const size_t max_size_;
    bool full_ = 0;
};

在过去的三天里我一直在修改它，但我就是无法让它按照我想要的方式工作。它是一个 FIFO 结构，将打印a, b,c或c, d, e。

在这种情况下，我希望它从上到下、从头到尾打印，但我无法弄清楚。

Answer 1

如果我理解正确，那么您所寻找的只是一个具有固定大小的缓冲区，该缓冲区有一个指向“堆栈”的“顶部”的指针，该指针会递增/递减，以便它环绕堆栈的末尾缓冲。这将自动导致最新的条目总是覆盖最旧的条目，从而有效地为您提供最后 N 个值的 LIFO 存储，其中 N 是缓冲区大小。例如：

\n\n

#include <cstddef>\n#include <memory>\n#include <iostream>\n\ntemplate <typename T>\nclass ForgetfulStack\n{\n    std::unique_ptr<T[]> buffer;\n    std::size_t head = 0;\n    std::size_t size = 0;\n\npublic:\n    ForgetfulStack(std::size_t size)\n        : buffer(std::make_unique<T[]>(size)), size(size)\n    {\n    }\n\n    void push(const T& value)\n    {\n        buffer[head] = value;\n        head = (head + 1) % size;\n    }\n\n    T pop()\n    {\n        head = (head - 1 + size) % size;\n        return buffer[head];\n    }\n};\n\nint main()\n{\n    ForgetfulStack<int> blub(3);\n\n    blub.push(1);\n    blub.push(2);\n    blub.push(3);\n    blub.push(4);\n    blub.push(5);\n\n    std::cout << blub.pop() << \' \' << blub.pop() << \' \' << blub.pop() << std::endl;\n}\n

\n\n

请注意，这个简单的实现不是线程安全的\xe2\x80\xa6

\n