Implementing a Stack, pt1
Tags: algorithms, javascript
Published: 2019-03-03 00:35:01

---
title: Implementing a Stack, pt1
series: Implementing a Stack
published: true
description: 
tags: algorithms, javascript
---
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:

```javascript
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:
```javascript
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:

```javascript
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.

```javascript
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](https://dev.to/tttaaannnggg/stack-pt2-o1-max-18ik)