Discussion on: Creating 3 Stacks With 1 Array in JavaScript

[Josep M Sobrepere]

Hi Emma,

First and foremost, thanks a lot for sharing this. It's a cool implementation!

I came up with an alternative implementation, though. Which would allow for any Stack to take as much space as possible. I have not tested it, but I think that the following implementation accomplishes that:

class MultiStack {
  constructor(nStacks, arraySize) {
    this._array = new Array(arraySize);
    this._stacks = new Array(nStacks);
    this._nextUnusedIdx = 0;
    this._availableIdxs = null;
  }

  isFull() {
    return this._nextUnusedIdx === this._array.length && !this._availableIdxs;
  }

  isEmpty(stackIdx) {
    return this._stacks[stackIdx] === undefined;
  }

  _getNextAvailableIdx() {
    if (this._nextUnusedIdx < this._array.length) return this._nextUnusedIdx++;
    if (this._availableIdxs) {
      const {idx} = this._availableIdxs;
      this._availableIdxs = this._availableIdxs.prev;
      return idx;
    }
  }

  push(stackNumber, value) {
    if (this.isFull(stackNumber)) {
      return console.log(`Stack number ${stackNumber} is full`);
    }
    const idx = this._getNextAvailableIdx();
    this._array[idx] = value;
    this._stacks[stackNumber] = {idx, prev: this._stacks[stackNumber]};
  }

  _releaseIdx(idx) {
    this._availableIdxs = {idx, prev: this._availableIdxs};
  }

  pop(stackNumber) {
    if (this.isEmpty(stackNumber)) {
      return console.log(`Stack number ${stackNumber} is empty`);
    }

    const {idx} = this._stacks[stackNumber];
    const result = this._array[idx];
    this._releaseIdx(idx);
    this._stacks[stackNumber] = this._stacks[stackNumber].prev;
    return result;
  }

  peek(stackNumber) {
    if (this.isEmpty(stackNumber)) {
      return console.log(`Stack number ${stackNumber} is empty`);
    }

    const {idx} = this._stacks[stackNumber];
    return this._array[idx];
  }
}

The thing is that normally Stacks are implemented using linked data-structures. So, we could do the same thing here... The idea is to have each Stack to keep a linked list of the indeces that it's using. Then, every time that one of them releases an index, we keep that one in another internal linked-list (_availableIdxs) so that we have a way of knowing which indeces are not used... A "drawback" is that isFull is common for all of them, of course. There is a bit more overhead, but the time-complexity is still constant for all the operations (push, peak and pop) and the memory usage would be a bit better... Another drawback would be the fact that a Stack can take all the available space, leaving nothing for the others :-)

I'm just sharing this, because I thought you could find it interesting. I'm not trying to criticise your work. There is no such thing as a free lunch when it comes to software development, there are prons and cons to both implementations.

[Emma Bostian ✨]

Love this thank you!!

[Harald Lang]

Thanks for sharing your solution.

However, as an interviewer, my follow-up question would be, if you can get rid of the second array, as well as the two member variables.

:)