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 🙂
- A number base converter, where you can convert a number from one base to another
- 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.
- Write a factorial algorithm using recursion in this post.
- You can write postfix algorithms and build a postfix calculator.
- “Undo” operations in your application.
- Virtual Pez dispenser
- 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 )
- Matching tags in HTML and XML
- Back button in a web browser (page history)
- 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.
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
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
Lets extend our basic stack class with its operations.
and the ES2015 version
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
Here is the ES2015 version
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.
And the ES2015 version
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.
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.
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.
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.
- you start off with 2 numbers. The decimal number and the base to which to convert to ( function parameters)
- you divide the decimal number by the base and you push the remainder on a stack (on the right).
- 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
- finally output everything on the stack into a string …for eg 1000000 (base 2) or 2101 (base 3)
I wrote this based on how i learned how to do base conversions. Yours might be different, but will ultimately give the same answer.