叠中元素

Question

我在geeksforgeeks网站上读到了关于用javascript和python实现堆栈的文章。我在javascript中实现了删除堆栈中的中间元素的代码，就像在同一个网站中为python提供的代码一样。但我答错了。为什么会这样？这两种语言在这种情况下有什么不同？如何在JavaScript中得到正确答案？下面是JavaScript中的代码。

js prettyprint-override">class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.items.length === 0) {
      return "Underflow";
    } else {
      return this.items.pop();
    }
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length == 0;
  }
  print() {
    console.log(this.items);
  }
}

function deleteMid(stack, curr) {

  // If stack is empty or all items 
  // are traversed 

  if (stack.isEmpty() || curr == stack.items.length) {
    return;
  }
  // Remove last item
  x = stack.peek();
  stack.pop();

  // Remove other items 
  deleteMid(stack, curr + 1);
  console.log("length value: ", stack.items.length);

  // Put all items back except middle 
  if (curr != Math.floor(stack.length / 2)) {
    stack.push(x);
  }
}

var stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.print();
deleteMid(stack, 0);
stack.print();

Answer 1

您的实现遗漏了Python实现的某些部分：

您有一个隐式的全局X变量--与Python不同的是，在Javascript中，没有var/let/const声明的变量被分配给全局对象，因此一旦递归的deletemid完成，您每次都只重新分配了一个名为X的变量（而不是每次迭代都重新分配一个）。改为使用const x，以确保deletemid的每个调用都有自己的x绑定。

您的堆栈没有length属性，因此curr！=math.flola(stack.length/2)测试结果为curr！=nan-这不是您所希望的。尽管可以为堆栈赋予长度getter属性：

  get length() {
    return this.items.length;
  }

这仍然不符合Python实现的要求，它会不断递归地传递初始长度，作为另一个参数：如果您想模仿Python实现，也可以使用n变量：

function deleteMid(stack, n, curr) {
  // ...
  // Remove other items 
  deleteMid(stack, n, curr + 1);
  // Put all items back except middle 
  if (curr != Math.floor(n / 2)) {
  // ...
// Call with:
deleteMid(stack, stack.items.length, 0);

检查length属性的问题是，它会在迭代过程中发生更改，这将使工作变得更加困难。

出于同样的原因，为了使即使大小的堆栈也能工作，我们还需要在这里更改您的JS测试：

if (stack.isEmpty() || curr == stack.items.length) {

if (st.isEmpty() or curr == n) :

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.items.length === 0) {
      return "Underflow";
    } else {
      return this.items.pop();
    }
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length == 0;
  }
  print() {
    console.log(this.items);
  }
  get length() {
    return this.items.length;
  }
}

function deleteMid(stack, n, curr) {

  // If stack is empty or all items 
  // are traversed 

  if (stack.isEmpty() || curr === n) {
    return;
  }
  // Remove last item
  const x = stack.peek();
  stack.pop();

  // Remove other items 
  deleteMid(stack, n, curr + 1);

  // Put all items back except middle 
  if (curr != Math.floor((n) / 2)) {
    stack.push(x);
  }
}

var stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.print();
deleteMid(stack, stack.items.length, 0);
stack.print();