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();
        }
        /*add new value*/
        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 ☜(゚ヮ゚☜)

Privacy Preference Center

Necessary

These cookies are used to record GDPR choices and to provide the minimum necessary functioning of the website for both logged-in and non-logged in users. The third party cookies from Google power the search engine on our site.

wpc_wpc, wp_api_sec, _wpndash, wordpress_logged_in, recognized_logins, G_ENABLED_IDPS, usprivacy, wordpress_sec, wp_api, tk_ai, gdpr[consent_types], wp-settings-time-20, wp-settings-20, gdprprivacy_bar, wordpress_test_cookie, gdpr[allowed_cookies], wp-settings.time-1, last_active_role,
ANID, 1P_JAR, CGIC,DV, SEARCH_SAMESITE

Analytics

Part of our website uses Google cookies to provide site analytics (how our website is used). This helps us to improve our website and create content suitable for all our visitors. You can learn more about how Google uses cookies, and how to manage them at
https://policies.google.com/technologies/types?hl=en-US

_gat_gtag_UA*, _ga, _gid, , CONSENT
__Secure-3PSIDCC, __Secure-3PSID, SIDCC, __Secure-3PAPISID, SSID, SAPISID, APISID, SID, NID, OTZ, COMPASS

Learning Content

We use Dropbox to deliver some of our paid for learning content. This places cookies on our website managed by Dropbox.

jar, locale, __Host-js_csrf, t, lid, last_active_role, bjar

Shopping Cart

These cookies are used to process the payment for paid-for content and to grant access to that content. Our website uses the WooCommerce platform to handle the shopping cart and the PayPal gateway to handle payment processing.

You can find out more about PayPal's cookies (which do not appear on our site) and Privacy Policy by visiting paypal.com/privacy

wp_woocommerce_session, woocommerce_items_in_cart, woocommerce_cart_hash, tk_ai, tk_us, mailchimp_user_mail, mailchimp.cart.current_email

Mailing List Subscriptions

We use a Wordpress plugin to manage our email subscription sign up. We use Mailchimp to handle and manage email to our subscribers, but we don't use their cookies on our site. For more information on MailChimp Cookies, visit https://mailchimp.com/legal/cookies/

et_bloom_optin_optin*, et_bloom_subscribed_to_optin

Marketing and Tracking

_fbp

The Audio Programmer Logo

Connect with the Audio Programmer community and find out about new tutorials, jobs, and events!

You have Successfully Subscribed!