Javascript：如何使用单个数组实现三个堆栈？

so I've tried my way, which has not worked and seemed to have way too many control statements, which got somewhat confusing. The question is pretty self evident.

所以我试过了自己的方式,这种做法没有用,似乎有太多的控制语句,这有点令人困惑。这个问题非常明显。

How do you implement three stacks using a single array?

如何使用单个阵列实现三个堆栈?

I know the answer has been answered in Java, but I couldn't find anything in Javascript.

我知道答案已在Java中得到解答,但我在Javascript中找不到任何内容。

For now, a potential solution that has fixed amount of space for each stack would be fine. I know that a solution that would be more flexible in space allocation would also be more complex.

目前,每个堆栈具有固定空间量的潜在解决方案都可以。我知道在空间分配方面更灵活的解决方案也会更复杂。

Thank you for your help :)

感谢您的帮助 :)

EDIT: This is my code

编辑:这是我的代码

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 )
      }
    }
  }
}

It's not finished, but the idea was to keep pointers of the beginning and end of each stack and update them accordingly. I think the point is to not use another data structure (other than that one array) or else I would just create an array with three internal arrays and update them accordingly. So the idea is that for example if we start with array = [4, 5, 1, 2, 0, 3, 6], this array is actually composed of three stacks, one = [ 4, 5 ), two = [ 1, 2), and three = [0, 3, 6). The idea is that if I want to add x to stack two, then I'll end up with the array = [4, 5, 1, 2, x, 0, 3, 6]

它没有完成,但想法是保持每个堆栈的开头和结尾的指针并相应地更新它们。我认为重点是不使用其他数据结构(除了那个数组),否则我只会创建一个包含三个内部数组的数组并相应地更新它们。所以我的想法是,例如,如果我们从array = [4,5,1,2,0,3,6]开始,这个数组实际上由三个堆栈组成,一个= [4,5],两个= [1 ,2),和3 = [0,3,6)。我的想法是,如果我想将x添加到堆栈2,那么我最终会得到数组= [4,5,1,2,x,0,3,6]

I hope this makes it more clear!

我希望这更清楚!

2 个解决方案

#1

This exercise is actually much easier in JavaScript than in many other languages, because an array in JavaScript behaves more like an associative array with keys instead of numerical indexes. This means that a sparse array only takes up as much space as it has elements; e.g. this array:

这个练习在JavaScript中实际上比在许多其他语言中容易得多,因为JavaScript中的数组更像是一个带键而不是数字索引的关联数组。这意味着稀疏数组只占用与元素一样多的空间;例如这个数组:

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

only has two elements, and doesn't actually have 998 empty elements taking up space. This means that if you want to use one array to create three stacks, you can simply give them indexes starting at e.g. 0, 1000 and 2000, and then each stack can hold a thousand elements without the array actually taking up the space of 3000 elements.

只有两个元素,并没有实际占用空间的998个空元素。这意味着如果你想使用一个数组来创建三个堆栈,你可以简单地给它们开始索引,例如从0,1000和2000,然后每个堆栈可以容纳一千个元素,而阵列实际上不占用3000个元素的空间。

So a three-stacks-in-an-array implementation could be something like this (and it could easily be extended to have a variable number of stacks in one array):

因此,三个堆栈的数组实现可能是这样的(并且可以很容易地扩展到在一个数组中具有可变数量的堆栈):

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

You can easily adapt this for a variable number of stacks, and you don't have to decide how many stacks you want when you create the multi-stack; you set the maximum capacity per stack, and then you can use as many stacks as you like, as long as stacks × capacity isn't greater than the maximum safe integer 2⁵²-1, which means you can use e.g. a million stacks with a billion elements each. And, as explained above, this uses only the amount of space needed for the number of elements that are actually present.

您可以轻松地将其调整为可变数量的堆栈,并且您不必在创建多堆栈时决定所需的堆栈数量;你设置每个堆栈的最大容量,然后你可以使用任意数量的堆栈,只要堆栈×容量不大于最大安全整数252-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>");

#2

This problem is trivial in JS even with one array such that it seems somewhat out of the spirit of the question. The reason is because JS arrays will automatically expand to add elements making them much easier to work with than ArrayLists or primitive arrays in Java.

这个问题在JS中是微不足道的,即使有一个数组,这似乎有点超出了问题的精神。原因是因为JS数组会自动扩展以添加元素,这使得它们比Java中的ArrayLists或原始数组更容易使用。

One approach could involve each stack mapped to an offset in the array. For example, in a three stack configuration, the first stack begins at index 0 and uses elements 0, 3, 6, 9 and so on. The second stack begins at index 1 and uses indices 1, 4, 7, 10 and so on. Indexing into the array for a top operation uses the formula i + n * (sizes[i] - 1), while pushing a new top is i + n * sizes[i] where i is the stack ID number and n is the number of stacks specified in the constructor.

一种方法可能涉及映射到阵列中的偏移的每个堆栈。例如,在三堆栈配置中,第一个堆栈从索引0开始,并使用元素0,3,6,9等。第二个堆栈从索引1开始,使用索引1,4,7,10等。索引到顶部操作的数组使用公式i + n *(sizes [i] - 1),而推新的顶部是i + n * sizes [i]其中i是堆栈ID号,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));