Средний элемент в стеке

Question

Я прочитал статью о реализации стека в javascript и python на сайте geeksforgeeks.Я реализовал код для удаления среднего элемента в стеке в javascript точно так же, как указано для python на том же сайте.Но я получаю неправильный ответ.Почему это так?В чем разница между двумя языками в этом случае?Как я могу получить правильный ответ в JavaScript?Ниже приведен код в Javascript.

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 / *Глобальному объекту присвоено 1006 *, поэтому после завершения рекурсивных deleteMid будет только одна переменная с именем x (а не одна для каждой итерации), которую вы каждый раз переопределяете.Вместо этого используйте const x, чтобы гарантировать, что каждый вызов deleteMid имеет собственную привязку x.

В вашем стеке нет свойства length, поэтому результаты теста curr != Math.floor(stack.length/2) в curr != NaN - это не то, что вы хотите.Хотя вы можете присвоить свойству stack a length 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) {

для соответствия коду Python:

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();

Answer 2

Поскольку вы знаете средний индекс при запуске, вы можете проверять длину стека после удаления каждого элемента и останавливаться при попадании в середину.

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, middle = Math.round(stack.items.length / 2)) {
  if (stack.isEmpty()) return;
  
  const isMiddle = stack.items.length === middle;
  
  // Remove last item
  const x = stack.pop();

  // stop when you get to the middle
  if (isMiddle) return;
  
  // Remove other items
  deleteMid(stack, middle);
  
  // add the item back
  stack.push(x);
}

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