Created
January 13, 2020 08:11
-
-
Save dashsaurabh/d3baf1c955019a1fe4f2eb864d8e4c87 to your computer and use it in GitHub Desktop.
Sort a Stack using Temp Stack
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node { | |
constructor(val) { | |
this.val = val; | |
this.next = null; | |
} | |
} | |
class Stack { | |
constructor() { | |
this.first = null; | |
this.last = null; | |
} | |
push(val) { | |
let newNode = new Node(val); | |
if(this.first === null) { | |
this.first = newNode; | |
this.last = newNode; | |
} else{ | |
newNode.next = this.first; | |
this.first = newNode; | |
} | |
return this.first; | |
} | |
pop() { | |
if (this.first === null) return null; | |
let temp = this.first; | |
if (this.first === this.last) { | |
this.last = null; | |
} | |
this.first = this.first.next; | |
return temp; | |
} | |
peek() { | |
return this.first; | |
} | |
} | |
function sortStack(mainStack, tempStack) { | |
let firstNode = mainStack.pop(); | |
tempStack.push(firstNode.val); | |
while(mainStack.first !== null) { | |
let tempNode = mainStack.pop(); | |
while(tempStack.first !== null) { | |
if(tempNode.val < tempStack.peek().val) { | |
let poppedNode = tempStack.pop(); | |
mainStack.push(poppedNode.val); | |
} else{ | |
break; | |
} | |
} | |
tempStack.push(tempNode.val) | |
} | |
while(tempStack.first !== null) { | |
let currentNode = tempStack.pop(); | |
mainStack.push(currentNode.val) | |
} | |
return mainStack; | |
} | |
let itemStack = new Stack(); | |
itemStack.push(1); | |
itemStack.push(2); | |
itemStack.push(3); | |
let tempStack = new Stack(); | |
let sortedStack = sortStack(itemStack, tempStack); | |
console.log(sortedStack) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment