Log inSign up
easyGeeksforGeeksNot Started

Queue Reversal

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Queue
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a Queue Q containing N elements, the task is to reverse the Queue. Your function should reverse the order of elements in the given queue.

Implement the solution function: - Queue<Integer> rev(Queue<Integer> q) which takes the Queue as input parameter and returns the reversed Queue.

Example 1 · Standard Queue Reversal:

Input: Q = [4, 3, 1, 10, 2, 6]
Output: [6, 2, 10, 1, 3, 4]
Explanation: After reversing the given elements of the queue, the resultant queue will be 6 2 10 1 3 4.

Example 2 · Small Queue:

Input: Q = [4, 3, 2, 1]
Output: [1, 2, 3, 4]
Explanation: Reversing [4, 3, 2, 1] gives [1, 2, 3, 4].

Constraints:

  • 1 <= N <= 105
  • 1 <= elements of Queue <= 105

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Queue FIFO Mechanics
  • Stack LIFO Mechanics
  • Basic Recursion

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the interplay between LIFO (Stack) and FIFO (Queue) structures.
  • Understand recursive unwinding for sequence reversal.
  • Choose between heap-safe iterative vs recursive implementations.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Reversing linear sequences using restricted abstract data types.
  • Need to flip FIFO order using standard primitives.

Algorithmic Decision Tree:

  • Iterative: Dequeue all into a Stack, then pop all from Stack into Queue.
  • Recursive: Dequeue front, recurse, then enqueue the saved element.

Connected Patterns:

Reverse First K Elements of QueueImplement Queue using StacksImplement Stack using Queues

1. Brute Force — Array Conversion & Reverse

Intuition

Extract all items to an array, reverse the array, and push back to queue.

Algorithm

  1. Step 1: Dequeue all elements into a list.
  2. Step 2: Reverse the list using two pointers.
  3. Step 3: Enqueue all list elements back into the queue.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <queue>
3#include <vector>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 queue<int> rev(queue<int> q) {
11 vector<int> temp;
12 while (!q.empty()) {
13 temp.push_back(q.front());
14 q.pop();
15 }
16 reverse(temp.begin(), temp.end());
17 for (int x : temp) {
18 q.push(x);
19 }
20 return q;
21 }
22};
23
24int main() {
25 Solution sol;
26 queue<int> q;
27 q.push(4); q.push(3); q.push(1); q.push(10); q.push(2); q.push(6);
28 queue<int> res = sol.rev(q);
29 while (!res.empty()) {
30 cout << res.front() << " ";
31 res.pop();
32 }
33 cout << endl; // 6 2 10 1 3 4
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N) — Dumping into array and reversing takes 2N operations.
  • Space complexity: O(N) — Allocates auxiliary array of size N.

Why Brute Force Doesn't Scale:

Recursion on N = 105 causes segmentation fault / stack overflow.

Explicit iterative stack handles N = 106 elements in 8ms safely on heap memory.

2. Better — Recursive Call Stack Reversal

Intuition

Dequeue front element, recursively reverse remaining queue, then enqueue the saved front element at the back.

Algorithm

  1. Step 1: Base case: if queue is empty, return.
  2. Step 2: Dequeue front element and save in local variable val.
  3. Step 3: Recursively call rev(q).
  4. Step 4: Push val back into queue (lands at the rear).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <queue>
3
4using namespace std;
5
6class Solution {
7public:
8 queue<int> rev(queue<int>& q) {
9 if (q.empty()) return q;
10 int val = q.front();
11 q.pop();
12 rev(q);
13 q.push(val);
14 return q;
15 }
16};
17
18int main() {
19 Solution sol;
20 queue<int> q;
21 q.push(1); q.push(2); q.push(3);
22 sol.rev(q);
23 while (!q.empty()) {
24 cout << q.front() << " ";
25 q.pop();
26 }
27 cout << endl; // 3 2 1
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N) — N recursive calls, each popping and pushing one element.
  • Space complexity: O(N) Recursion Stack — Call stack depth equals queue length N.

3. Optimal — Explicit Auxiliary Stack (Iterative)

Intuition

Push all queue elements into a stack. Popping from stack and pushing back into queue reverses the order iteratively without recursion limits.

Algorithm

  1. Step 1: Initialize an empty stack st.
  2. Step 2: While q is not empty, dequeue from q and push onto st.
  3. Step 3: While st is not empty, pop from st and enqueue into q.
  4. Step 4: Return q.

Stack Inversion Execution Trace

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
All elements moved into stack
Visual state
Values and pointers at this exact step
queue
FRONT → REAR
6 (top)
2
10
1
3
4 (bottom)
Enqueue adds at the rear · Dequeue removes from the front
Decision / next transition
Queue -> Stack
Why this step matters

All elements moved into stack. Top is 6, bottom is 4.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <queue>
3#include <stack>
4
5using namespace std;
6
7class Solution {
8public:
9 queue<int> rev(queue<int> q) {
10 stack<int> st;
11 while (!q.empty()) {
12 st.push(q.front());
13 q.pop();
14 }
15 while (!st.empty()) {
16 q.push(st.top());
17 st.pop();
18 }
19 return q;
20 }
21};
22
23int main() {
24 Solution sol;
25 queue<int> q;
26 q.push(4); q.push(3); q.push(1); q.push(10); q.push(2); q.push(6);
27 queue<int> res = sol.rev(q);
28 while (!res.empty()) {
29 cout << res.front() << " ";
30 res.pop();
31 }
32 cout << endl; // 6 2 10 1 3 4
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) — N pops to stack + N pops to queue = 2N operations.
  • Space complexity: O(N) Explicit Stack — Stack stores N integers on heap.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Array ConversionO(N)O(N)Dump queue into a dynamic array, reverse array with two pointers, and rebuild queue.Array allocation and conversion.
2.Better — Recursive Call StackO(N)O(N) Recursion StackDequeue front element, recursively reverse remainder of queue, then enqueue front element at back.Function call stack depth.
3.Optimal — Explicit Auxiliary Stack (Iterative)OptimalO(N)O(N)Dequeue all elements into an explicit stack, then pop all elements back into the queue.Two linear passes (Queue->Stack, Stack->Queue).

Common Pitfalls & Crucial Edge Cases

Dequeuing into queue directly

Without an intermediate LIFO stack or recursive frame, enqueuing back into the same queue preserves the original order.

Stack overflow on recursion

For N = 105, recursive implementations hit stack overflow; prefer iterative stack for production.

Crucial Edge Cases to Validate:

  • Empty queue — Function returns immediately without throwing null or empty pointer exceptions.
  • Single element queue — Dequeues and re-enqueues 1 element unchanged.
  • Queue with duplicate values — Inverts sequence without affecting frequency of duplicates.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state both approaches: 'We can reverse it recursively using the execution call stack or iteratively using an explicit Stack on the heap.'
  2. Explain stack overflow risks for large input sizes to demonstrate production awareness.
  3. Discuss the trade-off between the recursive call stack vs explicit heap stack for deep recursion depths.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does transferring elements from a Queue to a Stack and back reverse the queue?

2.What is the primary drawback of the recursive approach for reversing a queue?

3.What is the total number of element moves performed in the iterative stack solution?

Back to DSA Sheet