Implementing Stacks in JavaScript

One type of data structure you can use when solving algorithms is a stack. A stack is a linear structure where adding or removing of an element follows a particular order: LIFO (Last In First Out) or FILO (First In Last Out).

I’ll be using a sample problem from LeetCode called Valid Parentheses

In this problem you receive a string of characters that can only be “()”,”[]”,”{}”, and you must create an algorithm to check if the string is valid (i.e. all openings are closed) and it gives you examples of what qualifies asa a a valid string as well as sample inputs with appropriate outputs.

My thought process to go about this was to check every character starting form the beginning and add it to a data structure if its an opening (
“(“ , ”[“ ,”{“) and if its a close closing ( “)”, “]”, “}”) check to see if the last item in my data structure is the corresponding opening, and if it is, remove that character from my data structure. If none of these conditions are met, return “false” as the closing does not match the latest opening, therefore not a valid string, and if at the end of the string, my data structure is empty, then return “true” because all the openings have been closed, otherwise false because there was an opening left unclosed.

I realized that a data structure that fits this well is a stack (since I’ll need LIFO method for adding/removing). The two ways I learned to implement them are by creating a Stack class (I call this for “formal” way) or using an array (I call this the “informal” way). Although simply using an array is much easier, I included the “formal” way in case you need to implement it in a tougher problem.

  1. Creating a Stack class
class Stack {
constructor () {
this.head = null;
this.tail = null;
this.length = 0;
this.data = []
}
push(element){
this.data.push(element)
}
pop(){
if (this.data.length == 0){
return false
}else{
this.data.pop()
}
}
peek(){
return this.data[this.data.length-1]
}
isEmpty(){
return this.data.length == 0
}
}

For this method you create a class and name is Stack, in the constructor you declare the initial values for the class and you declare the helper methods you’ll need, in this case it’ll be push (to add item),pop (to remove item),peek(to see last item), and isEmpty(to see if the stack is empty. With this you can implement the solution below

var isValid = function(s) {

let stack = new Stack
for (let i=0; i < s.length; i++){
if (s[i] === "(" || s[i] === "[" || s[i] === "{"){
stack.push(s[i])
} else if (s[i] === ")" && stack.peek() === "("){
stack.pop()
} else if (s[i] === "]" && stack.peek() === "["){
stack.pop()
} else if (s[i] === "}" && stack.peek() === "{"){
stack.pop()
} else{
return false
}
}
return stack.isEmpty()
}

Notice how I create a new instance of the “Stack” class and assigning it to a variable “stack”. This will allow me to use the helper methods on the stack as needed (push to add any openings, peek to check the last item in my stack, pop to remove the last item, isEmpty to check if the stack is left empty after we iterate through the string).

Note to self — I just realized that instead of “peek”, I could’ve named the helper method “last” or something similar for clarity.

By now you probably noticed that I created an entire class for one instance, which creates an array, to use helper methods that would’ve worked directly on the array anyway (or have a simple work around). This is why I ended up using the second method: simply using an array.

2. Using an array

For this method I avoid the class all together and simply assign an array as my stack:

var isValid = function(s) {

let stack = []

for (let i=0; i < s.length; i++){
if (s[i] === "(" || s[i] === "["|| s[i] === "{"){
stack.push(s[i])
} else if (s[i] === ")" && stack[stack.length-1] === "("){
stack.pop()
} else if (s[i] === "]" && stack[stack.length-1] === "["){
stack.pop()
} else if (s[i] === "}" && stack[stack.length-1] === "{"){
stack.pop()
} else{
return false
}
}
return !stack.length
};

Notice how push and pop remain unchanged, and instead of peek I simply search directly for the last item in the array, and instead of isEmpty I check if the length is 0 (falsy) or not (truthy) and return the opposite since length of 0 means the string is valid(all openings are properly closed).

While this works just fine, it’s not very DRY (i.e. a lot of repeating) and not reusable (only fits that one specific situation), therefore I wanted to figure a way to dry it up a bit. I realized that all the openings have the same reaction (add to stack), therefore I created an array to group all the openings:

var isValid = function(s) {

let stack = []
const openings = ["(","[","{"]

for (let i=0; i < s.length; i++){
if (openings.includes(s[i])){
stack.push(s[i])
} else if (s[i] == ")" && stack[stack.length-1] === "("){
stack.pop()
} else if (s[i] == "]" && stack[stack.length-1] === "["){
stack.pop()
} else if (s[i] == "}" && stack[stack.length-1] === "{"){
stack.pop()
} else{
return false
}
}
return !stack.length
};

Although this helps a bit, especially in the edge case that another opening is added, it doesn’t do anything to the closing. After some thinking I came up with this:

var isValid = function(s) {

const ref = {
')' : '(',
']' : '[',
'}' : '{',
}

const stack = []

for (const char of s) {
if (char in ref) {
if (ref[char] === stack[stack.length - 1]) {
stack.pop()
} else {
return false
}
} else {
stack.push(char)
}
}
return !stack.length
}

Here is what I did:

  • I created a reference object to save all the closings and their respective openings, this way if there are other pairs that need to be added, it can be done easily and the code will work

I realized the above improvements sacrifices a bit of time, but the time complexity is still O(n) (linear time) and it needs more memory usage with the use of an object, but that’s negligible since space complexity is still O(n). However, the code is much cleaner and it allows for any number of opening and closing pairs.

Here’s an article that helped me understand this: https://www.geeksforgeeks.org/implementation-stack-javascript

If you need help visualizing how a stack works, check this site out: http://visualgo.net/en/list