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.

Answers Code

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 Code
int 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
Copyright ©2022 Educative, Inc. All rights reserved

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.

Answers Code
Keep Exploring