Match a simple balanced language using a queue
As Konrad Rudolph points out in comments on the other question, this is probably about Pushdown Automata, for which the wikipedia page has some useful examples, and this stackoverflow answer is very helpful.



Using a stack

The stack is used to preserve data while iterating along the input. We move left-to-right from character to character, making a decision based on the current character, and the contents of the stack.

If the input becomes invalid at a certain point (e.g. it contains a 'c', or has too many 'b's, etc.), we can reject it. Otherwise we continue until we have processed the entire input.

For the instructions you've been given, we don't actually need a stack. A counter would suffice. However, a stack would allow balancing multiple sets of characters (e.g. balancing strings of parentheses ([]())[]).

At every 'a' we encounter, we push it onto the stack. At every 'b' we encounter, we pop one off the stack. If we are ever attempting to pop something off an empty stack, the input is not balanced. At the end of the input, the stack must be empty (we popped off the same number of 'b's as the number of 'a's we pushed on).

bool is_balanced(std::string const&amp; input)
{
    if (input.empty()) // n == 0
        return false;

    std::stack&lt;char&gt; stack;
    bool is_first_word = true;

    for (auto c : input)
        if (!pda(stack, is_first_word, c))
            return false;

    return stack.empty();
}




The queue

As you noticed, having the input contained in a queue limits how it can be processed. We don't know the length of the input in advance. We can only pop off one character at a time and process it.

More usually in C++, input like this would come from a stream of some sort.

Note, however, that the core of the algorithm remains exactly the same:

bool is_balanced(std::queue&lt;char&gt;&amp; input)
{
    if (input.empty()) // n == 0
        return false;

    std::stack&lt;char&gt; stack;
    bool is_first_word = true;

    while (!input.empty())
    {
        auto c = input.front();
        input.pop();

        if (!pda(stack, is_first_word, c))
            return false;
    }

    return stack.empty();
}




Making Decisions

The details of the pda function are left to the reader ;) , but it looks something like this:

bool pda(std::stack&lt;char&gt;&amp; stack, bool&amp; is_first_word, char c)
{
    if (c == 'a')
    {
        // check the stack, push / pop, return true / false
    }
    else if (c == 'b')
    {
        // check the stack, push / pop, return true / false
    }
    else
        return false; // invalid character
}


It checks the current character 'c', checks the stack, and pushes / pops if necessary. It returns true if we should keep processing input, and false otherwise.



Weird Things

There are a few slightly unusual things about the instructions you've been given:


Empty input is invalid (n must be >= 1). Often an empty input would be considered a balanced string. This is a simple check to make though.
Only 'a' and 'b' characters means the stack is technically redundant. Usually one would think about balancing parentheses, as in the linked stackoverflow question.
The wording implies that inputs like "abab" are invalid, as this would be considered more than one "word" in the specified language. This is the reason for the is_first_word boolean above. It might be simpler to just ignore this to start with.