Reversing a Queue

Table of Contents

Introduction

Reversing a Queue is one of the most fundamental questions in the queue it is generally not asked directly in interviews but is used to solve various questions asked in interviews. It is crucial to understand the in and out of reversing a queue.

A formal Statement of the problem we need to solve is

You have been given a queue of ‘N’ distinct integers. For a given queue, you need to reverse all the elements in it.

Example

Input:    Queue=  [1,2,3,4,5,6,7,8,9]
Output: Queue= [9,8,7,6,5,4,3,2,1]

Explanation: The output queue is the reverse of the input queue

Before moving on to the solution, let’s discuss some basics about the queue

Queue

A queue is a linear data structure like an array and linked list that follows a particular order to insert and retrieve elements. The order is First In First Out(FIFO). The queue data structure is the same as a queue in the real world in which a person who enters first is served first.

Basic Operations on Queue:

Four basic operations can be performed on a queue,

Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.

Dequeue: Removes an item from the queue. The items are removed in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.

Front: Get the front item from the queue.

Rear: Get the last item from the queue.

Now we know basic operations on Queue, so without any further ado, let’s discuss solutions and approaches for reversing a queue.

Reversing a Queue: Using Stack

We know that a queue is a FIFO structure, and random access of elements is not allowed, so it is not possible to reverse the queue in-place so we need another data structure in which we could store the elements of the queue in such a manner that while inserting the elements back to the queue the order of elements is reversed. So our aim is to find a data structure that could help in reversing a queue and has a property of LIFO(Last In First Out). Do you know such a data structure?

You guessed it right! Stack is the data structure that can fulfill our requirement and help us to reverse the queue. So in this approach for reversing a queue, we will dequeue all the elements of the queue and push them into the stack, and once the queue is empty, we will pop elements from the stack and insert them in the queue.

Code:

#include<iostream>
#include<stack>
#include<queue>
using namespace std;

void reverse(queue<int> &q)
{

    // Explicitly create a stack.
    stack<int> st;

    // Push all elements of the queue into the stack.
    while (!q.empty())
    {
        st.push(q.front());
        q.pop();
    }

    // Push back all elements from the stack into the queue.
    while (!st.empty())
    {
        q.push(st.top());
        st.pop();
    }
}

void printQueue(queue<int> q)
{

    while(!q.empty())
    {
        cout<<q.front()<<" ";
        q.pop();
    }
    cout<<endl;
}

int main()
{
    queue<int> q;
    //inserting elements into the queue using loop
    for(int i=1;i<=10;i++)
    {
        q.push(i);
    }
    cout<<"Queue before Reversing: ";
    printQueue(q);
    
    reverse(q);

    cout<<"Queue after Reversing: ";
    printQueue(q);
}

Output:

Queue before Reversing: 1 2 3 4 5 6 7 8 9 10 
Queue after Reversing: 10 9 8 7 6 5 4 3 2 1

Time Complexity: O(n) where n is the size of the queue as we are iterating the queue once.

Space Complexity: O(n) as we are storing the elements of the queue in the stack.

Reversing a Queue: Using Recursion

In this approach, instead of creating a stack explicitly, we will use the concept of recursion. The idea is to remove the front element from the queue and recursively call the reverse function for the remaining queue. In this way, we are dividing the larger problem into smaller sub-problems. We will pop the elements from the queue until it becomes empty, which is our base condition for a recursive function.

Once the queue is empty, push the elements back into the queue in this way, we will be able to reverse the elements as in the recursive function stack, the element that was popped at last would be pushed first and would be at the front of the queue.

Code:

#include<iostream>
#include<stack>
#include<queue>
using namespace std;

void reverse(queue < int > & q) {
    if (q.empty()) {

        // If the queue is empty, return.
        return;
    }

    // Store the front element in a variable.
    int element = q.front();
    q.pop();

    // Recursively call for the rest of the queue.
    reverse(q);

    // Push back the stored element.
    q.push(element);
}


void printQueue(queue<int> q)
{

    while(!q.empty())
    {
        cout<<q.front()<<" ";
        q.pop();
    }
    cout<<endl;
}

int main()
{
    queue<int> q;
    for(int i=1;i<=10;i++)
    {
        q.push(i);
    }
    cout<<"Queue before Reversing: ";
    printQueue(q);
   
    reverse(q);

    cout<<"Queue after Reversing: ";
    printQueue(q);
}

Output:

Queue before Reversing: 1 2 3 4 5 6 7 8 9 10 
Queue after Reversing: 10 9 8 7 6 5 4 3 2 1

Time Complexity: O(n) where n is the size of the queue as we make the recursive calls for each element once and perform operations in constant time.

Space Complexity: O(n) if we consider the function call stack else O(1).

Key Takeaways

This blog covered the various methods of reversing a queue. We discussed two approaches for reversing a queue, namely: Using stack and Using recursion. The blog discusses approaches with algorithms and code in c++.

Don’t stop here. Check out our Data Structures and Algorithms -guided path to learning DSA from scratch. We hope you found this blog useful. If you want to solve more problems like this which have been asked in the interviews, big tech giants like Amazon, Flipkart, Google, and Facebook, you can look out for interview problems at CodeStudio.

By: Pranchal Agrahari