In previous posts we learned what data structures are and their importance when engineering software applications. In this post, we will learn a new data structure called a Stack, and find out what benefits it gives us when storing and organizing data. What is a stack? Well, the meaning is in the idea of the word. Think of a stack of books or papers in a bookstore, or a stack of dirty plates in kitchen. The idea is we have a container (our stack) in which things (data) are stacked on top of another. We are trying to organize data in a stacking order, hence the name. When we add an item, it is added to the top of the stack. And when we remove, we also remove from the top. So think of javascript stacks as a collection in which data is added or removed in a Last In First Out (LIFO) out manner. Lets take a look at a simple diagram. 

Here you see we have a stack container with 3 data items. First we added “Data 1”, then “Data 2” and finally “Data 3”. Adding an item onto the stack is known as pushing onto the stack. One can also peek into the stack. This is like looking into the container. So calling a peek operation on a stack will return “Data 3” (which is at the top). The more items you at to the stack container, the bigger the stack depth/size increases. Just like pushing onto the stack, you can also pop onto the stack. You can think of push & pop operations within the stack just as you would in an array. When you push you add to the end of the array (which is the top). And when you pop it returns the top element. Lets look at this diagram, popping “Data 3” from the stack.

When “Data 3” is popped from the stack, “Data 2” becomes the new top. We can find out by calling the peek operation (returns the item at the top). The 3 fundamental stack operations are push, pop, and peek. We do not need to worry about any other operation as stacks are not designed for those. This is done so by intention. We are not concerned with adding to the middle or beginning of the stack, or about next/previous pointer references (like in linked lists). We don’t even care about indexing in the stack. So if you find yourself trying to do crazy things with a stack, you are probably using the wrong data structure. We will be implementing 3 additional operations however. Clear will remove everything from the stack (empty it), length will return the total number of items, and empty returns true or false (whether the stack is empty or not).

So you might be asking yourself. Why the hell would i ever want to use a stack? They sound very limited, yes, but it is so for a reason. Stacks are used to solve some specific types of problems.. well lots of specific problems 🙂

1. A number base converter, where you can convert a number from one base to another
2. If we ever wanted to write a Palindrome algorithm we could also use a stack. A palindrome is a word that is spelled the same forward and backward. For example “racecar”. When you reverse it, you get “racecar”. Other palindrome words include dad, madam, noon, kayak, refer, etc.
3. Recursive processes. If you are interested in learning about recursion in javascript, look at this tutorial.
4. Write a factorial algorithm using recursion in this post.
5. You can write postfix algorithms and build a postfix calculator.
6. “Undo” operations in your application.
7. Virtual Pez dispenser
8. Balancing of symbols ( for example a stack can be used to ensure a mathematical expression has balanced parenthesis. this balancing of symbols capability is also very important in compiler operations )
9. Matching tags in HTML and XML
10. Back button in a web browser (page history)
11. Google chrome’s V8 engine also has a call stack which keeps track of program execution. Pretty much it keeps track of statements and functions that are fired. Functions that are called get pushed onto the stack and are popped off when complete.

As you can see, stacks are very useful and important! Knowing how to implement one can help you tremendously when building software applications.

Stack Implementation

A stack can be implemented using a simple array or linked list as its backend data store. At the end of the day it’s a collection of data (with a special order), meaning we can use data structures such as an array or linked list as a container for our data. For example arrays allow you to add data to it. However when you add data to an array, it is not put at the zeroth index, it is pushed to the back. So all we do in the case is consider the end of the array as the top of the stack. Simple! There are methods within an array that allows you to add items to the front of the array (like – unshift), but this will not be performant as that operating requires shifting and reindexing of arrays. The same with a linked lists. In the previous post, we saw how to add an item to the head/tail of the list. Specifically speaking we say how to add to the tail of the list (which is like adding to the top).

So we can use these data structures as part of our Stack algorithm. The question is, which one is best suited? In this post will looking at how to implement our stack using an array data structure. We are using an array here before they give us a little bit more performance than using a linked list. The reason has to do with the way arrays store data next to each other. Performing operations like push, pop, peek, etc. has a time complexity of O(1) and space complexity of O(n). You can find similar runtime and space complexity in linked lists, overall its better in an array. You can read more about this in the singly linked list post. Lets write some code.

The Stack Class

Let’s write basic Stack class

See the Pen Stack Class Shell by kofi (@scriptonian) on CodePen.

Simple right?! We create a class called Stack and give it one property: items. Items will be used to store guess what? Our stack items…duh! and is of type array. Now i have a little surprise for you. Lets write this in ES 2015!! Yes i have decided to write both ES5 and ES6 in my blogs moving forward, with the hopes of getting away from ES5 in the near future. Here is our Stack class

See the Pen Stack Class Shell – ES2015 by kofi (@scriptonian) on CodePen.

Looks fancy huh?!ES2015 is only syntactic sugar (as they call it) around ES5 and is the future of javascript. It makes writing javascript a little bit easier as you have nicer ways of writing javascript code. Since many are using it now for obvious reason, i guess you understand why i am doing the same. If you are not using ES2015, just ignore it and use the ES5 version of the stack. But from now on i will write both. It is also worth me mentioning that ES2015 does not fall only under the syntactic sugar umbrella, there are many enhancements to the language as well (new constructs that have been introduced). So it is definitely worth your time.

Stack Operations

Lets extend our basic stack class with its operations.

See the Pen Stack Operations by kofi (@scriptonian) on CodePen.

and the ES2015 version

See the Pen Stack Operations – ES2015 by kofi (@scriptonian) on CodePen.

Remember that the 3 main operations within a stack are push, pop and peek. However we wanted to enhance our class to do a few more things. We wanted to be able to implement other operations such as: finding if the stack was empty, getting the total number of items in the stack and finally we wanted a way to delete all items in the stack.

push, pop and peek

Lets implement this 3 main operations for our stack

See the Pen Push, Pop and Peek by kofi (@scriptonian) on CodePen.

Here is the ES2015 version

See the Pen Push, Pop and Peek – ES2015 by kofi (@scriptonian) on CodePen.

As you can see there is nothing really magical here. Push is pushing the item into the array (the end of the array which we are calling the top), peek returns whatever is at the end of the array (the top), and pop just removes whatever is at the end of the array (which is also the top)!

size, clear and isEmpty

Lets finish up our stack implementation by writing the code of the remaining operations.

See the Pen Size, Clear and isEmpty by kofi (@scriptonian) on CodePen.

And the ES2015 version

See the Pen Size, Clear and isEmpty – ES2015 by kofi (@scriptonian) on CodePen.

Again, nothing special with this code. isEmpty returns the boolean of whether the length of the items array is zero or not, size returns the length of the items array and clear simply sets the items array to empty (like erasing everything). OK our stack class is done. Lets create a stack and perform some operation

Using the Stack Class

We will use the example we saw in the first diagram of this post. We will create a stack by pushing “Data 1”, “Data 2” and “Data 3” and performing pop and peek operations! We will also see our 3 other operations in action.

See the Pen Using the Stack by kofi (@scriptonian) on CodePen.

What do we see when we log the stack to our console?

We added “Data 3” last and so we see it at the end of the array ( which in our case, we consider to be the top of the stack ). So this means when we call  peek, we SHOULD get “Data 3” returned. When we pop it should remove “Data 3” and “Data 2” should be on the top of the stack.

When we call peek on the stack it returns “Data 3” since that is at the top. And when we pop, we remove “Data 3”. Notice that “Data 2” is now at the top. When we query for the size of the stack, we get 2.

Solving problems using Stacks

So now that you know how to implement a stack, how can you use it in the real world? I mentioned some cases where you could use a stack data structure to solve specific problems. Lets take on some of these! We will implement a palindrome, a multiple number base converter and we will see how to write a factorial function using stacks! But first, a palindrome. You can find the source on github.

Palindrome using a javascript stack

See the Pen Palindrome with JS Stack by kofi (@scriptonian) on CodePen.

While there are many ways you could implement a palindrome, we are mainly focussed here on how to do it with a stack. You will see i have provided a non-stack alternative at the end of that last sample code.

Our palindromeTest function takes a word as a parameter. We create a stack and push each letter of the word onto the stack. We then create a while loop to go through each letter in the stack and append it to a wordRevised variable (the word has to spell the same forwards and backward, kayak spelled backwards is kayak). The function returns the reversed word and we check to see if its the same as the original.

Factorial using a stack

Lets see how to implement a factorial function using a stack, for example 5! = 5 x 4 x 3 x 2 x 1 = 120. To get this to work its a good idea that you understand recursive processes. I provided a link earlier so please take a look.

See the Pen Javascript Stack – Factorial by kofi (@scriptonian) on CodePen.

In the example above, you create stack and push numbers onto it (decrementing the factorial number by 1 on each iteration). Once everything is on the stack, you loop through again popping each number off the stack and multiplying them. This may not be the most efficient way of implementing a factorial, however the point here is to demonstrate how stacks can be used to solve real world problems.

Number Base Converter using stack

Remember back in high school when you learned how to do number base conversions? Given any decimal number (base 10) you would be asked to convert it to another base (say from 2 – 9). Growing up in Ghana, here is how i remember doing them

Above i convert 64 to base 2 (left) and base 3 (right). Here is the algorithm for converting the number.

1. you start off with 2 numbers. The decimal number and the base to which to convert to ( function parameters)
2. you divide the decimal number by the base and you push the remainder on a stack (on the right).
3. the new decimal number is the result of the first division. first n was 64, in the next iteration n is 32 (on the next iteration) and so forth until there are no remainders
4. finally output everything on the stack into a string …for eg 1000000 (base 2) or 2101 (base 3)

Let see this in javascript

See the Pen Number Base Converter – Javascript by kofi (@scriptonian) on CodePen.

I wrote this based on how i learned how to do base conversions. Yours might be different, but will ultimately give the same answer.

We can go on and on with Stacks. I hope you see why they are so important as a javascript developer. I have mentioned many of its uses and i will provide a lot more solutions on my github page, the whole point of this post is to give you an idea of what you can do with stacks in javascript. Stacks also fall into interview type questions, so understanding them can help you get that next job. Hope you have appreciate stacks a lot more now. If you have any special requests, kindly comment and i will get back to you as soon as possible. Feel free to reach out on twitter as well ( @scriptonian ) if you have any questions. Next, lets talk about Queues!