Non-recursive Backtrack using Queue: runs out of memory

Question

I have tried to implement a backtracking example program by using a std::queue container, in the C++11 dialect.

However there is a coding mistake somewhere in the algorithm that causes the program to run out of memory. What is that mistake?

In the code sample below, the functions reject(), accept(), first_child() and next_child() may be assumed to work correctly, because they have been tested successfully with recursive and std::stack container implementations of backtracking.

// helper functions
bool reject(const std::string &c);
bool accept(const std::string &c);
const std::string * first_child(const std::string &c);  // nullptr == no child
const std::string * next_child(const std::string &c);   // nullptr == no child

void backtrack_que(const std::string &start)
try
{
    std::queue<std::string> que;

    que.push(start);

    while (!que.empty())
    {
        if (reject(que.front()))
        {
            que.pop();
            continue;
        }

        if (accept(que.front()))
            std::cout << que.front() << '\n';

        const std::string *p_child(first_child(que.front()));

        que.pop();

        if (p_child != nullptr)
        {
            que.push(*p_child);

            const std::string *p_sibling(next_child(que.back()));

            while (p_sibling != nullptr)
            {
                que.push(*p_sibling);
                p_sibling = next_child(que.back());
            }
        }
    }
}
catch (...)
{
    std::cerr << "unknown exception in `" << __func__ << '`' << std::endl;
    throw;
}

Answer 1

I have performed a simple counting test and found that @IgorTandetnik was accurate regarding the Queue variant: it reached 60+ million maximum size.

Surprisingly to me, the Stack variant didn't exceed 200. Upon revisiting the code I concluded that this is due to how the Stack variant "rushes" to last possible child while the Queue variant accumulates a great number of children before going further to the next generation: in more computer-sciency terms, Stack does Depth-First Search while Queue does Breadth-First Search.

Also surprising was that, apparently, the traditional Recursive variant seems to be the most efficient and also the fastest.

max recursion depth for bt-rec: 6
max container size for bt-stk:  176
max container size for bt-que:  60466176