Hello, eager learners! In today's lesson, we're exploring stacks, a crucial data structure in programming. We aim to understand stacks, implement and manipulate stacks in TypeScript, and analyze their complexities. Stacks are used in various real-world applications, such as undo operations in text editors. Let's dive right in!

First and foremost, let's understand what a stack is. Imagine a stack of plates that you can only remove from the top. This concept exemplifies stacks, which follow a Last-In, First-Out (LIFO) structure. In a LIFO stack, the last item added is the first removed. For example, adding numbers 1, 2, and 3 in sequence will yield removal in the order: 3, 2, 1. Let's see an implementation in TypeScript, where we'll push (add), pop (remove), and peek (view the top) elements.

TypeScript
Copy to clipboard
1class Stack<T> {
2  private items: T[]; // Type-annotated array
3
4  constructor() {
5    this.items = []; // Empty Stack
6  }
7
8  isEmpty(): boolean {
9    return this.items.length == 0; // Check if stack is empty
10  }
11}

We start by introducing the Stack class that stores an array of items that are of a specific type. Utilizing a generic type <T> makes the stack versatile, allowing it to handle any data type, such as numbers, strings, or custom objects.

In TypeScript, arrays can work as stacks. They have the necessary built-in methods. However, let's implement each operation ourselves to understand this data structure better.

Let's look at how our operations look implemented in code:

TypeScript
Copy to clipboard
1push(element: T): void {
2  this.items.push(element);
3}
4
5pop(): T | string {
6  return this.items.length == 0 ? "Underflow" : this.items.pop();
7}
8
9peek(): T | string {
10  return this.items.length == 0 ? "Stack is empty" : this.items[this.items.length - 1];
11}

• The push method adds a new element to the top of the stack. It utilizes the built-in push method of arrays to add the element to the end of the items array, representing the top of the stack.

• The pop method removes the topmost element from the stack. It first checks if the stack is empty and returns "Underflow" if it is, indicating that there are no elements to remove. Otherwise, it removes and returns the top element of the stack. It returns the type union T | string for valid data or errors (in our implementation, the "Underflow" string).

• The peek method allows us to view the topmost element without removing it from the stack. It returns the element at the last index of the items array, representing the top of the stack, or "Stack is empty" if the stack is empty.

The push, pop, and peek methods take constant time - $O(1)$. This is because these operations are performed at the end of the array. The space complexity is proportional to the number of elements - $O(n)$, where n is the quantity of stack elements.

Here is a complete stack implementation with a usage example:

TypeScript
Copy to clipboard
1class Stack<T> {
2  private items: T[];
3
4  constructor() {
5    this.items = []; // Empty stack
6  }
7
8  push(element: T): void {
9    this.items.push(element);
10  } // Add element
11
12  pop(): T | string {
13    return this.items.length == 0 ? "Underflow" : this.items.pop();
14  } // Remove element
15
16  peek(): T | string {
17    return this.items.length == 0 ? "Stack is empty" : this.items[this.items.length - 1];
18  } // Check top element
19}
20
21let stack = new Stack<number>();
22stack.push(1);
23stack.push(2);
24stack.push(3);
25console.log(stack.pop()); // 3
26console.log(stack.peek()); // 2

Well done! You've completed your journey through stacks in TypeScript, mastering their concept, implementation, operations, and complexity analysis. Exercise sessions await you to further strengthen your TypeScript skills. So, let's set sail for some exciting hands-on practice!