sorting elements of stack using javascript

Question

I m trying to understand sorting a stack elements using recursion given in http://www.geeksforgeeks.org/sort-a-stack-using-recursion/ Use of any loop constructs like while, for..etc is not allowed. We can only use the following ADT functions on Stack S:

is_empty(S) : Tests whether stack is empty or not.

push(S) : Adds new element to the stack.

pop(S) : Removes top element from the stack.

top(S) : Returns value of the top element. Note that this function does not remove element from the stack. I tried below but getting error

var stack = [-3, 14, 18, -5, 30];

function sortStack() {
  if (stack.length > 0) {
    temp = stack.pop();
    sortStack();
    sortedInsert(temp, stack);
  }
}

function sortedInsert(element, stack) {
  if (stack.length > 0 || element > stack[stack.length - 1]) {
    stack.push(element);
  } else {
    temp = stack.pop();
    sortedInsert(element, stack);
    stack.push(temp);
  }

}

sortStack();

console.log(stack);

RangeError: Maximum call stack size exceeded
at sortedInsert:12:22
at sortedInsert:21:5
at sortedInsert:21:5
at sortedInsert:21:5
at sortedInsert:21:5
at sortedInsert:21:5

http://www.geeksforgeeks.org/sort-a-stack-using-recursion/ I m trying to implement this algorithm in javascript — kiran reddy, Dec 22 '16 at 13:07
you need to use `var` to get your temp variable local instead if global. Also you have confused stack is empty with stack has elements in `sortedInsert`. — Sylwester, Dec 22 '16 at 14:41

rcgldr · Accepted Answer · 2016-12-23T02:26:24.360

With javascript, local (scoped) variables need to be declared as var, otherwise they are static. Without the var before t in sortStack(), t would be a static and just get overwritten with each pop, leaving t == -3 on all the returns from sortStack(). The same issue occurs with x in sortedInsert().

var stack = [-3, 14, 18, -5, 30];

function sortStack(s) {
  if (s.length > 0) {
    var t = s.pop();
    sortStack(s);
    sortedInsert(s, t);
  }
}

function sortedInsert(s, e) {
  if (s.length == 0 || e > s[s.length - 1]) {
    s.push(e);
  } else {
    var x = s.pop();
    sortedInsert(s, e);
    s.push(x);
  }
}

sortStack(stack);

console.log(stack);

score 0 · Answer 2 · edited Dec 22 '16 at 13:44

0

var stack = [-3, 14, 18, -5, 30];

function compare(a,b) {

    return parseInt(a, 10) - parseInt(b, 10);
    }

stack.sort(compare);

console.log(stack);

edited Dec 22 '16 at 13:44

Ponnarasu

635
1
11
24

answered Dec 22 '16 at 13:04

pankaj chauhan

1

http://www.geeksforgeeks.org/sort-a-stack-using-recursion/ I m trying to implement this algorithm in javascript – kiran reddy Dec 22 '16 at 13:07
var stack = [-3, 14, 18, -5, 30]; function bubbleSort(items) { var length = items.length; for (var i = (length - 1); i >= 0; i--) { //Number of passes for (var j = (length - i); j > 0; j--) { //Compare the adjacent positions if (parseInt(items[j]) < parseInt(items[j - 1])) { //Swap the numbers var tmp = items[j]; items[j] = items[j - 1]; items[j - 1] = tmp; } } } } bubbleSort(stack); //stack.sort(compare); console.log(stack); – pankaj chauhan Dec 22 '16 at 13:13
Use of any loop constructs like while, for..etc is not allowed. We can only use the following ADT functions on Stack S: is_empty(S) : Tests whether stack is empty or not. push(S) : Adds new element to the stack. pop(S) : Removes top element from the stack. top(S) : Returns value of the top element. Note that this function does not remove element from the stack. – kiran reddy Dec 22 '16 at 13:18
this is restriction given in the problem description of geeks4geeks – kiran reddy Dec 22 '16 at 13:18

score 0 · Answer 3 · edited May 23 '17 at 11:45

If you just want to sort the array, you can use sort() method. Check example below:

var stack = [-3, 14, 18, -5, 30];
console.log(stack.sort());

If you want to understand how to sort array manually, have a look at this ans (Note: below code is copied from same ans):

var stack = [-3, 14, 18, -5, 30];

function arrSort(arr, subkey) {
  //Default to 0 if no subkey is set
  subkey = (subkey === undefined ? 0 : subkey);

  var a = arr.slice(0),
      b = [], x;

  // For each section in the array, create an array containing whatever we are trying to sort by and our unique ID
  for (x in a) {
    b[x] = [a[x][subkey], x];
  }

  b = b.sort();

  //Wipe out all the data that's currently in arr!
  arr.splice(0, arr.length);

  for (x in b) {
    arr.push(a[b[x][1]]);
  }

  return arr;
}

// console.log(arrSort(stack, 0));
console.log(arrSort(stack));

thanks , but I m trying to understand this algorithms related to stack http://www.geeksforgeeks.org/sort-a-stack-using-recursion/ I m trying to implement this algorithm in javascript, cant we implement this in js — kiran reddy, Dec 22 '16 at 13:08
we can definitely implement this JS, will check the link and try to explain in my ans. — Yogesh, Dec 22 '16 at 13:13

score 0 · Answer 4 · answered Jun 10 '20 at 15:11

/*
Create a temporary stack say tmpStack.
    While input stack is NOT empty do this:
            Pop an element from input stack call it temp
            while temporary stack is NOT empty and top of temporary stack is greater than temp,
                     pop from temporary stack and push it to the input stack
            push temp in temporary stack
The sorted numbers are in tmpStack
*/

class sortStack{
  constructor(){
      this.tempStack = [];
  }

  sortStack(inputStack){
         if(inputStack.length==0){
             return "empty "
         }
         while(inputStack.length > 0){

            let item = inputStack.pop()
            while(this.tempStack.length > 0 && item < this.tempStack[this.tempStack.length -1]){
                inputStack.push(this.tempStack.pop())
            }
            this.tempStack.push(item)
         }

         return this.tempStack;
  }

}


let a = [34, 3, 31, 98, 92, 23];
let s = new sortStack();
console.log(s.sortStack(a))

sorting elements of stack using javascript

4 Answers4

Linked