DEV Community

Emma Bostian ✨
Emma Bostian ✨

Posted on

Creating 3 Stacks With 1 Array in JavaScript

stack

This problem was a prompt from the Cracking The Coding Interview book. The exercise is: "Describe how you could use a single array to implement three stacks."

What Is A Stack?

A stack is a data structure that is based on the concept of “last-in-first-out” or “LIFO.” You can think of it like a stack of books where the top book has to be taken off the stack before you can retrieve the bottom book. JavaScript doesn’t have a native stack data structure, so we’re going to create one today.

Our array will contain three different stacks of a fixed size. The top of the stack will be on the right side and the bottom of the stack will be on the left side. You can picture it similar to this diagram. If this stack was full, the bottom element would live at stack[0] and the top element would live at stack[stack.length-1].

stack

Class Breakdown

Our stacks will have a fixed size which will be equal to the argument passed in at instantiation.

Properties

The following properties will be initialized within the constructor:

  • _stackCapacity: The maximum number of elements that can fit into one stack. This is a read-only property which is why it’s prepended with an underscore.
  • values: An array which contains of all elements in the three stacks
  • sizes: An array with three indices, each representing the current number of elements in the respective stacks.
  • numberOfStacks: A constant which represents the total number of stacks we’ll allow our array to hold. We’re initializing this to three, however future iterations of this MultiStack class could take in a second argument to customize the number of stacks the array can hold.

Methods

Our MultiStack class will contain the following methods:

  • get stackCapacity(): Returns the total capacity of each of the stacks (this is just a way for me to check that everything is working as expected, we won’t really be using this.)
  • push(stackNumber, value): Pushes the value onto the top of the respective stack number.
  • pop(stackNumber): Pops the top item off of the respective stack number.
  • peek(stackNumber): Returns the top item off of the respective stack number. It’s just a way for us to “peek” at what element is on the top; no stack mutation will happen.
  • isEmpty(stackNumber): Returns a boolean which indicates whether the respective stack has values.
  • isFull(stackNumber): Returns a boolean which indicates whether the respective stack is full.
  • indexOfTop(stackNumber): A helper method which returns the index, in the values array, of the top element in the respective stack.

Constructor

The first thing we’ll do is create our constructor. It will take in one argument, the stack size. Thus, the total length of our values array will be 3 * the stack size (since we’re initializing numberOfStacks to three).

We will initialize the sizes array to contain three indices with the value zero. For our purposes we will assume that the values being pushed onto the stacks are positive integers. You can change this logic to fit your needs.

Get Stack Capacity

This method returns the total capacity of each of the stacks (this is just a way for me to check that everything is working as expected, we won’t really be using this.)

You can read more about JavaScript getters on MDN.

isFull

This method returns a boolean which indicates whether the respective stack is full. It will check how many elements are currently on the respective stack and compare it against the stack capacity.

isEmpty

This method returns a boolean which indicates whether the respective stack has values.

indexOfTop

This is a helper method which returns the index, in the values array, of the top element in the respective stack.

This explanation could get a little tricky, so stick with it! I’ve included diagrams to better visualize the process.

First we need to grab the offset of the stack within the values array. To do this, we’ll multiply the stack number we want by the capacity of each stack.

For example, let’s find the index of the top item in stack 2 given that the _stackCapacity for each stack is 5. The stacks contain the following elements:

  • Stack 0: [1, 12]
  • Stack 1: [18, 8, 2]
  • Stack 2: [5, 9, 66, 15]

Here is a visual representation of what the values array looks like:

stack
stack

Step 1: Calculate the offset; find the index of the bottom item in stack two

Assuming our stacks start at zero (i.e. stack 0, stack 1, stack 2), we can find where the bottom of stack two starts in the values array by multiplying the stack we’re looking for, two, by the stack capacity, which is the value passed in at instantiation. If our stack capacity is five, we know that the bottom element of stack two starts at index 10 in the values array.

index of bottom element in stack 2 = stack we’re looking for * capacity of each stack.

index of bottom element in stack 2 = 2 * 5 (found from _stackCapacity)

index of bottom element in stack 2 = 10

stack

Step 2: Calculate the total number of values currently in stack two

We already know how many values are in stack 2; they’re being kept in the sizes array. So by grabbing the value of sizes[2] we know how many elements are in stack 2: 4

Step 3: Add the offset with the total number of values in the stack, minus one

We have to subtract one from the number of items in the stack, since our array starts at index zero.

When we add it all up we get:

index of top element in stack 2 = offset + number of values in stack two — 1

index of top element in stack 2 = 10 + 4 — 1

index of top element in stack 2 = 13

stack

The code for this is as follows:

Push

The push method pushes a value onto the top of the respective stack. It takes in two arguments:

  • The stack to push the value onto
  • The value
  1. The first thing we have to do is check whether the stack is full. If it is full, let’s console.log the message Stack number ${stackNumber} is full.
  2. If the stack isn’t full, increase the number of items in the stack, which is found in the sizes array.
  3. Then add the new value to the top of the stack. We’ll use the indexOfTop method we just explained above to grab the top of the stack and add a value on top of it.
  4. If it’s successfully added, let’s console.log a friendly message.

Pop

This method pops the top item off of the respective stack number. It takes in one argument:

  • The stack to pop the value off of
  1. We must first check if the stack is empty using the isEmpty method. If it is, we’ll return a console.log a message.
  2. If the stack isn’t empty, we’ll grab the index of the top element on the stack using the indexOfTop method and save it to a variable called topIndex.
  3. Now let’s grab the value of that element. We can do this with this.values[topIndex] . We’ll return this element, which is why we need to save it to a variable.
  4. We also need to tell the values array that the value at this index no longer exists. We’ll set this explicitly to zero (this could pose issues if your stack can take zero as a value, but for our sake we’ll assume the stack only accepts positive integers).
  5. We must also decrement the size of the stack in the sizes array. We can do this with this.sizes[stackNumber]--.
  6. Finally, let’s return the value we just popped off.

Peek

This method returns the top item off of the respective stack number. It doesn’t alter the stack, it simply lets you view the element on the top. It takes in one argument:

  • The stack whose top value we want to peek at
  1. We first have to check if the stack is empty. We can use the isEmpty method to do so. If it is empty, let’s console.log a friendly message.
  2. If the stack isn’t empty, we need to find the index for the element on top of the stack. We can use the indexOfTop method to do so.
  3. Finally, we can return the value found at that index with this.values[topIndex].

Putting It All Together

The final class looks like this:


You’ve now created an array that represents three fixed-size stacks! You can view the CodePen for this class here.

Top comments (26)

Collapse
 
josepot profile image
Josep M Sobrepere • Edited

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.

Collapse
 
emmabostian profile image
Emma Bostian ✨

Love this thank you!!

Collapse
 
haraldlang profile image
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.

:)

Collapse
 
geompse profile image
Geompse

For storing three stacks using one array, you are using an object containing two arrays.
To me a nicer answer would have been to use one array only, maybe using the array as the object itself :
multipleStacksArray.constructor === Array;
multipleStacksArray.pushToStack(stackNumber,value);

Anyways using indexed accesses to the array does not seem to comply to the demand, aka if you replace [] with {} in your class it will still work while not using arrays... Can you do it over using Javascript's native methods Array.push and Array.pop ? I would like to see such a clever implementation.

Collapse
 
rudavko profile image
Andrii

Yeah, I was a bit disappointed that the total number of arrays was two as well :) I’m on board with “one array” means one array..
It could be achieved by reserving the first n items of the single array to contain the sizes.

Not sure how I feel about using indexed access not complying with the demand. I mean it is an array, so I’m not really getting your point.
Would be thankful if you could elaborate further on your second point.

Collapse
 
geompse profile image
Geompse

Well, to me, using indexes is cheating because it is the same as using objects. Since you can access the [topIndex] value you access the [topIndex-1] value : that is in opposition with the concept of stacks (LIFO).

You might as well have objects with named properties (i.e. multipleStacks.stack1.value1) and no array at all.

For the sole purpose of science I would have enjoyed an "only one stack" version where you have to unstack in a temporary stack untill reaching the desired value to access or update (loop of Array.pop then loop of Array.push).

For the sake of fulfilling the use case, for production usage, I would have made one object containing an array per stack (but a multimensional array is cheating as well) and not one object containing two objects.

TL;DR it seems very bad not to use Array.pop nor Array.push in a JavaScript exercice regarding stacks.

Thread Thread
 
haraldlang profile image
Harald Lang

Well, I do not understand that complain.

The task was to implement a stack using an array, rather than to implement a stack using a stack.

So from my understanding, using indexed access is perfectly fine.

Collapse
 
juliang profile image
Julian Garamendy

Besides the interview question, why would I want to implement 3 stacks with 1 array?
Honest question.

Collapse
 
haraldlang profile image
Harald Lang

That is indeed the better question :D

Collapse
 
emmabostian profile image
Emma Bostian ✨

LOL I have no freaking clue. I definitely wouldn't want to IRL. Was just an exercise.

Collapse
 
agredalex profile image
Alex Ágreda • Edited

Excellent article!

Just one question:
In push method, shouldn't be

this.values[this.indexOfTop(stackNumber) + 1] = value;

instead of

this.values[this.indexOfTop(stackNumber)] = value;

?

Collapse
 
dallas profile image
Dallas Reedy

This was a really fun article to play along with, Emma! Thanks for structuring it the way you did. Being a somewhat seasoned developer, I appreciated the flying overview at the beginning so that I could write up my own version of such a class with all the proper attributes and methods in place. I even took my own first stab at filling in those methods and guessing ahead at how you might fulfill each one’s responsibility. I came really close on a lot of it!

I also really appreciate how you break it down into really simple terms – with visuals! – so that beginners and those of us who appreciate the “why?” behind the “how?” could get a firm grasp on the concepts.

Thank you! 🙏🏼

Collapse
 
konrud profile image
Konstantin Rouda

Doesn't this code override the last element in the stack instead of adding it, as this.indexOfTop returns the index of the last element?

  this.values[this.indexOfTop(stackNumber)] = value;
Collapse
 
dallas profile image
Dallas Reedy • Edited

I’m thinking the same thing… if indexOfTop points at the top-most element, then setting that same index to the new value just keeps overwriting that top-most element, no?


Edit: I actually tried it the way I thought it should be (adding 1 to the value of indexOfTop) and it definitely does not do the right thing (the first element of every stack is empty, so everything is off by 1). And when I removed that code, it worked perfectly.

So, now my only question is: How is it working!? How can indexOfTop be used to both show the top-most element and to insert a new element?

Collapse
 
dallas profile image
Dallas Reedy • Edited

Oh. I see it now 🤦🏻‍♂️!

It works because of the line immediately preceding that line:

this.sizes[stackNumber]++;

That seems tricky – difficult to come back to later on and immediately understand how those lines work in concert. Perhaps it would be more straight-forward to swap those two lines and add 1 to the indexOfTop instead:

// insert our new value to the top of the stack
this.values[this.indexOfTop(stackNumber) + 1] = value;
// increment our stack size by 1
this.sizes[stackNumber]++;
Thread Thread
 
emmabostian profile image
Emma Bostian ✨

It is a bit convoluted eh?

Thread Thread
 
dallas profile image
Dallas Reedy

Yeah, maybe a little. Not too bad. Once I actually ran the code, I began to understand the cleverness at work.

Collapse
 
voliva profile image
Víctor Oliva

Hey Emma, that's a nice solution, but wouldn't something like this work as well?

Stack 1 indices: N*3
Stack 2 indices: N*3 + 1
Stack 3 indices: N*3 + 2

So basically you split the array where position 0 is stack 1, 1 is stack 2, 2 is stack 3, 3 is stack 1 again, 4 is stack 2, etc.

This would allow your stacks to have an indefinite max length as well (as you'll never run in a case where a stack needs to take space from another one)

Collapse
 
snowfrogdev profile image
Philippe Vaillancourt • Edited

I was thinking the same thing but then you would end up with a sparse array. I guess it's not that big a deal in JS.

Collapse
 
haraldlang profile image
Harald Lang

Hi Emma,

thanks for your post (and code) on that coding interview question.

In my opinion, the applicant not only needs to know what a stack is, and how it's implemented, but also needs to be able to "flatten" a data structure into a (one-dimensional) range of memory, in that case a simple fixed-size array.

Thus, I modified your code a bit, to get rid of the second array and the member variable _stackCapacity.
For simplicity, I also removed the support for arbitrary numbers of stacks, as its not requested by the interviewer' question.

class ThreeStacks {

  constructor(array) {
    this._data = array; // Store a reference to the (external) data array.
  }

  get capacity() {
    return ((this._data.length - 3) / 3) | 0;
  }

  size(stackNumber) {
    return this._data[stackNumber];
  }

  isEmpty(stackNumber) {
    return this.size(stackNumber) === 0;
  }

  isFull(stackNumber) {
    return this.size(stackNumber) === this.capacity;
  }

  indexOfTop(stackNumber) {
    return 3 + (this.capacity * stackNumber) + this.size(stackNumber) - 1;
  }

  push(stackNumber, value) {
    if (this.size(stackNumber) === this.capacity) {
      console.log(`Stack number ${stackNumber} is full`);
      return false
    }
    // Add the value to the list
    this._data[3 + (this.capacity * stackNumber) + this.size(stackNumber)] = value;
    // Add one to the respective stack count
    this._data[stackNumber]++;
    console.log(`Item ${value} has been successfully added to stack ${stackNumber}`);
    return true;
  }

  pop(stackNumber) {
    if (this.isEmpty(stackNumber)) {
      console.log('Stack number ${stackNumber} is empty');
      throw new Error('Cannot pop an empty stack.');
    }
    const topIndex = this.indexOfTop(stackNumber);
    const value = this._data[topIndex];
    this._data[topIndex] = 0; // Clear out element.
    this._data[stackNumber]--; // Reduce num elements in the stack
    return value;
  }

  peek(stackNumber) {
    if (this.isEmpty(stackNumber)) {
      console.log('Stack number ${stackNumber} is empty');
      throw new Error('Cannot peek an empty stack.');
    }
    const topIndex = this.indexOfTop(stackNumber);
    return this._data[topIndex];
  }

}
// Usage:
let array = new Array(10).fill(0);
console.log("raw data: ", array);

const stack = new ThreeStacks(array);
console.log("capacity: ", stack.capacity);
console.log("size(0): ", stack.size(0));
console.log("");

console.log("stack.push(0, 13)");
stack.push(0, 13);
console.log("size(0): ", stack.size(0));
console.log("peek(0): ", stack.peek(0));
console.log("");

console.log("stack.push(0, 37)");
stack.push(0, 37);
console.log("size(0): ", stack.size(0));
console.log("peek(0): ", stack.peek(0));
console.log("");

console.log("stack.pop(0)");
stack.pop(0);
console.log("size(0): ", stack.size(0));
console.log("peek(0): ", stack.peek(0));
console.log("");

console.log("stack.pop(0)");
stack.pop(0);
console.log("size(0): ", stack.size(0));
console.log("");

let v = 0;

for (s = 0; s < 3; s++) {
  while (!stack.isFull(s)) {
    stack.push(s, v);
    v++;
  }
  v += 10;
}
console.log("raw data: ", array);

Collapse
 
jimbotsov profile image
JimboTSoV • Edited

Edit:
I just realized that you actually did that already, my bad!


I found this interesting, but in your leading paragraph you could probably add why you would use this. Is this simply meant to teach about stacks in general or do you have an example use case for Javascript at hand?

Collapse
 
emmabostian profile image
Emma Bostian ✨

Sure! This was a prompt from the Cracking The Coding Interview book. The exercise is: "Describe how you could use a single array to implement three stacks.":)

Collapse
 
patriklarsson profile image
Patrik • Edited

This is a great example and breakdown and nice solution.

It did spawn some thinking though whether it's not feasible to take a more function-oriented approach (with some traditional OOP interspersed) to really hone in on the "a single array" part of the question. By extracting separate objects for the different queues, we can hold positions inside those objects instead, shifting the responsibility completely.

I thought of something like this:

let Arrack = (stacks, maxStackSize, freeStackSlotsWhenDigested=false) => {
    let stackSize = maxStackSize * stacks,
        masterStack = Array(stackSize);

    let QueueHandler = (stack) => {
        if (stack >= stacks) {
            throw "Not enough stacks in this Arrack"
        }

        let stackStart = (stack) * maxStackSize,
            stackPosition = stackStart,
            stackEnd = stackStart + maxStackSize,
            queue = (ob) => {
                if (stackPosition === stackEnd) {
                    throw "Max stack size reached"
                }

                masterStack[stackPosition] = ob;
                stackPosition++;
            },
            digest = () => {
                if (stackPosition === stackStart) {
                    throw "No items to digest"
                }

                stackPosition--;
                let item = masterStack[stackPosition];
                if (freeStackSlotsWhenDigested) {
                    masterStack[stackPosition] = null;
                }
                return item;
            };

        return {
            queue: queue,
            digest: digest
        }

    };

    return {
        initiateStack: QueueHandler
    };
};

We can then initiate an object that holds the values inside it, as well as a handler for each available stack.

The last argument is whether we want to clear the slots once used, or we simply leave out to keep them in-memory (to avoid an additional operation).

let arrack = Arrack(3, 10, true);

Once we have our Arrack we can handle each queue separately.

let stack0 = arrack.initiateStack(0),
    stack1 = arrack.initiateStack(1),
    stack2 = arrack.initiateStack(2);

We then use the queue(ob) and digest() methods to put and get items from our queue.

stack1.queue({
    message: 'foo',
    type: 'bar'
});
stack1.digest();
> {message: "foo", type: "bar"}

I lazily threw errors if we try to digest what we don't have, or put more objects than we're allowed (Python habit I'm afraid), but that could be tweaked.

for (let i=0; i<11; i++) {
    stack2.queue(i);
}
>! Uncaught Max stack size reached

Feedback is very welcome :)

Collapse
 
cagataysert profile image
Çağatay Sert

Hey Emma,

it was a great article. Thank you for sharing your knowledge. I will try to make this kind of example to improve my JS skills :)

Collapse
 
lambshift profile image
Juan Pablo de la Torre

What about using the structure file headers have? Files usually store the size of a field as the first bytes in them. This way, one could implement a dynamic array of dynamic stacks within a single array.

Collapse
 
lambshift profile image
Juan Pablo de la Torre

I wrote this. It uses a single array which is the class in itself. Not really needed but really fun.

class Stacks extends Array {

  /**
   * @param [count=0] Number of stacks to initialize the Array
   */
  constructor (count) {
    super(count || 0).fill(0);
    this.count = count || 0;
  }

  /**
   * Gets index after a stack ends. 
   * @param position Stack position
   */
  next (position) {
    return position < this.count ?
      position < 0 ?
        0 :
        Array(position + 1).fill(0).reduce(sum => sum += this[sum] + 1, 0) :
      this.length;
  }

  /**
   * Gets index where a stack starts (stack size is stored here).
   * @param position Stack position
   */
  first (position) {
    return position ? this.next(position - 1) : 0;
  }

  /**
   * Gets the size of stack at position.
   * @param position Stack position
   */
  size (position) {
    return this[this.first(position)];
  }

  /**
   * Peeks the last item of stack at position.
   * @param position Stack position
   */
  peek (position) {
    return this[this.next(position) - 1];
  }

  /**
   * Pushes items to a stack.
   * @param position Stack position
   * @param items The rest of the arguments would be pushed to the stack
   */
  push (position, ...items) {
    if (position < this.count) {
      this.splice(this.next(position), 0, ...items);
      this[this.first(position)] += items.length;
    }
  }

  /**
   * Pops the last item of a stack.
   * @param position Stack position
   */
  pop (position) {
    if (position < this.count) {
      this[this.first(position)]--;
      return this.splice(this.next(position) - 1, 1)[0];
    } else {
      return null;
    }
  }

  /**
   * Adds a new stack at position.
   * @param position Position to place the new stack
   * @param items Items of the stack.
   */
  add (position, items) {
    items.unshift(items.length);
    this.splice(this.next(position - 1), 0, ...items);
    this.count++;
  }

  /**
   * Removes stack at position.
   * @param position Stack position
   */
  remove (position) {
    if (position < this.count && position >= 0) {
      const first = this.first(position);
      this.splice(first, this[first] + 1);
    }
  }

}

Here is an example:

const memory = new Stacks(0); [ ]
memory.add(0, [1, 2, 3]);
  // result > [ 3, 1, 2 ,3 ]
  // 1 stack, 3 items
memory.add(0, [10, 11]);
  // result > [ 2, 10, 11, 3, 1, 2, 3 ]
  // 2 stacks of 2 and 3 items
memory.push(1, 4, 5);
  // result > [ 2, 10, 11, 5, 1, 2, 3, 4, 5 ]
  // 2 stacks of 2 and 5 items
memory.pop(0); // returns 11
  // result > [ 1, 10, 5, 1, 2, 3, 4, 5 ]
  // 2 stacks of 1 and 5 items
memory.pop(1); // returns 5
  // result > [ 1, 10, 4, 1, 2, 3, 4 ]
  // 2 stacks of 1 and 4 items
memory.remove(0);
  // result > [ 4, 1, 2, 3, 4 ]
  // 1 stack of 4 items

And a test using console.assert.

const test = new Stacks(3);
console.assert(test.count === 3, "Size doesn't match");
console.assert(test.size(0) === 0, "First stack is not empty");

test.push(1, 3);
console.assert(test.size(1) === 1, "Second stack items don't match expected");
console.assert(test.peek(1) === 3, "Second stack items don't match expected");

test.add(0, [5, 6, 7]);
console.assert(test.count === 4, "New stack was not added");
console.assert(test.size(0) === 3, "New stack size doesn't match what's expected");
console.assert(test.peek(0) === 7, "Second stack items don't match what's expected");