JavaScript Sort Stack Coding Challenge

Question

A coding challenge to write a function sortStack that receives a stack of integers into ascending order (with largest integers on top) and returns another stack with sorted integers. At most one additional stack may be used to hold items; no other data structures may be used to copy or hold the elements.

Stack Class:

class Stack { constructor() { this.storage = []; } push(item) { this.storage.push(item); } pop() { return this.storage.pop(); } peek() { return this.storage[this.storage.length-1]; } isEmpty() { return this.storage.length === 0; } printContents() { this.storage.forEach(elem => console.log(elem)); } } 

Stack:

const s = new Stack(); s.push(4); s.push(10); s.push(8); s.push(5); s.push(1); s.push(6); 

My solution:

const sortStack = (stack) => { sorted = new Stack(); while (stack.storage.length) { tmp = stack.pop(); if (tmp >= sorted.peek()) { sorted.push(tmp); } else { while (tmp < sorted.peek()) { stack.push(sorted.pop()); } sorted.push(tmp); } } return sorted; } sortedStack = sortStack(s); sortedStack.printContents(); // correctly outputs 1, 4, 5, 6, 8, 10 

This iterative solution returns the correct output on multiple test cases, and there are no missing edge cases or other logical flaws that I can see, however I don't like the nested while-loop.

I want to keep the solution iterative, so how could I go about not having to use the nested while-loop?

Answer 1

You seem to have some extra code in your function that is not needed. The code below does the same thing as your function:

const sortStack = (stack) => { sorted = new Stack(); while (!stack.isEmpty()) { tmp = stack.pop(); while (tmp < sorted.peek()) { stack.push(sorted.pop()); } sorted.push(tmp); } return sorted; } 

The reason this also works is that whenever tmp < sorted.peek() returns false, tmp >= sorted.peek() would have returned true. So only one comparison is needed.

Answer 2

You have access to the stack array directly so you can copy the unsorted stack it to a new stack and sort it in place using Array.sort

"use strict"; function sortStack(stack) { const sorted = new Stack(); while (!stack.isEmpty()) { sorted.push(stack.pop()) } sorted.storage.sort((a, b) => a - b); return sorted; } 

or

"use strict"; function sortStack(stack) { const sorted = new Stack(); sorted.storage = [...stack.storage].sort((a, b) => a - b); return sorted; } 

If they did not want you to access the storage array directly they would have protected it in closure. (well if that crossed their minds)

BTW your should always add "use strict" to the top of your javascript code as you have neglected to declare any of your variables, making them all global and setting your self up for some horror bugs.

The use strict directive will not let you use undeclared variable.

Answer 3

It can be slightly more performant:

• Keep track of the number of elements you add back to the original stack
• Empty check
• Add first item if not empty (size of one check)

 class Stack { constructor() { this.storage = []; this.counts = { push: 0, pop: 0, peek: 0, isEmpty: 0 } } push(item) { this.counts.push += 1; this.storage.push(item); } pop() { this.counts.pop += 1; return this.storage.pop(); } peek() { this.counts.peek += 1; return this.storage[this.storage.length - 1]; } isEmpty() { this.counts.isEmpty += 1; return this.storage.length === 0; } printContents() { this.storage.forEach(elem => console.log(elem)); } printCounts() { this.counts.total = 0; this.counts.total = Object.values(this.counts).reduce((r, v) => r + v, 0); console.log(this.counts); } } console.log("My implementation"); const stack1 = new Stack(); stack1.push(4); stack1.push(10); stack1.push(8); stack1.push(5); stack1.push(1); stack1.push(6); const sorted1 = sortStack1(stack1); sorted1.printContents(); stack1.printCounts(); sorted1.printCounts(); console.log("Accepted implementation"); const stack2 = new Stack(); stack2.push(4); stack2.push(10); stack2.push(8); stack2.push(5); stack2.push(1); stack2.push(6); const sorted2 = sortStack2(stack2); sorted2.printContents(); stack2.printCounts(); sorted2.printCounts(); function sortStack1(stack) { const sorted = new Stack(); if (stack.isEmpty()) // always return a new instance return sorted; // add first element sorted.push(stack.pop()); while (!stack.isEmpty()) { let removeCount = 0; const temp = stack.pop(); // element to add // move to other stack for (removeCount = 0; temp < sorted.peek(); removeCount += 1) stack.push(sorted.pop()); // push new element sorted.push(temp); // push back to sorted for (let i = 0; i < removeCount; i += 1) sorted.push(stack.pop()); } return sorted; } function sortStack2(stack) { sorted = new Stack(); while (!stack.isEmpty()) { tmp = stack.pop(); while (tmp < sorted.peek()) { stack.push(sorted.pop()); } sorted.push(tmp); } return sorted; }

.as-console-wrapper { top: 0 !important; max-height: 100vh !important; }

My function is labeled sortStack1.

Note: These performance enhancements probably don't matter that much.