Javascript: Как вы можете использовать один массив для реализации трех стеков?

Question

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

Как реализовать три стека, используя один массив?

Я знаю, что ответ получен в Java, но я не смог найти ничего в Javascript.

На данный момент, потенциальное решение, которое имеет фиксированный объем пространства для каждого стека, было бы хорошо.,Я знаю, что решение, которое было бы более гибким в распределении пространства, также было бы более сложным.

Спасибо за вашу помощь:)

РЕДАКТИРОВАТЬ: Это мой код

function ThreeInOne() {
  this.stack = []; 
  this.firstStackBeginning;
  this.firstStackEnd;
  this.secondStackBeginning;
  this.secondStackEnd;
  this.thirdStackBeginning;
  this.thirdStackEnd;

  this.addAtStack = function(stackIndex, value) { 
    if (this.stack.length === 0) {
      this.stack.push(value);
      if (stackIndex = 1) {
        this.firstStackBeginning = 0;
        this.firstStackEnd = 0;
      } else if (stackIndex = 2) {
        this.secondStackBeginning = 0;
        this.secondStackEnd = 0;
      } else if (stackIndex = 3) {
        this.thirdStackBeginning = 0;
        this.thirdStackEnd = 0;
      } else if (stackIndex > 3) {
        console.log("There are only 3 stacks available to add to")
      }
    } else if (this.stack.length > 0) {
      if (stackIndex == 1) {
        if (this.secondStackBeginning == 0) {
          this.stack.unshift(value);
          this.secondStackBeginning++;
          this.secondStackEnd++;
          this.firstStackBeginning = 0;
          this.firstStackEnd = 0;
        }
        if (this.secondStackBeginning && this.secondStackBeginning !== 0) {
          this.stack.splice(this.secondStackBeginning-1, 0, value);
          this.firstStackEnd++;
        } 
      } else if (stackIndex == 2) {
        if (this.thirdStackBeginning==0) {
          this.stack.unshift(value);
          this.thirdStackBeginning++;
          this.thirdStackEnd++;
          this.secondStackBeginning = 0;
          this.secondStackEnd = 0;
        } else if (this.thirdStackBeginning != 0) {
          this.stack.splice(this.thirdStackBeginning-1, 0, value);
          this.secondStackEnd = this.thirdStackBeginning-1;
          this.thirdStackBeginning++;
          this.thirdStackEnd++;
        }
      } else if (stackIndex == 3) {
        if (this.firstStackEnd && !this.secondStackEnd && !this.thirdStackBeginning) {
          this.thirdStackBeginning = this.firstStackEnd+1;
          this.stack.push(value);
        } else if (this.seconStackEnd )
      }
    }
  }
}

Это еще не закончено, но идея состояла в том, чтобы сохранить указатели начала и конца каждого стека и соответственно обновить их.Я думаю, что смысл в том, чтобы не использовать другую структуру данных (кроме этого одного массива), иначе я бы просто создал массив с тремя внутренними массивами и обновил их соответствующим образом.Таким образом, идея состоит в том, что, например, если мы начнем с массива = [4, 5, 1, 2, 0, 3, 6], этот массив на самом деле состоит из трех стеков, один = [4, 5), два = [1, 2) и три = [0, 3, 6).Идея состоит в том, что если я захочу добавить x в стек два, то получу массив = [4, 5, 1, 2, x, 0, 3, 6]

Я надеюсь, что этоделает это более ясным!

Answer 1

Эта проблема тривиальна в JS даже с одним массивом, который кажется несколько не в духе вопроса.Причина в том, что массивы JS будут автоматически расширяться для добавления элементов, что значительно упрощает работу с ними по сравнению с массивами ArrayLists или примитивами в Java.

Один подход может включать в себя каждый стек, сопоставленный со смещением в массиве.Например, в конфигурации с тремя стеками первый стек начинается с индекса 0 и использует элементы 0, 3, 6, 9 и так далее.Второй стек начинается с индекса 1 и использует индексы 1, 4, 7, 10 и так далее.Индексирование в массив для операции с верхом использует формулу i + n * (sizes[i] - 1), в то время как нажатие на новую вершину имеет значение i + n * sizes[i], где i - это номер идентификатора стека, а n - это количество стеков, указанное в конструкторе.

class NStack {
  constructor(n) {
    this.stacks = [];
    this.sizes = new Array(n).fill(0);
  }
  
  peek(i) {
    return this.stacks[i+(this.sizes[i]-1)*this.sizes.length];
  }
  
  pop(i) {
    if (this.sizes[i] > 0) {
      return this.stacks.splice(
        i + (--this.sizes[i]) * this.sizes.length, 1, null
      );
    }
  }
  
  push(i, elem) {
    if (this.sizes[i] >= 0) {
      this.stacks[i+(this.sizes[i]++)*this.sizes.length] = elem;
    }
  }
}

const tripleStack = new NStack(3);
tripleStack.push(0, "banana");
console.log(tripleStack);
tripleStack.push(2, "apple");
console.log(tripleStack);
tripleStack.push(1, "watermelon");
console.log(tripleStack);
tripleStack.push(2, "jackfruit");
console.log(tripleStack);
tripleStack.pop(0);
console.log(tripleStack);
tripleStack.pop(2);
console.log(tripleStack);
console.log(tripleStack.peek(0));
console.log(tripleStack.peek(1));
console.log(tripleStack.peek(2));

Answer 2

Это упражнение на самом деле намного проще в JavaScript, чем во многих других языках, потому что массив в JavaScript ведет себя больше как ассоциативный массив с ключами, а не числовыми индексами.Это означает, что разреженный массив занимает только столько места, сколько у него элементов;например, этот массив:

var array = [];
array[0] = "one";
array[999] = "two";

имеет только два элемента и на самом деле не имеет 998 пустых элементов, занимающих место.Это означает, что если вы хотите использовать один массив для создания трех стеков, вы можете просто присвоить им индексы, начиная, например, с 0, 1000 и 2000, а затем каждый стек может содержать тысячу элементов без массива, фактически занимающего пространство 3000 элементов.,

Таким образом, реализация «три стека в массиве» может выглядеть примерно так (и ее можно легко расширить, чтобы иметь переменное количество стеков в одном массиве):

function ThreeStacksInOne(capacity) {
    this.stack = [];
    this.begin = [0, capacity, 2 * capacity, 3 * capacity];
    this.end = [,,];

    this.push = function(stack, value) { 
        if (stack > 2) {
            console.log("Illegal stack index: " + stack + ".");
            return false;
        }
        if (this.end[stack] === undefined) {
            this.end[stack] = this.begin[stack];
        }
        else if (this.end[stack] + 1 == this.begin[stack + 1]) {
            console.log("Stack " + stack + " is full.");
            return false;
        }
        else ++this.end[stack];
        this.stack[this.end[stack]] = value;
        return true;
    }

    this.pop = function(stack) {
        if (stack > 2) {
            console.log("Illegal stack index: " + stack + ".");
            return undefined;
        }
        if (this.end[stack] === undefined) {
            console.log("Stack " + stack + " is empty.");
            return undefined;
        }
        var value = this.stack[this.end[stack]];
        delete this.stack[this.end[stack]];
        if (this.end[stack] == this.begin[stack]) {
            this.end[stack] = undefined;
        }
        else --this.end[stack];
        return value;
    }
}

var stack = new ThreeStacksInOne(1000000000);
stack.push(0,"a");
document.write(stack.pop(0));
var x = stack.pop(0);
stack.push(3,"b");

Вы можете легко адаптировать это к переменному количеству стеков, и вам не нужно решать, сколько стеков вы хотите при создании мультистека;Вы устанавливаете максимальную емкость для стека, а затем можете использовать столько стеков, сколько захотите, если стеки × емкость не больше максимального безопасного целого числа 2 ⁵² -1, что означает, что вы можетеиспользуйте, например, миллион стеков с миллиардом элементов в каждом.И, как объяснено выше, при этом используется только количество места, необходимое для количества элементов, которые фактически присутствуют.

function multiStack(maxSizePerStack) {
    this.stack = [];
    this.size = maxSizePerStack;
    this.end = [];

    this.push = function(stack, value) { 
        if (this.end[stack] === undefined) {
            this.end[stack] = this.size * stack;
        }
        else if (this.end[stack] + 1 == this.size * (stack + 1)) {
            console.log("Stack " + stack + " is full.");
            return false;
        }
        else ++this.end[stack];
        this.stack[this.end[stack]] = value;
        return true;
    }
    this.pop = function(stack) {
        if (this.end[stack] === undefined) {
            console.log("Stack " + stack + " is empty.");
            return undefined;
        }
        var value = this.stack[this.end[stack]];
        delete this.stack[this.end[stack]];
        if (this.end[stack] == this.size * stack) {
            this.end[stack] = undefined;
        }
        else --this.end[stack];
        return value;
    }
}
var stack = new multiStack(1000000000);
stack.push(0,"a");
stack.push(0,"b");
document.write(stack.pop(0) + "<br>");
document.write(stack.pop(0) + "<br>");
document.write(stack.pop(0) + "<br>");
stack.push(1000000,"c");
document.write(stack.pop(1000000) + "<br>");
document.write(stack.pop(9) + "<br>");