Help me understand this algorithm (simple)

I have just made a queue class and I now have to use it to do this.

Write a c++ program to generate all strings using A,B,and C as the letters.

The strings must be generated in the following order: A B C AA AB AC BA BB BC CA CB CC AAA AAB AAC ABA ABB ABC ACA ACB ACC etc.

It's supposed to do this until my queue overflows.

Now, I simply don't understand the algorithm the teacher suggested using, which is this.

Start with A and B and C in the queue. “Remove it Display it then Add Add Ad开发者_高级运维d ”

The add add add thing throws me off, how does it accomplish getting these letters in this particular order?

I think your teacher meant "Add A, Add B, Add C".

Suppose you have A, B and C in the queue. You pop the first one off the queue and print it. This should print A. Then you add an A to that. This gives you AA, which you push back into the queue. You also add a B and add a C to the string you popped last (giving you AB and AC) and push them back into the queue as well. Now your queue contains [B,C,AA,AB,AC]. Next you will pop B and do the same sequence of operations on that as well, and so on until you run out of space in your stack.

Let our behavior be:

For any token X, add XA, XB, and XC to the queue.

Our flow will be something like:

Start with a Queue
A B C

Pop (and display) off A
B C

Behave on token: "A"
  add AA
  add AB
  add AC
B C AA AB AC

Pop (and display) off B
C AA AB AC
  add BA
  add BB
  add BC
C AA AB AC BA BB BC

If we pretend our function is

main() {
    Queue q;
    q.add("A");
    q.add("B");
    q.add("C");

    while(true) {
        process(q.pop());
    }
}

process(String x, Queue q) {
    display x;
    q.add(x + "A");
    q.add(x + "B");
    q.add(x + "C");
}

Get it now?

A B C

prints A new queue state B C A A A

prints B new queue state C A A A B B B

prints C new queue state A A A B B B C C C

prints A new queue state A A B B B C C C A A A

prints A new queue state A B B B C C C A A A A A A

prints A new queue state B B B C C C A A A A A A A A A

This was my first interpretation of the cycle, but i must be getting it wrong, because i go from 1 repeat to 3 right away.

Update: definitely read the initial problem wrong after seeing the other responses.