Is there a way to do a circular stack?

Question

Good afternoon !

I am trying to make some sort of circular stack. It should be like a normal LIFO stack, but without an apparent limit. Instead of hitting it's max capacity it should eliminate or jump over the first element introduced at that moment in time !

For example:

Let's say we have a stack with 3 elements: stack[3]

We populate it by "pushing" 3 elements inside: push[a], push[b], push[c].

But then we will want to add a 4th and a 5th element: push[d], push[e].

Standard stacks will say that the stack reached it's limit and it can't add any more elements.

But I want a circular stack that will eliminate or jump over a and b, remember c, d and e and output e, d and c;

The project is done in PlatformIO on an ESP32, so I don't have access to the C++ STL, and even if I had, I thought that compiling such a big library for just 1 stack is pointless. Even if there were a time when I thought I should compile a similar library that should give me acces to stack or deque, that time is long gone, because right now I feel like an idiot who can't figure out a math problem. This has been bugging me for over a week now.

All I have managed to find online was the following FIFO circular buffer:

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;
};

I've been tinkering with it for the past 3 days but I just can't make it work the way I want it to. It, being a FIFO structure, will print a, b, c or c, d, e.

I want it to print from top to bottom, from head to tail in this case, but I cannot figure it out.

Answer 1

If I understand correctly, then all you're looking for is a buffer with a fixed size that has a single pointer to the "top" of the "stack", which is incremented/decremented such that it wraps around the end of the buffer. This will automatically lead to the newest entry always overwriting the oldest one, effectively giving you a LIFO storage for the last N values, where N is the buffer size. For example:

#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;
}

Note that this simple implementation is not thread safe…