使用javascript对堆栈元素进行排序

Question

我试图理解使用中给出的递归对堆栈元素进行排序http://www.geeksforgeeks.org/sort-a-stack-using-recursion/不允许使用while、for…等任何循环结构。我们只能在堆栈S上使用以下ADT函数：

is_empty（S）：测试堆栈是否为空。

push（S） ：向堆栈添加新元素。

Pop（S）：从堆栈中删除顶部元素。

top（S） ：返回 top 元素的值。请注意，此函数不会从堆栈中删除元素。我在下面尝试过，但出现错误

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

Answer 1

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

function compare(a,b) {

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

stack.sort(compare);

console.log(stack);

Answer 2

如果您只想对数组进行排序，可以使用sort（）方法。检查以下示例：

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

如果你想了解如何手动排序数组，看看这个ans（注意：下面的代码是从同一个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));

Answer 3

对于javascript，局部(作用域)变量需要声明为var，否则它们就是静态的。如果sortStack()中t之前没有var，t将是一个静态变量，每次弹出时都会被覆盖，因此sortStack()的所有返回都是t == -3。sortedInsert()中的x也会出现同样的问题。

js lang-js prettyprint-override">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);