 Select Page

Queues and stacks are fundamental to many algorithms. In this challenge we will be working with std::queue from the STL. For us Audio Programmers, queues are the linking component to everything we do.

C++ is a deep language with a lot to learn. Experimentation, projects and general development practice will catapult you forward. However, sometimes it is important to step back and review some basic computer science and coding challenges. Doing so has helped me think differently about solving problems and appreciate certain aspects of C++ that are easy to forget. This is a part of the reason why I have been practicing extensively on LeetCode.

## The Problem

You can find this problem here. This is part of the Introduction to Data Structure Queue & Stack Card on LeetCode. There are some great explanations on these data structures that I highly suggest taking a look at. I have also written an article on this.

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

### Example:

``````MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3``````

### Starter Code:

``````class MovingAverage {
public:
/** Initialize your data structure here. */
MovingAverage(int size) {

}

double next(int val) {

}
};

/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage obj = new MovingAverage(size);
* double param_1 = obj.next(val);
*/``````

## Breaking It Down

This is a moving average calculation and you can find out more about it here. Moving averages are used all the time in signal analysis or any role where you have time series data. Digital Signal Processing and Finance are two fields where you can expect this type of question. In DSP you will often hear this called a moving average filter, which is essentially a crude low-pass filter.

It is common to address this problem using a queue such as a FIFO. In this case, I would suggest using the std::queue data structure from the STL. While I actually wrote about this data structure in a previous article, I do not suggest you copy paste those classes for a variety of reasons. Do not over complicate this task by building your own generic FIFO class.

Just a word here, there are different types of moving average. There are cumulative moving averages which take into account all of the data submitted. There are weighted moving averages which use a constant set number of values as data and there may be be a weight applied (like a windowing function). All in all, this question is actually neither of those. The number of used values is not constant. However, the basic process of en-queuing a value to use is the main point of this exercise.

## A Simple Solution

The following code block should make for a clear solution. Note that the std::queue class does not allow us to pre-allocate size or check for a size limit. We must create this check ourselves.

``````class MovingAverage {
public:
/** Initialize your data structure here. */
double runningTotal;
unsigned int windowSize;
std::queue<int> buffer;

MovingAverage(unsigned int inputSize) {
/*initialize values*/
runningTotal = 0.0;
windowSize = inputSize;
}

double next(int inputValue) {
/*check if buffer is full*/
if (buffer.size() == windowSize)
{
/*subtract front value from running total*/
runningTotal -= buffer.front();
/*delete value from front of std::queue*/
buffer.pop();
}
buffer.push(inputValue);
/*update running total*/
runningTotal += inputValue;
/*calculate average*/
return static_cast<double>(runningTotal / buffer.size());
}
};``````

Of course, it is possible to handle the runningTotal differently. It is possible to recalculate it every time a value is added. However, this would be inefficient.

## Asymptotic Analysis

I could be wrong concerning space time complexity of this code. It seems to me that this solution uses (in the worst case) a constant amount of space O(1). In the worst case there are only as many values as the windowSize. The time complexity is O(n) in the worst case. This is because the common C++ documentation says:

Constant (amortized time, reallocation may happen).

If a reallocation happens, the reallocation is itself up to linear in the entire size.

push() and pop() both have this complexity. If we assume that reallocation happens every time, then O(n) will happen in two places.

## Conclusion

In this article, I showed you a basic implementation of a std::queue used as a means to filter data. Remember to think through the many C++ data structures that you have available to you before you approach a problem. Also think about how you can relate these problems to our field of Audio Programming. This moving average problem seems like an intuitive introduction as we tend to work with time series data. Until next time:

Be good to each other and take it easy…

-Will ☜(ﾟヮﾟ☜) 