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).