c++ - 有没有办法做一个循环堆栈?
问题描述
下午好 !
我正在尝试制作某种圆形堆栈。它应该像一个普通的 LIFO 堆栈,但没有明显的限制。它应该消除或跳过当时引入的第一个元素,而不是达到它的最大容量!
例如:
假设我们有一个包含 3 个元素的堆栈:stack[3]
我们通过“推”里面的 3 个元素来填充它:push[a], push[b], push[c]
.
但随后我们将要添加第 4 个和第 5 个元素:push[d], push[e]
.
标准堆栈会说堆栈达到了它的限制,它不能再添加任何元素。
但我想要一个循环堆栈,它可以消除或跳过a
and b
、记住c
、d
ande
和输出e
, d
and c
;
该项目是在 ESP32 上的 PlatformIO 中完成的,所以我无法访问 C++ STL,即使我有,我认为只为 1 个堆栈编译这么大的库是没有意义的。即使有一段时间我认为我应该编译一个应该让我访问stack
or的类似库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;
};
在过去的 3 天里,我一直在修补它,但我无法让它按照我想要的方式工作。它是一个 FIFO 结构,将打印a
, b
,c
或c
, d
, e
。
在这种情况下,我希望它从上到下,从头到尾打印,但我无法弄清楚。
解决方案
如果我理解正确,那么您正在寻找的只是一个具有固定大小的缓冲区,它有一个指向“堆栈”的“顶部”的指针,该指针会递增/递减,使其环绕缓冲区的末尾. 这将自动导致最新的条目总是覆盖最旧的条目,从而有效地为您提供最后 N 个值的 LIFO 存储,其中 N 是缓冲区大小。例如:
#include <cstddef>
#include <memory>
#include <iostream>
template <typename T>
class ForgetfulStack
{
std::unique_ptr<T[]> buffer;
std::size_t head = 0;
std::size_t size = 0;
public:
ForgetfulStack(std::size_t size)
: buffer(std::make_unique<T[]>(size)), size(size)
{
}
void push(const T& value)
{
buffer[head] = value;
head = (head + 1) % size;
}
T pop()
{
head = (head - 1 + size) % size;
return buffer[head];
}
};
int main()
{
ForgetfulStack<int> blub(3);
blub.push(1);
blub.push(2);
blub.push(3);
blub.push(4);
blub.push(5);
std::cout << blub.pop() << ' ' << blub.pop() << ' ' << blub.pop() << std::endl;
}
请注意,这个简单的实现不是线程安全的……</p>
推荐阅读
- java - Wildfly 17 上的休眠 ogm infinispan @manytoone 双向问题
- azure-service-fabric - 如何解决“Service Fabric Partition is in error”错误?
- java - 如何为某些 XML 配置片段找到相应的注释/基于 Java 的配置对应项?
- r - R中的正则表达式:如何在目标字符串的左侧和右侧填充多个匹配的数据框
- r - R:重命名第二个数据帧的数据函数中的列(揭盲数据)
- opengl - 如何为定制结构配置 VAO 和 VBO
- nuxt.js - .nuxt/ 文件是否需要始终提交?
- excel - 如何在确定的单元格中复制粘贴,每周更改变量(不在代码中)
- ios - 使用 swiftUI 的动态视图
- php - Laravel echo 没有任何响应