The stack
Tags: computerscience, typescript, data, beginners
Published: 2020-06-05 23:03:26

A stack is an abstract data structure which uses an order of operations called LIFO (Last In First Out) which does as it says on the tin, the last element added to the stack will be the first one to be removed. 

> You can think of this like a stack of plates, adding or removing plates is only possible from the top of the stack.

Thus, a stack controls elements held within via two principal operations:

1. The `push` operation adds an element to the collection
2. The `pop` operation removes the most recent element in the collection

There are a few other methods which we will implement but the ordering combined with these operations are the signature of a stack. 

> Stacks are used in a variety of ways in the real world, for example the JavaScript [Call Stack](https://developer.mozilla.org/en-US/docs/Glossary/Call_Stack) is a stack which tracks function calls and allows the browser to track all the various things being executed as they run without conflicts between calls occurring.

In this article we will explore how I would implement a stack and I will also explain each method we implement in detail.

## Tests

For the tests of our stack I will be using the [Jest](https://jestjs.io/) test runner alongside [ts-jest](https://www.npmjs.com/package/ts-jest) which will support us to test our [TypeScript](https://www.typescriptlang.org/) implementation.

```ts
let stack: Stack<number>;

beforeEach(() => {
  stack = new Stack<number>();
});

describe("Stack", () => {
  it("Should have predictable defaults", () => {
    expect(stack.count).toBe(0);
    expect(stack.items).toEqual([]);
  });

  it("Should add an item to the stack", () => {
    stack.push(1);
    expect(stack.count).toBe(1);
  });

  it("Should return the index of the item added to the stack", () => {
    expect(stack.push(1)).toBe(0);
  });

  it("Should remove an item from the stack", () => {
    stack.push(1);
    expect(stack.count).toBe(1);
    expect(stack.items).toEqual([1]);
    stack.pop();
    expect(stack.count).toBe(0);
    expect(stack.items).toEqual([]);
  });

  it("Should return the value of the item removed from the stack", () => {
    stack.push(1);
    expect(stack.pop()).toBe(1);
  });

  it("Should return undefined if no items exist in the stack when trying to pop the top value", () => {
    expect(stack.pop()).toBe(undefined);
  });

  it("Should return undefined if the item being searched for doesn't exist", () => {
    expect(stack.find(1)).toBe(undefined);
  })

  it("Should return the index of the value if it is found", () => {
    stack.push(1);
    expect(stack.find(1)).toBe(0);
  });

  it("Should allow us to peek at the item at the top of the stack", () => {
    stack.push(1);
    expect(stack.peek()).toBe(1);
  });

  it("Should return undefined if there is no item to peek at", () => {
    expect(stack.peek()).toBe(undefined);
  });

  it("Should let us check if the stack is empty", () => {
    expect(stack.empty()).toBe(true);
  });

  it("Should let us check how many items are in the stack", () => {
    expect(stack.size()).toBe(0);
  });

  it("Should clear the stack", () => {
    stack.push(1);
    stack.push(1);
    expect(stack.count).toBe(2);
    expect(stack.items).toEqual([1, 1]);
    stack.clear();
    expect(stack.count).toBe(0);
    expect(stack.items).toEqual([]);
  });
});
```

For the tests I chose to use a `Stack` using `number` types for simplicity. If you want to explore and run the tests, you can use the repl below.

{% replit @jamesrweb/stacks %}

## Implementation

For this implementation we will be using [TypeScript](https://www.typescriptlang.org/).

```ts
class Stack<T> {
  public items: T[] = [];
  public count: number = 0;

  push(item: T): number {
    this.items[this.count] = item;
    this.count++;
    return this.count - 1;
  }

  pop(): T | undefined {
    if(this.count === 0) return undefined;
    this.count--;
    const deletedItem = this.items[this.count];
    this.items = this.items.slice(0, this.count);
    return deletedItem;
  }

  find(value: T): number | undefined {
    for(let index = 0; index < this.size(); index++) {
      const item = this.items[index];
      if(Object.is(item, value)) return index;
    }

    return undefined;
  }

  peek(): T | undefined {
    return this.items[this.count - 1];
  }

  empty(): boolean {
    return this.count === 0;
  }

  size(): number {
    return this.count;
  }

  clear(): T[] {
    this.items = [];
    this.count = 0;
    return this.items;
  }
}
```

We are using [Generics](https://www.typescriptlang.org/docs/handbook/generics.html) as a part of the implementation to provide opt-in type strictness for our stack, this is represented by the type `T` in the implementation above. To see this in action we can do this for example:

```ts
const stack = new Stack<number>();
stack.push(1); // Works fine
stack.push("1"); // Throws a TypeError
```

If no type `T` is provided then anything can be added into the stack like so:

```ts
const stack = new Stack();
stack.push(1); // Works fine
stack.push("1"); // Also works fine
```

Personally though, I would recommend that if you don't want to lock the types of the items in your stack then add the explicit `any` type to the `T` type instead since being explicit is always better than being implicit with such things, for example:

```ts
const stack = new Stack<any>();
stack.push(1); // Works fine
stack.push("1"); // Also works fine
```

### Properties

Our `Stack` contains 2 properties, the `items` currently within the stack and the `count` of the items in the stack, we can access these like so:

```ts
const stack = new Stack();
console.log(stack.count); // 0
console.log(stack.items); // []
state.push(1);
console.log(stack.count); // 1
console.log(stack.items); // [1]
```

### Methods

Alongside the properties of the `Stack` are it's methods, let's explore these and what they do a bit more.

#### `push`

The `push` method adds an item to the stack and returns the index of that item once added, for example:

```ts
const stack = new Stack();
const idx = stack.push(1);
const idx2 = stack.push(2);
console.log(idx, idx2, stack.items); // 0, 1, [1, 2]
```

#### `pop`

The `pop` method removes an item from the stack and returns the value of the removed item, for example:

```ts
const stack = new Stack();
stack.push(1);
stack.push(2);
const item = stack.pop();
console.log(item, stack.items); // 2, [1]
```

#### `find`

The `find` method finds an item in the stack and returns its index if it is found or `undefined` if it isn't, for example:

```ts
const stack = new Stack();
console.log(stack.find(1)); // undefined
stack.push(1);
console.log(stack.find(1)); // 0
```

#### `peek`

The `peek` method lets us check what item is currently at the top of the stack, for example:

```ts
const stack = new Stack();
stack.push(1);
console.log(stack.peek()); // 1
```

#### `empty`

The `empty` method lets us check if the stack is empty or not, for example:

```ts
const stack = new Stack();
console.log(stack.empty()); // true
stack.push(1);
console.log(stack.empty()); // false
```

#### `size`

The `size` method lets us see how many items are in the stack currently, for exmaple:

```ts
const stack = new Stack();
console.log(stack.size()); // 0
stack.push(1);
console.log(stack.size()); // 1
```

#### `clear`

The `clear` method lets us remove all items from the stack, for example:

```ts
const stack = new Stack();
stack.push(1);
stack.push(1);
stack.push(1);
console.log(stack.count, stack.items); // 3, [1, 1, 1]
stack.clear();
console.log(stack.count, stack.items); // 0, []
```

## Conclusions

Stacks are really efficient data structures for setting, getting, deleting and finding a value, we can see that with the Big O of these operations coming in as follows:

|        | Average | Worst |
|--------|---------|-------|
| Get    | Θ(n)    | Θ(n)  |
| Set    | Θ(1)    | Θ(1)  |
| Delete | Θ(1)    | Θ(1)  |
| Find   | Θ(n)    | Θ(n)  |

This makes it one of the most efficient data structures that you can use and this is why it one of the most common data structures you will come across when developing software.

I hope this post brought you some value and feel free to leave a comment below!