2

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.

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]

I hope this makes it more clear!

Improve this question
8
  • 1
    Please show us some of what you've tried, and some suggestion of the public interface you're trying to create. Commented Sep 18, 2018 at 19:00
  • 3
    the question is not really "self evident". What exactly is it that you're trying to achieve? What woul be an example of a "three stack array"? What do you want to be able to do with it? Commented Sep 18, 2018 at 19:00
  • 3
    Javascript is a very dynamic language, so you can simply use: let stacks = [[ ], [ ], [ ]] and get three stacks in a single array. Maybe not in the spirit of the question, but evidence that the question is not at all "self evident". Commented Sep 18, 2018 at 19:01
  • 1
    If you have a solution in Java, what difficulty are you having translating that into Javascript? Commented Sep 18, 2018 at 19:17
  • 1
    Arrays in Javascript are actually associative arrays rather that arrays with a numerical index. This means that if your first stack goes up to stack[9] and your second stack starts at stack[10], you could add an element stack[9.5] if you wanted to. Or you could use indexes like stack['a1'], stack['b0'] and stack['c5']. Commented Sep 18, 2018 at 19:59

2 Answers 2

Reset to default
3

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: 

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.

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 252-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. 

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

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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.

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.

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

Improve this answer

1 Comment

That's actually very clever. Thank you.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.