Learning Stacks In JavaScript

My journey learning JavaScript Stacks and Algorithms

Learning Stacks In JavaScript

What is a stack?

Stacks are data structures used to store a collection of elements, that follows the First In Last Out (FILO) or Last In First Out (LIFO) principle. There are three main operations:

  • Push, which adds an element to the collection
  • Pop, which removes the most recently added element
  • Peek, which looks into the stack to see the most recently added element

When an element is added to a stack, it is placed on the top of all previously entered items. When removing an element from the stack it removes the most recently added element, this is considered a “FILO” stack. When peeking into the stack, this gives access to the top element without modifying the stack.

For me, the concept of stacks stuck when a good friend by the name of Roxkstar74 described a stack to be similar to a Pringles tube. A tube full with crisps that has been placed inside and stacked one by one from bottom to top.

pringles_in.gif

With a Pringle tube (stack) you must take the first crisp from the top of the tube before you can take out the next. Unlike a bag of crisps where you are able to reach in, root around and grab any delicious crisp you wish to eat.

Pringles tube outBag of crisps
pringle_out.gifbag_test.gif

When taking a crisp out of the Pringles tube, you are only able to take one crisp out at a time.

one_at_a_time.gif

You are not able to take out a crisp that has been placed below the top crisp in the tube. You must take out all crisps that are above the desired crisp you would like. In the below examples I want to eat crisp 3 that is in the middle of the tube. Before I can do so, I must take out and eat crisp 5 and then 4 after before being able to take crisps 3

in_middle.gif

Implementing a stack using JavaScript

Although Arrays in JavaScript provide all the functionality required for a Stack. There are times you are required to create these tiny portions of array methods, restricting access to other methods of an array.

Our JavaScript class will contain an empty array with the following functions

  • push(element), to push an element to the top of the stack
  • pop(), removes the top element and returns it

  • peek(), looks into the stack to see the most recently added element

We can start by creating a simple class with a constructor that initializes an empty array

class Stack {
  constructor() {
    this.data = [];
  }
}

Using the built in array methods push and pop we will create the push and pop functionality

...
  push(record) {
    this.data.push(record);
  }

  pop() {
    return this.data.pop();
  }

The last functionality we want to add is the peek method. To view the element at the top of the stack without removing it. To do this we will get the arrays length - 1 as arrays have an 0 based index.

...
  peek() {
    return this.data[this.data.length - 1];
  }

Full example of the JavaScript code

class Stack {
  constructor() {
    this.data = [];
  }

  push(record) {
    this.data.push(record);
  }

  pop() {
    return this.data.pop();
  }

  peek() {
    return this.data[this.data.length - 1];
  }
}

Example use of the Stack

//Example useage
const s = new Stack()
s.push(1)
s.push(2)
s.pop(); // returns 2
s.pop(); // returns 1

Functional programming code example

This may not be best practice, however, I wanted to try and create the Stack in a functional manner. Let me know in the comments if I should be taking this approach differently

const createStack = () => {
  return []
}

const add = (stack, element) => {
  stack.push(element)
}

const remove = (stack) => {
  return stack.pop()
}

const peek = (stack) => {
  return stack[stack.length - 1]
}
module.exports = {
  createStack,
  add,
  remove,
  peek,
}

Example usage

const stack = createStack()

add(stack, 1)
add(stack, 2)
const r = remove(stack) // returns 2
const next = peek(stack) // returns 1

Testing with Jest

This post does not go over setting up Jest, however, please see code examples of tests ran for both JavaScript Stack code examples.

Class testing examples

const Stack = require('./index')

describe('Stacks', () => {
  test('Stack is a class', () => {
    expect(typeof Stack.prototype.constructor).toEqual('function')
  })

  test('stack can add and remove items', () => {
    const s = new Stack()
    s.push(1)
    expect(s.pop()).toEqual(1)
    s.push(2)
    expect(s.pop()).toEqual(2)
  })

  test('stack can follows first in, last out', () => {
    const s = new Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    expect(s.pop()).toEqual(3)
    expect(s.pop()).toEqual(2)
    expect(s.pop()).toEqual(1)
  })

  test('peek returns the first element but doesnt pop it', () => {
    const s = new Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    expect(s.peek()).toEqual(3)
    expect(s.pop()).toEqual(3)
    expect(s.peek()).toEqual(2)
    expect(s.pop()).toEqual(2)
    expect(s.peek()).toEqual(1)
    expect(s.pop()).toEqual(1)
  })
})

Stack functional programming tests

const { createStack, add, remove, peek } = require('./functional')

describe('Stacks', () => {
  test('stack can add and remove items', () => {
    const s = createStack()
    add(s, 1)
    expect(remove(s)).toEqual(1)
    add(s, 2)
    expect(remove(s)).toEqual(2)
  })

  test('stack can follows first in, last out', () => {
    const s = createStack()
    add(s, 1)
    add(s, 2)
    add(s, 3)

    expect(remove(s)).toEqual(3)
    expect(remove(s)).toEqual(2)
    expect(remove(s)).toEqual(1)
  })

  test('peek returns the first element but does not pop it', () => {
    const s = createStack()
    add(s, 1)
    add(s, 2)
    add(s, 3)
    expect(peek(s)).toEqual(3)
    expect(remove(s)).toEqual(3)
    expect(peek(s)).toEqual(2)
    expect(remove(s)).toEqual(2)
    expect(peek(s)).toEqual(1)
    expect(remove(s)).toEqual(1)
  })
})

Thank you!

If you got this far, I appreciate the time you have taken to read my post and for joining me on my learning journey. Stay tuned for more posts as I progress my learning Journey.