how is this queue being implemented?

[thewalrus]

public:
Queue() : front(0), back(0)
{}

void put(TreeNode *ptn)
{
    ListNode *tmp = new ListNode(ptn, 0);
    if (back == 0)
        front = tmp;
    else
        back->next = tmp;
    back = tmp;
}

TreeNode *get()


{
    assert(front);
    TreeNode *result = front->ptn;
    ListNode *tmp = front->next;
    delete front;
    front = tmp;
    if (front == 0)
    back = 0;
    return result;
}

I don't understand what put is supposed to do, because we're putting temp in back as well as the front at the beginning and then we're putting temp in the back and to the node pointed by back.

[StuXYZ]

Ok this is a standard top-tail queue. Let us walk through the process of putting objects into the queue and taking them off again to see how it works:

The important variabes are front/back.

Empty Case

Let us first conside the test case that you build an empty queue: front=back=0, if get is called the assert fails and error messages is produced.

One Element case

Next case: we add one elements [address of new ListNode N1] : we do that via put. front = back = N1 . back does not have its next ptr set so we will assume it is left as zero.

Now let us remove that object: get correctly applied that result is a COPY of the memory given in put [this is necessary because we are about to delete that memory record -- there are other ways of doing it.]
tmp is set to zero -- back->next was not set for one element.
front is deleted [there was only one object] front/back =0 which means
we have returned to the empty queue state.

Two+ Element case

Now let us add two (or more elements). Start from the state after adding one element, back is NOT zero, so back->next is set to N2. But careful, back is the reasined to N2 afterwards at the point of setting back->next to N2,back is actually pointing to N1 !! . So we have

   N1->next   : N2
   N2->next   : 0
   back       : N2
   from       : N1

at the end of the second call to put.

IF we add one more element we get:

N1->next : N2
N2->next : N3
N3->next : 0
back     : N3
front    : N1

Now we just have to consider the get case:

result is set to the data for N1. [we take from the front of the queue, this is not a last in first out queue (LIFO).] tmp becomes N2, N1 is deleted and front is set to N2. resulting in :

 N2->next : N3
 N3->next : 0
 front : N2
 back  : N3

One more call to get and we have:

 N3->next : 0
 front : 0
 back : 0

I assume that other options are being done with back because it is unnecessary to get the same logic.

Hopefully that help ... if not I suggest (a) reitereting the question a bit (b) writing a little write function to create the little tables I have done in the post, to see how it works.

[thewalrus]

thanks i got it now