Typescript Data Structure: Stack

Stacks, those orderly piles of data in your program, deserve a closer look. In TypeScript, these LIFO (Last-in-First-out) structures excel at managing data in a specific order, offering efficient retrieval and removal based on their most recent addition.

Basic Stack Operations

A stack typically supports two fundamental operations:

  1. Push: Adds an element to the top of the stack.
  2. Pop: Removes the element from the top of the stack.

Let's dive into their details with some examples:

Building a Basic Stack

class Stack<T> { private data: T[]; constructor() { this.data = []; } push(element: T): void { this.data.push(element); } pop(): T undefined { return this.data.pop(); } peek(): T undefined { return this.data[this.data.length - 1]; } isEmpty(): boolean { return this.data.length === 0; } } const myStack = new Stack<number>(); myStack.push(10); myStack.push(20); myStack.push(30); console.log(myStack.pop()); // Outputs: 30 console.log(myStack.peek()); // Outputs: 20 console.log(myStack.isEmpty()); // Outputs: false

This example demonstrates a basic stack implementation using an array and class with methods for pushing, popping, peeking, and checking emptiness. We define a generic type T to allow stacking any data type.

Utilizing Stack Operations

class Stack<T> { private data: T[]; constructor() { this.data = []; } push(element: T): void { this.data.push(element); } pop(): T undefined { return this.data.pop(); } isEmpty(): boolean { return this.data.length === 0; } } const undoStack = new Stack<string>(); function editDocument(text: string): string { undoStack.push(text); // Save previous document state // Make some edits to the document const newText = "Edited text"; // Replace with actual edited text return newText; } function undoEdit(): string undefined { if (!undoStack.isEmpty()) { return undoStack.pop(); // Revert to previous state } else { console.log("No edits to undo!"); return undefined; } } const initialText = "This is the initial text."; let currentText = editDocument(initialText); console.log(currentText); // Outputs: "Edited text" currentText = undoEdit(); console.log(currentText); // Outputs: "This is the initial text."

This example showcases a practical use of stacks in an undo/redo functionality. We use a stack to store document states after each edit, enabling users to revert changes by popping elements. This demonstrates the LIFO behavior in action.

Using Generics

class Stack<T> { private data: T[]; constructor() { this.data = []; } push(element: T): void { this.data.push(element); } pop(): T undefined { return this.data.pop(); } isEmpty(): boolean { return this.data.length === 0; } } const equationStack = new Stack<number string>(); function calculate(operand1: number, operand2: number, operator: string): number { switch (operator) { case "+": return operand1 + operand2; case "-": return operand1 - operand2; case "*": return operand1 * operand2; case "/": return operand1 / operand2; default: throw new Error(`Unsupported operator: ${operator}`); } } function evaluateExpression(expression: string): number { // Split expression into operands and operators const elements = expression.split(" "); for (const element of elements) { if (isNaN(Number(element))) { equationStack.push(element); // Operator goes on top } else { const operand1 = Number(equationStack.pop()); const operand2 = Number(equationStack.pop()); const result = calculate(operand1, operand2, element); // Perform operation equationStack.push(result); // Push result back on stack } } return Number(equationStack.pop()); // Final result remains on top } const result = evaluateExpression("2 + 3 * 5"); console.log(result); // Outputs: 17

This example highlights the power of generics. We use a single stack to hold both numbers and operators, thanks to generic typing. The expression evaluation logic utilizes the LIFO nature of the stack to perform calculations efficiently.

Applications of Stacks

Function Call Management

Stacks are used in managing function calls and local variables in recursive algorithms. Each function call adds a new frame to the stack, and when a function completes, its frame is removed.

Undo Mechanism

Stacks can be employed to implement an undo mechanism in applications where users can revert to previous states. Each action that modifies the state is pushed onto the stack, allowing easy reversal.

Expression Evaluation

Stacks are instrumental in evaluating expressions, especially in parsing and interpreting mathematical expressions. The stack helps maintain the order of operations.

Browser History

Stacks are commonly used to track the history of visited pages in web browsers. Each page visit is pushed onto the stack, and when the user navigates back, the last page visited is popped off the stack.

class BrowserHistory { private pageStack: string[] = []; visitPage(page: string): void { this.pageStack.push(page); } goBack(): string undefined { return this.pageStack.pop(); } getCurrentPage(): string undefined { return this.pageStack[this.pageStack.length - 1]; } } // Example usage: const browserHistory = new BrowserHistory(); browserHistory.visitPage("Home"); browserHistory.visitPage("About"); console.log(browserHistory.getCurrentPage()); // Outputs: "About" console.log(browserHistory.goBack()); // Outputs: "About"

Implementing with Different Data Structures

While arrays are common for stacks, other options exist. Linked lists can offer dynamic resizing, while circular buffers provide efficient memory usage for fixed-size stacks. Choosing the right data structure depends on your specific needs and performance considerations.

Beyond Simple LIFO

Stacks can be adapted for more complex tasks. Multiple stacks can be used for balancing parentheses, while queues can be implemented using two stacks (one for enqueueing and one for dequeueing). Remember, creativity and understanding of underlying principles open doors to various stack applications.

Conclusion

Stacks in TypeScript provide a simple and effective way to manage data with a Last-In-First-Out order. They find applications in a wide range of scenarios, including managing function calls, implementing undo mechanisms, evaluating expressions, and tracking browser history. The flexibility of TypeScript's type system enhances the safety and expressiveness of stack implementations.






Related Topics
  1. TypeScript Queues
  2. TypeScript Set
  3. TypeScript Map
  4. TypeScript Linked List
  1. Typescript Tree