Program to reverse a queue

An algorithm to reverse a queue.

We will implement an algorithm to reverse a queue in javascript using a stack. Everything will be written in ES6.

Example

Input:
1 2 3 4 5 6 7 8 9 10

Output:
10 9 8 7 6 5 4 3 2 1

Implementation

  • First we will add all the items from the queue into the stack.
  • Then we will remove all the items from the stack and again add it into the queue.
let reverseQueue = (queue) => {
  
  //Use a stack to reverse the queue
  let stack = new Stack();
  
  //Push all the items of the queue to the stack
  while(!queue.isEmpty()){
    stack.push(queue.dequeue());
  }
  
  //Again push all the items from the stack into the queue
  while(!stack.isEmpty()){
    queue.enqueue(stack.pop());
  }
  
  return queue;
}
Input:
let queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
queue.enqueue(6);
queue.enqueue(7);
queue.enqueue(8);
queue.enqueue(9);
queue.enqueue(10);
let reversed = reverseQueue(queue);
reversed.print();

Output:
"10,9,8,7,6,5,4,3,2,1"

Time complexity: O(n).
Space complexity: O(n).

Time and Space complexity

  • We are first copying all the elements of the queue into the stack which will take O(n), Then we are again copying all the elements from the stack into the queue which will also take O(n), so Time complexity is O(n + n) = O(n).
  • We are using stack to store all the copied elements, so Space complexity is O(n).

Leave a Reply

Your email address will not be published. Required fields are marked *