Data Structures — Part 2 — Stacks + How to Implement

Stack

A stack is a structure to store data unidirectionally. This means that the way to add or remove elements occurs in a single direction (from start to finish).

Unlike queues, stacks operate under a LIFO ( L ast I n F irst O ut) system. This means that the element closest to being removed will be the one that has entered more recently.

A very simple example of the implementation of a stack could be seen in the Undo / Redo system. Every time we access a page, it is saved in the history in a stack structure, so that when we click "Back" in the browser it takes us to the last record stored in the stack.

How Implement a Stack ?

Stack Implementation

Our stack will have several methods and properties, push, pop, peek, to look at what's next to be removed, length, and isEmpty. We'll start by creating an array held in closure to store our items.

We want to keep our collection in the correct order, so we always want to add and remove items from the same side of the array.

Push

Using push, we place new items at the end of the array.

function push(item) {
  stack.push(item);
}

The push method will add an item to the end of our array.

Reference Push Method

Pop

With pop, we remove the final item from the array. This ensures we maintain order in our stack.

function pop() {
  return stack.pop();
}

Peek

Now we'll create our peek method by returning the last item in our array.

function peek() {
  return stack[stack.length - 1];
}

If you wonder about the notation in brackets. It is the way we have to access an element by its index in javascript.

Length

We can create our length property. For this we can rely on a getter function that takes the size of the collection.

function get length() {
  return stack.length;
}

Is Empty

And finally we will add our isEmpty method to check if the collection is empty.

function isEmpty() {
  return stack.length === 0;
}

Let's put it all together

function createStack() {
  const stack = [];

  return {
    push(item) {
      stack.push(item);
    },
    pop() {
      return stack.pop();
    },
    peek() {
      return stack[stack.length - 1];
    },
    get length() {
      return stack.length;
    },
    isEmpty() {
      return stack.length === 0;
    }
  };
}

const lowerBodyStack = createStack();

lowerBodyStack.push("underwear");
lowerBodyStack.push("socks");
lowerBodyStack.push("pants");
lowerBodyStack.push("shoes"); 

console.log(lowerBodyStack.pop()); // shoes
console.log(lowerBodyStack.peek()); // pants
console.log(lowerBodyStack.length); // 3

Real Life Uses

• An "undo" mechanism in text editors; this operation is accomplished by keeping all text changes in a stack. Undo/Redo stacks in Excel or Word.
• Language processing :
  • space for parameters and local variables is created internally using a stack.
  • compiler's syntax check for matching braces is implemented by using stack.
• A stack of plates/books in a cupboard.
• A garage that is only one car wide. To remove the first car in we have to take out all the other cars in after it.
• Wearing/Removing Bangles.
• Back/Forward stacks on browsers.
• Support for recursion
  • Activation records of method calls.