Solution: Reverse a Queue

Grokking Data Structures & Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Reverse a Queue

Table of Contents

Contents are not accessible

Problem Statement

Given a queue containing integer elements, return the updated queue after reversing its elements.

Examples

Example 1

Input: queue = [1, 2, 3, 4, 5]
Expected Output: [5, 4, 3, 2, 1]
Explanation: The input queue elements are reversed.

Example 2

Input: queue = [10, 20, 30, 40, 50]
Expected Output: [50, 40, 30, 20, 10]
Explanation: The input queue elements are reversed.

Example 3

Input: queue = [5, 7, 12, 2, 4, 5]
Expected Output: [5, 4, 2, 12, 7, 5]
Explanation: The input queue elements are reversed.

Solution

The given Java program reverses the order of elements in a queue using a stack. The idea is to first transfer all the elements from the queue to a stack, which inherently reverses their order due to the Last-In-First-Out (LIFO) nature of a stack. Once all the elements are in the stack, they are popped back into the queue, thus reversing their original order. This approach efficiently leverages the stack's properties to achieve the desired outcome, ensuring that the elements in the queue are reversed.

Step-by-Step Algorithm

Initialize Stack:
- Create an empty Stack<Integer> named stack.
Transfer Elements to Stack:
- While the queue is not empty:
  - Remove the front element from the queue using remove().
  - Push this element onto the stack using stack.add().
Transfer Elements Back to Queue:
- While the stack is not empty:
  - Pop the top element from the stack using stack.pop().
  - Add this element back to the queue using queue.add().
Return the Queue:
- The queue now contains the elements in reversed order. Return the modified queue.

Algorithm Walkthrough

1 of 11

Code

Here is how we can implement this algorithm:

Python3

. . . .

Complexity Analysis

Time Complexity

Transferring elements from the queue to the stack: The first while loop iterates over all elements in the queue and pushes them onto the stack. This takes $O(N)$ time, where N is the number of elements in the queue.
Transferring elements back from the stack to the queue: The second while loop pops elements from the stack and adds them back to the queue. This also takes $O(N)$ time.
Therefore, the overall time complexity is $O(N + N) = O(N)$ .

Overall time complexity: $O(N)$ .

Space Complexity

Stack space: The stack is used to store the elements from the queue. Since the stack holds all N elements from the queue, the space required is $O(N)$ .
Queue space: The queue already holds N elements, but since we are using the same queue for input and output, this does not count as additional space.

Overall space complexity: $O(N)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible