Program to reverse a Queue

Queue is a data structure used for storing collection of data where order in which data is arriving is important. In Queue, insertion and deletion both happened from the different end.
Data insertion are done at one end which is known as “rear end” while data deletion are done at other end known as “front end“. The data which is arrived first will be deleted first in Queue. This data ordering is called as First in First out or FIFO.
Before going ahead have a look into Queue basics and Queue implementation.

Let’s have a look on basic C++ class definition for Queue.

class Queue
{
    private:
        int m_front;
        int m_rear;
        int m_entries;
        int m_max_size;

        int* m_queue;

    public:
        Queue (int max);
        ~Queue ();
        int size ();
        int maxSize ();
        int enqueue (int entry);
        int dequeue ();
        bool isEmpty ();
        int atFront ();

        void print_content ()
        {
            int temp = m_rear;
            while (temp != m_front)
            {
                cout << m_queue[temp] << " ";
                temp = (temp + 1) % m_max_size;
            }
            cout << endl;
        }
};

Reversing a Queue

Here we have to reverse the order of elements present in the Queue which means front elements should go to rear of queue and vice-versa. Let’s look into an example to understand it better.

As shown in above example, top queue is the given queue and bottom queue is the final queue in which elements are reversed.

Reversing a Queue using another Queue

In this method, we are going to reverse the order of elements present in the queue using another queue.

Algorithm

• Define a recursive function which takes both queue pointer as an argument.
• If source queue is empty then return.
• Dequeue element from source queue.
• Call the recursive function again.
• Enqueue the earlier dequeued element in the final Queue.
• Final Queue will have all the elements which are in reverse order.

Few of the functions used below are explained in Queue Implementation. Refer those before going ahead.
Let’s look into the sample code.

void reverse_queue_using_queue (Queue* q, Queue* final)
{
    if (q -> isEmpty ())
        return;

    int data = q -> dequeue ();
    reverse_queue_using_queue (q, final);
    final -> enqueue (data);
}

Let’s define a main function to use above methods.

int main ()
{
    Queue q(10);
    Queue final(10);
    q.enqueue (1);
    q.enqueue (2);
    q.enqueue (3);
    q.enqueue (4);
    q.enqueue (5);
    q.enqueue (6);
    q.enqueue (7);
    cout << "Queue content initially " << endl;
    q.print_content ();
    reverse_queue_using_queue (&q, &final);
    cout << "Queue content finally " << endl;
    final.print_content ();
}

Let’s analyze the output of this main function.

Queue content initially 
1 2 3 4 5 6 7 
Queue content finally 
7 6 5 4 3 2 1 

Reversing a Queue using Stack

In this method, we are going to reverse the order of elements present in the queue using Stack.

Algorithm

• Dequeue all items from Queue and PUSH these into Stack sequentially.
• POP all items from Stack and enqueue into the Queue sequentially.
• Queue will have all the elements in reverse order.

Few of the functions used below are explained in Queue Implementation and Stack implementation. Refer those before going ahead.
Let’s look into the sample code.

void reverse_queue (Queue* q)
{
    if (q->isEmpty ())
    {
        cout << "Queue is empty" << endl;
    }

    cout << "Queue content initially " << endl;
    q -> print_content ();
    Stack s(q -> maxSize ());

    while (!q -> isEmpty ())
    {
        int data = q -> dequeue ();
        s.push (data);
    }

    while (!s.isEmpty ())
    {
        int data = s.pop ();
        q -> enqueue (data);
    }
    cout << "Queue content finally " << endl;
    q -> print_content ();
}

Let’s define a main function to use above methods.

int main ()
{
    Queue q(10);
    q.enqueue (1);
    q.enqueue (2);
    q.enqueue (3);
    q.enqueue (4);
    q.enqueue (5);
    q.enqueue (6);
    q.enqueue (7);
    reverse_queue (&q);
}

Let’s analyze the output of this main function.

Queue content initially 
1 2 3 4 5 6 7 
Queue content finally 
7 6 5 4 3 2 1 

Reversing a Queue without any extra data structure

In this method, we are going to reverse the order of elements present in the queue without using stack or any other queue.

Algorithm

• Define a recursive function which takes queue pointer as an argument.
• If source queue is empty then return.
• Dequeue element from source queue.
• Call the recursive function again.
• Enqueue the earlier dequeued element in the Queue.
• Queue will have all the elements which are in reverse order.

Few of the functions used below are explained in Queue Implementation. Refer those before going ahead.
Let’s look into the sample code.

void reverse_queue_simple (Queue* q)
{
    if (q -> isEmpty ())
        return;

    int data = q -> dequeue ();
    reverse_queue_simple (q);
    q -> enqueue (data);
}

Let’s define a main function to use above methods.

int main ()
{
    Queue q(10);
    q.enqueue (1);
    q.enqueue (2);
    q.enqueue (3);
    q.enqueue (4);
    q.enqueue (5);
    q.enqueue (6);
    q.enqueue (7);
    cout << "Queue content initially " << endl;
    q.print_content ();
    reverse_queue_simple (&q);
    cout << "Queue content finally " << endl;
    q.print_content ();
}

Let’s analyze the output of this main function.

Queue content initially 
1 2 3 4 5 6 7 
Queue content finally 
7 6 5 4 3 2 1