Greetings! Today, we're delving into the concept of Stacks, a fundamental data structure in computer science. A stack operates similarly to a stack of plates: you add a plate to the top (Last In) and remove it from the top (First Out). This Last-In, First-Out (LIFO) principle is the core characteristic of a stack. In TypeScript, we can implement stacks using arrays due to their ease and efficiency. This lesson will illuminate the stack data structure, its operations, and their applications in TypeScript. Are you ready to start?

To create a stack, TypeScript uses arrays. For the push operation, we use the push() method to add an element to the end of the array. For the pop operation, there is the pop() function that removes the last element, mimicking the removal of the "top" element in a stack. Here's how it looks:

TypeScript
Copy to clipboard
1class StackExample {
2    private stack: string[] = []; // A new empty stack
3
4    // Push operations
5    push(element: string) {
6        this.stack.push(element);
7    }
8
9    // Pop operation
10    pop() {
11        return this.stack.pop();
12    }
13
14    display() {
15        console.log(this.stack);
16    }
17}
18
19let example = new StackExample();
20example.push("John");
21example.push("Mary");
22example.push("Steve");
23
24example.pop(); // Pop operation removes 'Steve'
25example.display(); // Outputs: ['John', 'Mary']

In the example provided, we push "John," "Mary," and "Steve" into the stack and then pop "Steve" from the stack.

Stack operations go beyond merely push and pop. For instance, to verify if a stack is empty, we can use the length property of the array. If it returns 0, the stack is empty. Conversely, if it returns a number greater than 0, the stack is not empty. To peek at the top element of the stack without popping it, we use the index this.stack[this.stack.length - 1].

Here's an example:

TypeScript
Copy to clipboard
1class StackOperations {
2    private stack: string[] = [];
3
4    push(element: string) {
5        this.stack.push(element);
6    }
7
8    pop() {
9        return this.stack.pop();
10    }
11
12    peek() {
13        return this.stack[this.stack.length - 1];
14    }
15
16    isEmpty() {
17        return this.stack.length === 0;
18    }
19
20    display() {
21        console.log(this.stack);
22    }
23}
24
25let stackOps = new StackOperations();
26stackOps.push("Steve");
27stackOps.push("Sam");
28
29console.log(stackOps.peek()); // Outputs: 'Sam'
30
31console.log(stackOps.isEmpty()); // Outputs: false
32stackOps.pop(); // Remove 'Sam'
33stackOps.pop(); // Remove 'Steve'
34console.log(stackOps.isEmpty()); // Outputs: true

In this example, "Sam" is added (pushed), and then the topmost stack element, which is "Sam," is peeked at.

The isEmpty() method checks if there are any elements in the stack. This is useful in situations where we need to avoid errors caused by attempting to pop or peek an empty stack.

The peek() method allows us to view the topmost element without removing it. This is especially useful in algorithms that need to check or use the top element multiple times before deciding whether to remove it.

Practical applications of stacks are plentiful. Here, we will explore one — reversing a string.

We will push all characters into a stack and then pop them out to obtain a reversed string!

TypeScript
Copy to clipboard
1class ReverseString {
2    static reverseString(input: string): string {
3        let stack: string[] = [];
4
5        for (let c of input) {
6            stack.push(c);
7        }
8
9        let reversedString = '';
10        while (stack.length > 0) {
11            reversedString += stack.pop();
12        }
13
14        return reversedString;
15    }
16}
17
18console.log(ReverseString.reverseString("HELLO")); // Outputs: OLLEH

A stack can be used to verify if parentheses in an expression are well-matched; i.e., every bracket has a corresponding pair. For example, parentheses in the string "()[{}]" are well-matched, while in strings "([]()", ")()[]{}", "([)]", and "[{})" they are not.

Here's the TypeScript implementation:

TypeScript
Copy to clipboard
1class ParenthesesBalance {
2
3    static isParenBalanced(parenString: string): boolean {
4        const stack: string[] = [];
5        const openingParen: { [key: string]: string } = { ')': '(', ']': '[', '}': '{' };
6
7        for (let paren of parenString) {
8            if (Object.values(openingParen).includes(paren)) {
9                // Met an opening parenthesis, just push to stack
10                stack.push(paren);
11            } else if (Object.keys(openingParen).includes(paren)) {
12                // Met a closing parenthesis
13                if (stack.length === 0 || stack.pop() !== openingParen[paren]) {
14                    return false;
15                }
16            }
17        }
18
19        return stack.length === 0;
20    }
21}
22
23console.log(ParenthesesBalance.isParenBalanced("(())")); // Outputs: true
24console.log(ParenthesesBalance.isParenBalanced("({[)}")); // Outputs: false

Here the openingParen is defined as an object with closing parentheses (), ], }) as keys and their corresponding opening counterparts ((, [, {) as values. The method iterates over each character (paren) in the input parenString.

If the character is an opening parenthesis ((, [, or {), it is pushed onto the stack. If the character is a closing parenthesis (), ], or }), the method checks:

• If the stack is empty, it returns false (because there is no corresponding opening parenthesis).
• Otherwise, it pops the top of the stack and compares it with openingParen[paren] to ensure it matches the expected opening parenthesis. If it doesn’t match, the method returns false.

Great job! We have explored the stack data structure, its operations, and their applications in TypeScript. The next step is to engage with practice exercises that will consolidate your newfound knowledge. Dive into them and master stacks in TypeScript!