Stacks

Getting started

For the first structure in the series, let's implement a stack as a JS class similar to what is available on Leetcode's 155 Min Stack.

Functionality

Stacks are simple, having only a few methods: push, pop, and peek. The class is basically a wrapper around an array, so I'll explain each method in terms of the underlying structure. push adds an item to the end, pop removes the last item, and peek returns the last item. Values other than the last item in the array are inaccessible. You can think of this as last-in, first-out, or as a stack of plates where you would interact with the top of the stack only unless you're a germaphobe like me who grabs the second one in case there's dust on the top one 😅.

class Stack {
  stack: T[]
  constructor(stack) {
    this.stack = stack || []
  }

  push(item: T) {
    this.stack.push(item)
  }

  pop() {
    this.stack.pop()
  }

  peek() {
    return this.stack.at(-1)
  }
}

This implements the most basic functionality, although I've also seen it implemented without using the array methods, which require storing the length separately. In fact, when I first did Leetcode 155 I implemented the problem this way which I've posted here.

Additional functionality

Some additional methods inspired by the Min Stack problem, are to get the minimum and maximum values from a stack of numbers which is done by creating separate substacks to keep the lowest or highest values, then handling these whenever there's a push or pop. Here's the result:

class Stack {
  stack: number[]
  min: number[]
  max: number[]
  constructor() {
    this.stack = []
    this.min = []
    this.max = []
  }

  push(item: number): void {
    // Push to min stack if less than current min
    if (!this.min.length || item <= this.min.at(-1)) {
      this.min.push(item)
    }

    // Push to max stack if greater than current max
    if (!this.max.length || item >= this.max.at(-1)) {
      this.max.push(item)
    }

    this.stack.push(item)
  }

  pop(): void {
    // Remove min if same as item being popped
    if (this.stack.at(-1) === this.min.at(-1)) {
      this.min.pop()
    }

    // Remove max if same as item being popped
    if (this.stack.at(-1) === this.max.at(-1)) {
      this.max.pop()
    }

    this.stack.pop()
  }

  peek(): number {
    return this.stack.at(-1)
  }

  minimum(): number {
    return this.min.at(-1)
  }

  maximum(): number {
    return this.max.at(-1)
  }
}