Overthink

Home
Data Structures
Data Structures - Part 2 - Stacks + How to Implement
Damian
March 15, 2021
2 min

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.

stack

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 whats next to be removed, length, and isEmpty. Well 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 well 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.
    • compilers 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.

Damian

Software Developer

Full stack developer, applying programming skills to solve complex challenges. Developing high quality, high performance and highly reliable software applications.

Expertise

JavaScript
TypeScript
React
NodeJS
GraphQL

Social Media

githubtwitter

Related Posts

Data Structures - Part 1 - Queues + How to Implement
March 03, 2021
3 min