reverse of a queue in c++

Question

this is a question from a exam paper i got stuck in below i have attached the question although i wasnt able to complete i have done some of it.

question:

Using the following class definitions of stack and queue classes write a templated function reverseQueue(?), that takes a pointer to queue as a parameter and uses stack object (or pointer to a stack object) to reverse the given queue. The function call to reverseQueue should reverse the data of the queue passed as a parameter. [Hint: Just call appropriate methods given below in your reverseQueue(?) function. You do not have to write implementation code for stack and queue classes/methods given below. Just read what each method does and use them according to your need.]

template <class T>
struct NODE {
    NODE<T> *pNext;
    T Data;
};

template <class T>
class stack{
    private:
       NODE<T> * top;

    public:
       stack();
       ~stack();
       void push (T data); //pushes a new node with data type //T in a stack
       bool pop (T &data); //pops out the top most node from //the stack
       void printStack(); //prints all elements of a stack
};

template <class T>
class queue {
    private:
        NODE<T> * front;
        NODE<T> * tail;
    public:
        queue ();
        ~queue();
        bool dequeue ( T & data); //removes first node from //a queue
        bool enqueue (T val); //appends a new node in a //queue
};

my answer is incomplete as i could not proceed further below is my answer whatever i have done

template <class T>
void reverseQueue(queue <T> *ptr){
    stack <T> *stackptr= new stack<T>;
    T temp;
    while(ptr->front !=NULL){

        temp=ptr->Data;
        ptr->dequee(ptr->Data);
        stackptr->push(temp);

     }

    // incomplete code
} 

if anyone can give the answer that would be great

Solution

Suppose the input queue looks like

 1    2    3    4
 ^              ^
front           back

If we dequeue the items from it, we will get 1, 2, 3, 4.

Suppose now that we push these items onto a stack as we dequeue them.
It would look like this:

4  <- top
3
2
1  <- bottom

If we pop these, we will get 4, 3, 2, 1.

Now, if we enqueue these in a queue as we pop them from the stack, we will get

 4    3    2    1
 ^              ^
front           back

which is the reverse of the original queue.

Something like this should do it:

template <class T>
void reverseQueue(queue <T> *q){
    stack <T> s;
    T temp;
    // First build a stack (LIFO queue) from the (FIFO) queue.
    while (q->dequeue(temp))
    {
        s.push(temp);
    }
    // The first item in the queue is now at the bottom of the stack.
    // The last item is at the top.
    // The queue is empty.

    // If we enqueue them again they will be reversed.
    while (s.pop(temp))
    {
        q->enqueue(temp);
    }
} 

Comments

[jxh]

Space complexity is actually constant.

[glaze]

Yes it can be constant if we implement it differently, but in my solution it is still O(n) as I am putting all in the stack in the 1st while loop.

[molbdnilo]

@glaze You're removing each item from the queue, so the space used is constant.

[rici]

Writing while(true){if(c){s;}else{break;}) instead of while(c)s; isn't good style. It borders on obfuscation.