Stacks

Giới thiệu

Là cấu trúc dữ liệu LIFO (Last In First Out).

Stacks được dùng để xử lý lời gọi hàm (call stack), chức năng undo/redo, cho routing, …

Khởi tạo

Tạo stack từ linked list

class NodeLinkedList {
  value: string;
  next: NodeLinkedList | null;
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  top: NodeLinkedList | null;
  size: number;
}

Khởi tạo các method

push

  push(val) {
    const newNode = new NodeLinkedList(val);

    if (!this.top) {
      this.top = newNode;
    } else {
      newNode.next = this.top;
      this.top = newNode;
    }

    this.size++;
    return this;
  }

pop

  pop() {
    if (!this.top) return null;

    const poppedValue = this.top.value;
    this.top = this.top.next;

    this.size--;

    return poppedValue;
  }

Độ phức tạp

Queues

Là kiểu dữ liệu FIFO (Fist In First Out)

Khởi tạo

Khởi tạo từ linked list

class NodeLinkedListQueue {
  value: string;
  next: NodeLinkedListQueue | null;

  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  rear: NodeLinkedListQueue | null;
  front: NodeLinkedListQueue | null;
  size: number;

  constructor() {
    this.rear = null;
    this.front = null;
    this.size = 0;
  }

  enqueue(val) {}

  dequeue() {}
}

Khởi tạo các method

enqueue

  enqueue(val) {
    const newNode = new NodeLinkedListQueue(val);

    if (!this.rear) {
      this.rear = newNode;
      this.front = newNode;
    } else {
      this.front.next = newNode;
      this.front = newNode;
    }

    this.size++;
    return this;
  }

dequeue

  dequeue() {
    if (!this.front) return null;

    const dequeueValue = this.rear.value;

    this.rear = this.rear.next;

    return dequeueValue;
  }

Độ phức tạp