Data Structures: What's a Stack?

Among the many computer science fundamentals, Data Structures can be found near the top of the list of essential knowledge topics software developers should be well versed in. Data structures allow developers to efficiently manage large amounts of data and can have an impact on the performance of our program or algorithm depending on the data structure of choice. This will be a weekly series diving into some of the most common data structures with accompanying problems showing them in use.

First up is the STACK!

Now you're probably wondering what a stack is, the simplest way of understanding this data structure can be easily represented with a real-world example. If you go into your kitchen and open the cabinet that contains your plates you're likely to see them neatly placed in a stack, unless you're like me, and still need to unload the dishwasher 😆 Now think about how your plates ended up in this stack and how they are removed when you need to use them. It is highly likely that the last plate you placed on the stack will be the first one removed when you go to grab a plate.

That is exactly how the stack data structure operates, allowing operations at only one end of the data structure. Two easy acronyms that describe a stack: LIFO (Last In First Out) and FILO (First In Last Out). When referencing the operations of a stack the insertion operation is called Push and the removal is called Pop.

Now let's look at a problem where the stack data structure can be used to help solve the problem at hand.

Valid Parentheses

Given an input str containing the characters '(', ')', '{', '}', '[', ']', determine if the given string is valid.

Input str is valid if:

• 1. Opening brackets are closed by the same type of bracket '()' => true, '(]' => false
• 2. Opening brackets are closed in the correct order '([])' => true, '([)]' => false

If str is valid return true otherwise return false. For simplicity we are not going to worry about any edge cases in this problem

const isValid = (str) => {
    let map = { ')': '(', '}': '{', ']': '[' };
    let stack = [];

    for (let i = 0; i < str.length; i++) {
        if (str[i] === '(' || str[i] === '{' || str[i] === '[') stack.push(str[i]);
        else if (map[str[i]] === stack[stack.length - 1]) stack.pop();
        else return false;
        console.log(stack);
    };
    return stack.length === 0;
};

isValid("{{}[][[[]]]}");

Output:

[ '{' ]
[ '{', '{' ]
[ '{' ]
[ '{', '[' ]
[ '{' ]
[ '{', '[' ]
[ '{', '[', '[' ]
[ '{', '[', '[', '[' ]
[ '{', '[', '[' ]
[ '{', '[' ]
[ '{' ]
[]
true

In the isValid function above we are using the stack to keep track of the opening brackets in the specific order that we encounter them. When an opening bracket is encountered we push()(add) it onto the stack. When a closing bracket is encountered we check to see if the last opening bracket added to the stack is of the same bracket type as the current closing bracket, if it is we pop()(remove) the opening bracket from the stack. If the last opening bracket added to the stack is not of the same type as the closing bracket we have encountered we return false.

In the resulting output from running our function, you can see that the stack is adhering to the FILO & LIFO principles through each iteration of the for loop.

I hoped this helped you understand the stack data structure better and you feel comfortable implementing it in the future. If you have any questions or any other fun problems where a stack can be utilized drop them in the comments below.

Cheers!