Exploring Stacks and Queues in TypeScript

Introduction: Stacks and Queues

Welcome to an exciting exploration of two fundamental data structures: Stacks and Queues! Remember, data structures store and organize data in a manner that is structured and efficient. Stacks and Queues are akin to stacking plates and standing in a line, respectively. Intriguing, isn't it? Let's dive in!

Stacks: Last In, First Out (LIFO)

A Stack adheres to the "Last In, First Out" or LIFO principle. It's like a pile of plates where the last plate added is the first one to be removed. TypeScript uses arrays to create a stack, leveraging the push() method to add an element to the end of the array and the pop() method to remove the last element. These methods help implement the LIFO behavior, with type safety enforced through type annotations. Let's explore this using a pile of plates. TypeScript class StackOfPlates {private stack: string[]; constructor() {this.stack = [];} // Inserts a plate at the top of the stack push(plate: string): void {this.stack.push(plate);} // Removes the top plate from the stack pop(): string {if (this.stack.length === 0) {return "No plates left to remove!";} return this.stack.pop()!;}} // Create a stack of plates const plates = new StackOfPlates(); plates.push('Plate'); // Pushing a plate plates.push('Another Plate'); // Pushing another plate // Let's remove a plate; it should be the last one we added. console.log('Removed:', plates.pop()); // Outputs: Removed: Another Plate The last plate added was removed first, demonstrating the LIFO property of a stack.

Queues: First In, First Out (FIFO)

A Queue represents the "First In, First Out" or FIFO principle, similar to waiting in line at the grocery store where the first person to arrive is the first to be served. In TypeScript, we can use arrays to achieve this behavior, using enqueue() for enqueueing (insertion at the end) and dequeue() for dequeueing (removal from the front). Let's examine this through a queue of people. TypeScript class QueueOfPeople {private queue: string[]; constructor() {this.queue = [];} // Add a person to the end of the queue enqueue(person: string): void {this.queue.push(person);} // Remove the first person from the queue (who has been waiting the longest) dequeue(): string {if (this.queue.length === 0) {return "No people left to dequeue!";} return this.queue.shift()!;}} // Create a queue of people const people = new QueueOfPeople(); people.enqueue('Person 1'); // Person 1 enters the queue people.enqueue('Person 2'); // Person 2 arrives after Person 1 // Who's next in line? It must be Person 1! console.log('Removed:', people.dequeue()); // Outputs: Removed: Person 1 Here, Person 1, the first to join the queue, left before Person 2, demonstrating the FIFO property of a queue.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Mastering Stack and Queue Operations With a Class

Let's illustrate these two structures within a text editor that incorporates an Undo mechanism, represented by a Stack, and a Print Queue, exemplified by a Queue.

TypeScript

class TextEditor {
  private stack: string[];
  private queue: string[];

  constructor() {
    this.stack = [];
    this.queue = [];
  }

  // Make a change (e.g., edit text, insert image, change font)
  makeChange(action: string): void {
    this.stack.push(action); // Add to the stack of actions
  }

  // Undo the most recent change
  undoChange(): string {
    if (this.stack.length === 0) {
      return "No changes to undo!";
    }
    return this.stack.pop()!;
  }

  // Add a document to the queue for printing
  addToPrint(doc: string): void {
    this.queue.push(doc);
  }

  // Print the document that has been waiting the longest
  printDoc(): string {
    if (this.queue.length === 0) {
      return "No documents in print queue!";
    }
    return this.queue.shift()!;
  }
}

// Use our text editor!
const editor = new TextEditor();
editor.makeChange("Changed font size"); // Make a change
editor.makeChange("Inserted image"); // Make another change
// Let's undo a change. It should be the last change we made.
console.log('Undo:', editor.undoChange());  // Undo: Inserted image

editor.addToPrint("Proposal.docx"); // Queue a document for printing
editor.addToPrint("Report.xlsx"); // Queue another document
// Let's print a document. It should be the document that has been waiting the longest.
console.log('Print:', editor.printDoc());  // Print: Proposal.docx

class TextEditor {
  private stack: string[];
  private queue: string[];

  constructor() {
    this.stack = [];
    this.queue = [];
  }

  // Make a change (e.g., edit text, insert image, change font)
  makeChange(action: string): void {
    this.stack.push(action); // Add to the stack of actions
  }

  // Undo the most recent change
  undoChange(): string {
    if (this.stack.length === 0) {
      return "No changes to undo!";
    }
    return this.stack.pop()!;
  }

  // Add a document to the queue for printing
  addToPrint(doc: string): void {
    this.queue.push(doc);
  }

  // Print the document that has been waiting the longest
  printDoc(): string {
    if (this.queue.length === 0) {
      return "No documents in print queue!";
    }
    return this.queue.shift()!;
  }
}

// Use our text editor!
const editor = new TextEditor();
editor.makeChange("Changed font size"); // Make a change
editor.makeChange("Inserted image"); // Make another change
// Let's undo a change. It should be the last change we made.
console.log('Undo:', editor.undoChange());  // Undo: Inserted image

editor.addToPrint("Proposal.docx"); // Queue a document for printing
editor.addToPrint("Report.xlsx"); // Queue another document
// Let's print a document. It should be the document that has been waiting the longest.
console.log('Print:', editor.printDoc());  // Print: Proposal.docx

This code reintroduces the concepts of a Stack (Undo feature) and Queue (Print queue) in the context of a real-life scenario.

Introduction: Stacks and Queues

Stacks: Last In, First Out (LIFO)

Queues: First In, First Out (FIFO)

Join the 1M+ learners on CodeSignal

Stacks and Queues: When and Where to Use?

Mastering Stack and Queue Operations With a Class

Lesson Summary