Stack — JS: Arrays

• Stack
• Semantics

Algorithms are important, but programs don't live on algorithms alone. It's important not only to be able to make a correct problem-solving algorithm but also to use the right structure to work with the data.

A data structure is a specific way of storing and organizing data. Depending on the tasks to be performed, different data structures may be the most convenient. You already know the array data structure quite well. In terms of organization, an array is a set of elements that can be accessed by index, but in terms of physical storage in memory, it's more complicated. Arrays can vary, and are also implemented differently in different languages.

In addition to arrays, there are many other data structures, such as lists, hash tables, trees, graphs, stacks, queues, and others. Using a data structure suitable for the task at hand allows you to drastically simplify your code, eliminating confusing logic.

Some of these data structures we'll cover in courses and projects, others you will need to learn by yourself by reading books. In any case, algorithms and data structures (without any exaggeration) form the basis on which everything else in development is strung.

It's best to separate it into three concepts:

• Data structure
• Specific data type (or just “data type”)
• Abstract Data Type (ADT)

Data structures should already be clear, we've already given a definition. Data type is also simple. For example, numbers in JavaScript are a data type. The concept of “data type” is always tied to a specific language and can be absolutely anything, depending on the preferences of the language developers. In other words, if JavaScript developers had decided that numbers should be called strings, no one would have prevented them from doing so, despite the absurdity of calling numbers that.

But abstract data types are a theoretical concept. An ADT entirely determined by the set of operations that can be performed on it. ADTs are abstract because it says nothing about the method of storage and exists only on paper and in heads. But in specific languages, there are specific types that implement ADTs.

ADTs are often confused with the concept of a data structure, moreover, often, data structures and ADTs have the same name. There's no need to dive into these mazes, it's enough to have a general idea.

In this lesson, we'll take a look at one of the simplest and most important abstract data types – the stack.

Stack

A stack is an ordered collection of elements in which data is added and removed from the same place. It's usually called the top of the stack.

There are, of course, real-life equivalents. For example, a shotgun magazine. Cartridges are only added one after another. They're also only removed in the opposite order. The last cartridge inserted will come out of the magazine first.

Virtually any real-world example like this can be looked at like a stack. When not using brute force, we work with stacks in two ways. You can either put a new item (such as a book) on top of the stack or remove an item from the top. That's why stacks are also called "Last In First Out" (LIFO).

Before parsing a particular problem, let's look at the role that stacks play in programming. Think about how programs are executed. Some functions call others, which in turn call others, and so on. After execution goes into the deepest function, it returns a value, and the process begins in reverse. First, it comes out of the deepest functions, then those at higher and higher levels, and so on until it reaches the outermost function. A function call is nothing more than adding an element to the stack, and a return is taking an element out of the stack. That's how things work at hardware level. In addition, if an error occurs during the execution of a program, its output is often called Stack Trace.

Another example related to programming is the "back" button in the browser. Site history is a stack, each time you click on a link, it's added to the history, and the "back" button retrieves the last item from the stack.

Working with the stack includes the following operations:

• Add to stack (push)
• Take from the stack (pop)
• Retrieve an item from the top of the stack without deleting it (peekBack)
• Check if the stack is empty (isEmpty)
• Return the size (size)

The first two are basic, the others will still be needed from time to time. In JavaScript, you can create a stack based on arrays. The push() and pop() methods and the length property are used for this purpose.

const stack = [];

stack.push(3);
console.log(stack); // => [ 3 ]
stack.push('Winterfall');
console.log(stack); // => [ 3, 'Winterfall' ]
stack.push(true);
console.log(stack); // => [ 3, 'Winterfall', true ]

const element1 = stack.pop();
console.log(element1); // => true
console.log(stack); // => [ 3, 'Winterfall' ]

const element2 = stack.pop();
console.log(element2); // => Winterfall
console.log(stack); // => [ 3 ]

Note that the pop() and push() methods modify the original array, and not only does pop modify it, but it also returns the element taken off the stack.

Let's look at a problem whose solution is trivial when using a stack. It's also something that gets asked at job interviews to make sure you know basic data structures.

Task:

You need to implement a function that checks that paired parentheses are balanced. I.e., each opening parenthesis has a closing parenthesis: (), ((()())). Here's an example of unbalanced parentheses: (, ((), )(. You need to do more than just check the number when seeing if they're balanced, it's also important to check the order they go in.

This problem has a simple solution without using a stack, but the stack is also good (and even clearer)

The solution with a stack looks like this:

1. If we have an opening parenthesis in front of us, we put it in the stack
2. If it's a closing parenthesis, we pull an element from the stack (obviously, the last one added) and see that it's an opening one to go with the closing one we have. If the check fails, then the expression does not match the required format.
3. If we get to the end of the line and the stack is empty, then everything is correct. If there are elements left in the stack, then the check has failed. This can happen if there were opening elements at the beginning of the line, but no closing elements at the end.

Let's break it down line by line:

const checkIsBalanced = (expression) => {
  // Initializing the stack
  const stack = [];
  // Pass through each character in the string
  for (const symbol of expression) {
    // See if it's opening or closing
    if (symbol === '(') {
      stack.push(symbol);
    } else if (symbol === ')') {
      // If there is no opening parenthesis for the closing one, then there's no balance
      if (!stack.pop()) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

export default checkIsBalanced;

Suppose the following string is input in the function: ((). Below is a description of the key steps when performing the check function:

1. The first parenthesis ( is put on the stack because it's an opening parenthesis
2. The next parenthesis ( is also put in the stack for the same reason
3. The last ) is a closing parenthesis, the last parenthesis added is retrieved from the stack
4. There is one element left in the stack, so there is no balance

Semantics

It can be tempting to use these functions in everyday practice. For example, to extract the last element of an array. Although the pop() method does allow you to do this, it's very much not preferred for several reasons:

1. It may change the array. Even if the array is not used later, such code introduces potential problems and may require it to be rewritten in the future.

2. Semantics may be broken. Tools must be used as intended; otherwise you'll end up with code that declares one thing, but in reality does something else. Any experienced programmer who sees pop() will immediately assume that the array in this part of the program is being used as a stack. If not, it'll take extra mental effort to understand what is going on.

To retrieve the last element, it's better to use the last() method from the lodash library.

import _ from 'lodash';

const items = ['first', 'second', 'third'];
_.last(items); // 'third'

Recommended materials

1. push method
2. pop method