Implementing a Stack, pt1

Here's beginner question that can end up being surprisingly deep. It seems extremely simple, but I couldn't get the bonus on my own, so I'm doing an obnoxiously thorough case study:

Implement a stack, with push, pop, and getMax methods. push should push a single item to the top of the stack and return the length of the stack. pop should remove the last item of the stack and return the removed item. getMax should return the highest value out of the numbers stored on the stack.

Bonus: getMax should compute in O(1) time.

So, the stack itself is fairly easy. I'll avoid using arrays and native array methods, so that I at least have to build it myself.

Here's what the constructor itself might look like:

function Stack(){
    this.storage = {},
    this.length = 0
}

Pretty straightforward, right? We've got 0 items in our stack, so our length is 0 and our storage has nothing in it.

We want to be able to store stuff in our stack, so let's add a push method to our Stack() constructor's prototype. We expect our push to store a single item at the top of our stack. This means two things:

1. we'll be taking a single argument
2. we need to keep track of the order our items are in

We can basically steal ideas from arrays as a strategy for keeping our items in the correct order. We'll create key/value pairs on our storage object that correspond with the index that they would have if it were an array.

Luckily, we'll know that the next item on our stack will exist at the index of our length. This is to say, when we have a length of 0 (0 items in the storage), the next item we'll add will be the '0th' index item. When we've got one item in the storage, our length will be 1, and our next item will be an item at index 1.

So, our strategy is to take the length of the array, use it as a key in our storage and store the value of the item we're pushing. After that, we'll increment our length value to keep it up to date with our storage. Finally, we'll return our length, just to keep it up to spec.

Our file will look like this:

function Stack(){
    this.storage = {},
    this.length = 0
}

Stack.prototype.push = function(item){
    this.storage[this.length] = item;
    this.length = this.length + 1;
    return this.length;
}

Next, we'll add the pop method. This will simply delete the top item from our object, update our length to stay accurate, and return the item that we deleted.

So here's how we're gonna do that:

1. decrement our length by 1
2. save the value of storage at length to a separate variable, since it'll be the last item in our storage
3. delete that item from our storage (we saved it to a separate variable)
4. return the saved item using our saved variable

And here it is:

function Stack(){
    this.storage = {},
    this.length = 0
}

Stack.prototype.push = function(item){
    this.storage[this.length] = item;
    this.length = this.length + 1;
    return this.length;
}

Stack.prototype.pop = function(){
    this.length = this.length - 1;
    const output = this.storage[this.length]; //our stored value
    delete this.storage[this.length];
    return output;
}

Finally, the real work, which is our getMax function. There's an obvious way to do it, which would just mean taking the values from our storage and invoking Math.max() on them.

function Stack(){
    this.storage = {},
    this.length = 0
}

Stack.prototype.push = function(item){
    this.storage[this.length] = item;
    this.length = this.length + 1;
    return this.length;
}

Stack.prototype.pop = function(){
    this.length = this.length - 1;
    const output = this.storage[this.length]; //our stored value
    delete this.storage[this.length];
    return output;
}

Stack.prototype.getMax = function(){
    return Math.max(Object.values(this.store));
}

This is a decent solution to grabbing a max value, but it's not perfect by any means. It operates in O(n) time, since Math.max() needs to look at all of the values in our stack before it can definitively know what the highest number is.

All of the fun starts in part 2, where we'll actually finesse our getMax to operate in the holy grail of time complexities, O(1) time.

update! here's part 2