loading...
Cover image for The stack

The stack

jamesrweb profile image James Robb ・5 min read

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 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 test runner alongside ts-jest which will support us to test our TypeScript implementation.

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([]);
  });
});
Enter fullscreen mode Exit fullscreen mode

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.

Implementation

For this implementation we will be using TypeScript.

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;
  }
}
Enter fullscreen mode Exit fullscreen mode

We are using Generics 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:

const stack = new Stack<number>();
stack.push(1); // Works fine
stack.push("1"); // Throws a TypeError
Enter fullscreen mode Exit fullscreen mode

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

const stack = new Stack();
stack.push(1); // Works fine
stack.push("1"); // Also works fine
Enter fullscreen mode Exit fullscreen mode

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:

const stack = new Stack<any>();
stack.push(1); // Works fine
stack.push("1"); // Also works fine
Enter fullscreen mode Exit fullscreen mode

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:

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]
Enter fullscreen mode Exit fullscreen mode

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:

const stack = new Stack();
const idx = stack.push(1);
const idx2 = stack.push(2);
console.log(idx, idx2, stack.items); // 0, 1, [1, 2]
Enter fullscreen mode Exit fullscreen mode

pop

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

const stack = new Stack();
stack.push(1);
stack.push(2);
const item = stack.pop();
console.log(item, stack.items); // 2, [1]
Enter fullscreen mode Exit fullscreen mode

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:

const stack = new Stack();
console.log(stack.find(1)); // undefined
stack.push(1);
console.log(stack.find(1)); // 0
Enter fullscreen mode Exit fullscreen mode

peek

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

const stack = new Stack();
stack.push(1);
console.log(stack.peek()); // 1
Enter fullscreen mode Exit fullscreen mode

empty

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

const stack = new Stack();
console.log(stack.empty()); // true
stack.push(1);
console.log(stack.empty()); // false
Enter fullscreen mode Exit fullscreen mode

size

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

const stack = new Stack();
console.log(stack.size()); // 0
stack.push(1);
console.log(stack.size()); // 1
Enter fullscreen mode Exit fullscreen mode

clear

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

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, []
Enter fullscreen mode Exit fullscreen mode

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!

Discussion

pic
Editor guide
Collapse
danlec profile image
Dan Leclaire

Interesting indeed. Elegantly laid out too! thanks for sharing James!

Collapse
jamesrweb profile image
James Robb Author

You're welcome Dan, glad you found some value in the post, thanks for dropping by!