In audio, we often use std::vector and arrays for holding data. It is a flexible data structure that allows random reads and writes. However, we may want to restrict the processing order. In this case, we may use other STL container classes or we may create data structures such as stacks and queues.

Two common data structures in computer science are LIFO (last-in-first-out) and FIFO (first-in-first-out). In audio the FIFO data structure is especially important and will occur as a topic of further discussion in later articles.

Resources

Finding good explanations of these data structures is easy but I want to point you to further resources:

Last-In-First-Out

In a LIFO data structure, the newest element added to the queue will be processed first. Sometimes this will be called a stack and is usually pictured as below. The new element is always added at the end of the stack. There are two basic operations that a LIFO needs to allow:

  • push – append an element to the end of the container
  • pop – remove the most recent element from the container

The LIFO data structure can be thought of as analogous to a deck of cards that you add to the top of and draw from the top of.

A Basic LIFO Data Structure

The following code should outline a basic LIFO as we have discussed so far.

class BasicLIFO
{
    private:
        /*use a vector to store the data...*/
        vector<float> containerLIFO;

        bool isEmpty()
        {
            /*checks if the container is empty or not...
            we need this function as our container is private.*/
            return containerLIFO.empty();
        }
    
    public:
    
        void push(float x)
        {
            /*append value to vector...*/
            containerLIFO.push_back(x);
        }
    
        bool pop()
        {
            /* check whether the queue is empty or not... */
            if (isEmpty())
            {
                return false;
            }
            /* delete an element from the queue...*/
            containerLIFO.pop_back();
            /*return true if the operation is successful...*/
            return true;
        }
};

There are more advanced LIFO structures that are generic, multi-channeled, can handle multiple users, multiple readers or can still have methods that handle internal sorting and searching.

LIFOs are useful when a program needs to access the most recent information entered. Stacks are important in algorithms involving backtracking. While this is not fundamental to DSP it is common to use this in other parts of a program such as File Management or parameter parsing. I highly recommend you come to grips with std::stack for solving interview related LIFO questions.

First-In-First-Out

In a FIFO data structures the first element added to the container will be processed first. There are two basic operations that a FIFO needs to allow:

  • enqueue – append an element to the end of the container
  • dequeue – remove the first element from the container

This is represented graphically below. The container is a number of contiguous boxes. A box can be added to only one end and a box can be taken from only the opposite end. Think of it like a conveyor belt.

A Basic FIFO Data Structure

The following code should outline a basic FIFO as we have discussed so far.

class BasicFIFO
{
    private:
        /*use a vector to store the data...
        pretend this is an audio buffer....*/
        vector<float> containerFIFO;       
        /*a read index to indicate the start position...*/
        int readIndex;

        bool isEmpty()
        {
            /*checks whether the container is empty or not...*/
            return readIndex >= containerFIFO.size();
        }

    public:
        BasicFIFO()
        {
            /*initialize readIndex position...*/
            readIndex = 0;
        }
    
        bool enqueueValue(float x)
        {
            /*insert an element into the container...
            return true if the operation is successful...*/
            containerFIFO.push_back(x);
            return true;
        }
    
        bool dequeueValue()
        {
            /*increment readIndex...
            return true if the operation is successful...*/
            if (isEmpty())
            {
                return false;
            }
            readIndex++;
            return true;
        }
};

This class and the behavior designated by the functions ensures that our data structure has this First In First Out behavior that the name implies. However, we can do much better as this class is highly inefficient.

r designated by the functions ensures that our data structure has this First In First Out behavior that the name implies. However, we can do much better as this class is highly inefficient.

The above implementation works but it wastes space. As the start Index moves, more and more space is wasted even if the elements before the start index may be empty. This is likely to be unacceptable. What happens if we have a space limitation? How can this be addressed?

A Circular FIFO / Ring Buffer / Circular Queue

To address these problems, we create a Circular FIFO aka Ring Buffer aka Circular Queue. A Ring Buffer uses a fixed-size array with two pointers. One pointer acts as a read head while one acts as a write head. The goal is to reuse the empty storage. This is one of the most important data-structures in audio programming.

I am sorry but I really did not want to make a .gif or animation of this. I have linked a YouTube animation that I think demonstrates this well.

Now here is another video from Timur Doumler about a special implementation of the ring-buffer in audio. We will come back to this video in the future but at this current time, I want you to just pay attention to his overall explanation of the ring buffer. You should be starting at 54:27 :

A Basic Circular FIFO Data Structure

The following code should outline a basic Circular FIFO as we have discussed so far. Please note the utility function of isEmpty() and isFull() which are important conditions to observe. While there is a std::queue data structure in the standard C++ library, I want to use std::vector as we will revisit this basic idea later.

class RingBuffer
{
private:
    vector<float> containerRingBuffer;
    int readIndex;
    int writeIndex;
    int size;
    
    bool isEmpty()
    {
        /* check if the buffer is empty or not. */
        return readIndex == -1;
    }
    
    bool isFull()
    {
        /* check if the buffer is full or not. */
        return ((writeIndex + 1) % size) == readIndex;
    }
    
public:
    RingBuffer(int inputSizeValue)
    {
        size = inputSizeValue;
        containerRingBuffer.resize(size);
        readIndex = -1;
        writeIndex = -1;
    }
    
    bool enqueueValue(float inputValue)
    {
        /* insert an element into the circular queue.
        return true if the operation is successful. */
        if (isFull())
        {
            return false;
        }
        if (isEmpty())
        {
            readIndex = 0;
        }
        writeIndex = (writeIndex + 1) % size;
        containerRingBuffer[writeIndex] = inputValue;
        return true;
    }
    
    bool dequeueValue()
    {
        /* delete an element from the circular queue.
        return true if the operation is successful. */
        if (isEmpty())
        {
            return false;
        }
        if (readIndex == writeIndex)
        {
            readIndex = -1;
            writeIndex = -1;
            return true;
        }
        readIndex = (readIndex + 1) % size;
        return true;
    }
};

I would not recommend that you normally build these data structures on your own. The C++ STL comes with all of the basic data structures you will require to solve problems and implement prototype algorithms. For this reason, I hope you take the time to understand std::queue and std::priority_queue. While it is unlikely that you will use these to build audio software, it is likely that you can prototype out a calculation using these standard data structures.

Conclusion

This article was meant to serve as a small introduction and guide to LIFO and FIFO data-structures. There is a good chance, as an audio programmer, that you will be asked to solve questions using these data structures. I aim to go through some practice coding interview questions which employ these data-structures as it helps to recognize when to use certain data-structures. After that, I want to introduce you to some C++ specific implementations concerning these data-structures and audio. Until then:

Be good to each other and take it easy…

-Will ☜(゚ヮ゚☜)

Liked it? Take a second to support William Fehlhaber on Patreon!

Shopping cart

Subtotal
Shipping and discount codes are added at checkout.
Checkout

Sign up here to learn about our premium courses and more!

 

Thank you for being a part of The Audio Programmer Community!