DS — Stack implement in JS

Welcome to my 2nd article in series of Data Structures in JS I’m working on. This time we will discuss about Stack, a popular data structure term in programming, especially “Stack overflows” — reminds you of something? :)

OK so let’s begin.

What is Stack?

Yup, it’s an example of Stack — Stack of pancakes

In programming, Stack is dynamic collection of elements in which:

• New element is added to stack using push() operation.
• Element is deleted/removed from stack using pop() operation, which strictly follows LIFO (Last-In, First-Out) concept — the most recent added one will be removed.

Indeed, take stack of pancakes for example, it’s obvious that new pancake will be added to the top of the stack, and remove the top most one for eating. Of course you can try the opposite direction, but why should you?

Another good example for Stack is chained activities execution. Let’s say, you have activity called Build your own Computer, in order to execute it, first you need to execute Buy all computer parts, but before this, you need to execute Research for best computer parts, etc… Each of the activity is chained/ waiting for the other activity to be finished executing before it can continue. And hence the activity stack will look like:

Activity stack — push() and pop()

This is similar example to our computer call stack. Using stack in this case ensures we won’t miss out any required sub-activity before completing the main activity.

How do we implement it?

• Basic structure

STACK {
   1. current size of the stack - or the index of the next top, initialize with 0.
   2. Object represents where we store all stack elements
}

• Push(item)

PUSH(item){
   1. Assign item to the available top index
   2. Increment the stack size - or prepare the index of the next top.
}

• Pop()

POP(){
   1. Check if stack is empty, if so return.
   2. Reduce the size of stack - aka the current top index.
   3. Get the current top element.
   4. Remove it from the storage by delete operation for Object Prototype.
   5. Return the element
}

• Peek()

PEEK(){
   1. Check if stack is empty, if so return.
   2. Else, return top element at index currentSize - 1.
}

• StackEmpty()

STACKEMPTY(){
   1. While stack is not empty
      1.1 Call pop()
}
}

Stack overflows/underflows

• Stack overflows

So what is “stack overflows” that we heard so much about? It’s status when the size of a stack exceeds the maximum allowed number — stack bound — say n. Normally this number is defined before hand.

One good example is when we try to execute recursive process, and if the process stopping condition is not well-defined, aka the process runs itself infinitely (except in reality, it will cause “stack overflows” and crash).

• Stack underflows

It is the status when an empty stack is popped. This is not a big issue since we always have the protection check before we try to pop() a stack.

The Code

A full DEMO can be found here.

Not using Array? Why?

As explained before in Queue article, I decided to use Object instead of Array because:

• Most operations in Array Prototype in JS has O(n) running time.
• Array needs to keep its order, hence it takes up a block of space.
• Object property can be added/accessed easily with O(1) running time.
• And most important, everything in JS is treated as Object anyway, so why not?

Complexity

• Push(item) — O(1) running time
• Pop() — O(1) running time.
• Peek() — O(1) running time.
• StackEmpty () — O(n) running time with n is the size of the stack

Summary

Stack is very common data structure which has a lot of applications — backtracking, computer call stack, JAVA virtual machine, etc…

It is easy to implemented, however, bear in mind Stack is good to use when order of elements doesn’t matter (batch jobs for instance).

When the order does matter and we want to minimize the maximum waiting time, it’s suggested to switch to Queue — similar concept but follows LIFO.

Now, are you up to a little challenge? Let’s implement Backtracking algorithm using Stack, shall we?

Want to know more about Queue? Here you go.

Have fun with data structures :) !

If you like this post and want to read more, feel free to check out my articles.

If you’d like to catch up with me sometimes, follow me on Twitter | Facebook or simply visit my portfolio website.

Maya Shavin (@MayaShavin) | Twitter