recursion in queue

[vedanshu]

today in my university paper i got this code and was asked what's it doing??

void f(queue q)
{
  int i;
  if(!isempty(q))
  {
    i=delete(q);
    f(q);
    insert(q,i);
  }
}

ps: please dont mind the fact that we cant declare a function named delete. (paper setter was drunk at the tym of designing the paper)

according to me it should reverse the queue but most of my friends are convinced that it is just deleting the queue!!!

what it is doing actually (there are too many error to actually compile this prog and make it run)

[vlad from moscow]

It does nothing because the queue is passed by value.

[Peter87]

I think this is pseudo code and you are right that it reverses the queue.

[vedanshu]

It does nothing because the queue is passed by value.

:)
well the examiner declared a function named delete so i guess that's the least of his issues..
i just want to ask what it would've done if we neglected the baby mistakes
if it is doing what i think it is doing then it is a cool way to do this

please assume that queue is passed by referrence and/or gloablly declared or whatever
i want the conceptual answer for this
thnx...

[vlad from moscow]

Well, if the queue is passed by reference then it is enough to consider one iteration of the function call

i=delete(q);
f(q);
insert(q,i);

A value is deleted from the beginning of the queue and inserted in the end of the queue.
So let the queue has

1, 2, 3, 4, 5, 6

At first all elements of the queue are deleted

then they are inserted in the order

6, 5, 4, 3, 2, 1

[vedanshu]

I think this is pseudo code and you are right that it reverses the queue.

some of my friends are saying that insert function in never executed.
after last attiration at which it is emptied out console goes back to main function..
( i cant understand this )

[vlad from moscow]

No, the control will be passed back to the calling function. As I said it shall be defined as

void f( queue &q )
{
int i;
if(!isempty(q))
{
i=delete(q);
f(q);
insert(q,i);
}
}

[vlad from moscow]

For example you can test the function by using standard container std::queue.

void reverse_queue( std::queue<int> &q )
{
	if ( !q.empty() )
	{
		int x = q.front();
		q.pop();
		reverse_queue( q );
		q.push( x );
	}
}

If you have MS VC++ compiler then the queue contains public method _Get_container. You can use it to be sure that the queue was reversed. For example

#include <iostream>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <queue>

void reverse_queue( std::queue<int> &q )
{
	if ( !q.empty() )
	{
		int x = q.front();
		q.pop();
		reverse_queue( q );
		q.push( x );
	}
}

int main()
{
	std::deque<int> d( 10 );

	std::iota( d.begin(), d.end(), 0 );

	std::copy( d.begin(), d.end(),
	           std::ostream_iterator<int>( std::cout, " " ) );
	std::cout << std::endl;

	std::queue<int> q( d );

	reverse_queue( q );

	d = q._Get_container();

	std::copy( d.begin(), d.end(),
	           std::ostream_iterator<int>( std::cout, " " ) );
	std::cout << std::endl;
}

The output is

0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

[bradw]

I had to re-write it with queue operations.

f( queue & q )
{
	if (!q.empty())
	{
		int i = q.dequeue();
		f(q);
		q.enqueue(i);
	}
}

some of my friends are saying that insert function in never executed.

Not true! See below, insert is called after f(q) catches its base-case (q being empty).

after last attiration at which it is emptied out console goes back to main function..

It is going to call insert for each instance of recursion "on its way out" after f(q) stopps getting called.

Below I expanded the function so you could see the recursion.

Example:
q = {1, 2, 3}

f( queue & q )
{
    if (!q.empty())
    {
        int i = q.dequeue();
        // i = 1

        f( queue & q )
        {
            if (!q.empty())
            {
                int i = q.dequeue();
                // i = 2
				
                f( queue & q )
                {
                    if (!q.empty())
                    {
                        int i = q.dequeue();
                        // i = 3
						
                        f( queue & q )
                        {
                            if (!q.empty())		// false condition!
                            {			// code skipped!
                                int i = q.dequeue();
                                f(q);		// not called
                                q.enqueue(i);
                            }            // execution continues below
                        }
						
                        // i = 3
                        q.enqueue(i);
                        // q = {3}
                    }
                }
				
                // i = 2
                q.enqueue(i);
                // q = {3, 2}
            }
        }
		
        // i = 1
        q.enqueue(i);
        // q = {3, 2, 1}
    }
}

q = {3, 2, 1}

[vlad from moscow]

If to return to the original code it can work without passing q by reference. It depends on the type of queue. For example it could be declared as

typedef base_queue *queue;

where base_queue is the actual definition of the container.

[vedanshu]

yes it is reversing..
thnx for the help guys :).......