Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

queue

# Which data structure can be used to reverse a queue? Adnan Abbas

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.   ## Problem

We want to reverse the elements present in a queue.

## Input

A queue of integers

## Return value

A queue of reversed integers.

Expected behavior of the function.

## Data structure and solution

• We will use an additional output queue to reverse the input queue. The last element of the input queue should be the head of the empty queue.
• We traverse the input queue and add the last element to the output queue. To do this, we pop the input queue one by one for size -1 times.
• When we get the last element, we pop it out from the input queue and push it to the output queue.
• This process is repeated until the input queue is empty.

This is shown as follows:

// C++ implementation of the function #include <bits/stdc++.h>using namespace std; // Function to reverse the input queue and return the reversed queue.queue<int> reverseQueue(queue<int> q){  // Size of queue  int s = q.size();  // Second queue  queue<int> output;  while(!q.empty()) {    // Get the last element to the front of queue    for (int j = 0; j < q.size() - 1; j++) {        int x = q.front();        q.pop();        q.push(x);    }    // Get the last element and    // add it to the output queue    output.push(q.front());    q.pop();  }  return output;} // Driver Codeint main(){  queue<int> q;  // Inserting elements  q.push(1);  q.push(2);  q.push(3);  q.push(4);  q = reverseQueue(q);  // Printing the queue  while (!q.empty()) {    cout << q.front() << " ";    q.pop();  }  return 0;}

RELATED TAGS

queue

CONTRIBUTOR Adnan Abbas    