Stack Data Structure in Typescript

In this article I will implement a stack in typescript and will display data saved in stack using Angular. Later on we will use this stack to solve the problem where we need to check if a string of parenthesis is balanced.

Stack is a LIFO (Last In First Out) data structure. Let’s think of a stack of books. Adding a new book will place that on top of the stack and removing books will be from the top of the stack. So in order to take a specific book, we have to remove all the elements on top of it.

Stack Terminology and Operations

1. push: Add a new element on top of the stack.
2. pop : Remove the last added element.
3. peek: Retrieve the top element without removing it.
4. size: Total number of elements in the stack.
5. isEmpty: Checks if the stack has no elements.

By default typescript has a built-in Stack, but for this article I will create everything from scratch. The idea behind stack is that all the operations should be executed in constant time: O(1) complexity.

To implement a Stack in Typescript, we are going to create a new generic class named Stack and all the operations that we mentioned above.

export class Stack<T> { 
    private _data: T[] = []; 
    push(value: T): void {} 
    pop(): T {} 
    peek(): T {} 
    size(): number {} 
 
    isEmpty(): boolean {} 
}

You can find the stack implementation here: https://stackblitz.com/edit/angular-ivy-bmbned?file=src/app/stack-visualization/stack.ts. I have also included a simple UI that allows you to push and pop dynamically generated values in the stack. Also the stack display the peek value of the stack or a message if the stack is empty as below:

Custom stack implementation

We mentioned before that all the stack operations complexity is constant and Typescript offers a built-in stack implementation. The question that might arise is when do we need to implement a custom stack. Let’s say you have to keep track of the maximum value at every moment in the stack. If after each operation of push and pop we have to display the maximum value and we check all the values to get the maximum, the time complexity of our stack will be O(n). An efficient solution is to keep a maxStack and after each push we will do a comparison between the peek value of maxStack and the new value and after each pop we will just pop the value from both stacks. At every moment the maximum value in our stack can be accessed by using peek in maxStack.

Stack can be implemented using either a Linked List, an Array or Dynamic Array. For this case I chose the dynamic array implementation. All the implementations have their advantages and disadvantages. Using a linked list to implement the stack will add on overhead because we will need to keep track of the next node, but on the other hand we will not block the memory for a stack that might not need all that. If we chose to implement the stack with a fixed size array we risk allocating more/less memory than the stack needs because we might not be aware beforehand how many elements the stack will keep. Dynamic Arrays is an elegant solution, because it will check if the array is almost full and will increase the space dynamically and this cost will be amortized.

Balanced Parenthesis Solution

Let’s suppose we have a string of parenthesis and we need to check if the string is balanced. Balance means that there is a matching closing parenthesis for every opening parenthesis and they are in order.

{[]} -> String is balanced because in the exact order for each opening parenthesis is a closing one.

{{]} -> String is not balanced because the second { is not closed correctly.

In order to solve this problem, we first need to understand it and why stack is the data structure that provides us with the optimal solution.

For each opening parenthesis we need to have a closing one is the exact order in order for the string to be balanced. Basically we need to keep track of all the opening parenthesis: {([ and when we encounter a closing parenthesis })] we need to check if that is matching with the last opening parenthesis.

This solution definition makes it clear that everytime we have a closing parenthesis we need to access the peek parenthesis in our stack and check if it is matching.

The solution we will provide will perform the following checks:

1. If it is an open parenthesis push that in the stack.
2. If it is a closing parenthesis we perform the following checks:
3. If the stack is empty we return false because it does not find the opening parenthesis.
4. If the open parenthesis we found in stack does not match the closing parenthesis we return false because the string is not balanced.
5. Otherwise if opening and closing parenthesis match, we pop the last parenthesis.
6. In the end we return true only if the stack is empty because the string was balanced: for each opening parenthesis we found a closing one successfully.

In the https://stackblitz.com/edit/angular-ivy-bmbned?file=src/app/stack-visualization/stack-visualization.component.ts you can see the code and check the implementation, otherwise if you want to access only the application you could go here: https://angular-ivy-bmbned.stackblitz.io.

Conclusions

To sum up, we created a new stack using Typescript and then visualized the operations using Angular. After a detailed explanation we could put in practise the knowledge we gained from stack to solve the balanced parenthesis problem.

Originally published at http://agdev.tech on March 2, 2021.