An algorithm to sort a stack using temporary stack.
We will implement a simple algorithm to sort a stack using another temporary stack in javascript. Everything will be written in ES6.
Example
Input: 5, 10 ,17, 11, 2, 23 Output: 23, 17, 11, 10, 5, 2
Implementation
- We will create a temporary stack.
- Then we will loop through while input stack is not empty.
- In each iteration if temporary stack is not empty and its top item is greater than input stack then we will swap them.
let sortStack = (stack) => {
//create a temporary stack
let tempStack = new Stack();
//loop while stack is not empty
while(!stack.isEmpty()){
// pop out the first element
let tmp = stack.pop();
// while temporary stack is not empty and
// top of stack is greater than temp
// change > to < for sorting in ascending order
while(!tempStack.isEmpty() && tempStack.peek() > tmp){
// pop from temporary stack and
// push it to the input stack
stack.push(tempStack.pop());
}
// push temp in tempory of stack
tempStack.push(tmp);
}
return tempStack;
}
Input:
let stack = new Stack();
stack.push(5);
stack.push(10);
stack.push(17);
stack.push(11);
stack.push(23);
stack.push(2);
let sorted = sortStack(stack);
while(!sorted.isEmpty()){
console.log(sorted.pop());
}
Output:
23
17
11
10
5
2
If you want to sort in ascending order then update to this while(!tempStack.isEmpty() && tempStack.peek() < tmp).
Time complexity: O(n).
Space complexity: O(n).
