Hướng dẫn javascript execution stack - ngăn xếp thực thi javascript

Đã đăng vào thg 5 15, 2019 4:38 CH 2 phút đọc 2 phút đọc

Stack và Queue là hai trong số dạng mà ta có thể bắt gặp ở bất kì cuốn sách nhập môn cấu trúc dữ liệu cơ bản (data structure) . Do cấu trúc của Stack và Queue giống nhau nên thường được đi cùng với nhau, và từ đó cũng có gây nhầm lẫn. Hôm nay mình sẽ hướng dẫn xây dựng một Stack và Queue cơ bản sử dụng JavaScript

Stack

Tổng quan

Stack là một danh sách có thứ tự mà phép chèn và xóa được thực hiện tại đầu cuối của danh sách và người ta gọi đầu cuối này là đỉnh (top) của stack ( cơ chế last-in-first-out hay LIFO)

Bạn có thể coi Stack như là một giá sách. Để lấy cuốn sách thứ nhất thì phải lấy dần dần từ quyển thứ 5 và lần lượt đến hết quyển thứ 2

Lợi ích

Việc thêm và xoá item trong stack cực kì nhanh, cả hai tác vụ có thời gian thực hiện bằng nhau.

Các phương thức

Sẽ 4 phương thức chính:

• pop(): Lấy ra item đỉnh stack
• push(item): Thêm item vào đỉnh stack
• peek(): Trả về giá trị đầu tiên của đỉnh stack
• isEmpty(): Trả về là true nếu stack rỗng

Xây dựng

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

  push(item) {
    return this.stack.push(item);
  }

  pop() {
    return this.stack.pop();
  }

  peek() {
    return this.stack[this.length - 1];
  }

  get length() {
    return this.stack.length;
  }

  isEmpty() {
    return this.length === 0;
  }
}

Ngoài ra chúng ta có thể xây dựng bằng closure:

function Stack() {
  const stack = [];

  return {
    push(item) {
    return stack.push(item);
    },

    pop() {
        return stack.pop();
    },

    peek() {
        return stack[this.length - 1];
    },

    get length() {
        return stack.length;
    },

    isEmpty() {
    return this.length === 0;
    }
  }
}

Ứng dụng

• Đệ quy: Được sử dụng trong các ứng dụng tìm kiếm, N-queen, v.v

• Đảo ngược chuỗi

Queue

Tổng quan

Stack là một danh sách có thứ tự mà phép chèn và xóa được thực hiện tại đầu cuối của danh sách và người ta gọi đầu cuối này là đỉnh (top) của stack ( cơ chế last-in-first-out hay LIFO)

Ứng dụng

• Đệ quy: Được sử dụng trong các ứng dụng tìm kiếm, N-queen, v.v
• Đảo ngược chuỗi

Các phương thức

• Sẽ 4 phương thức chính:
• pop(): Lấy ra item đỉnh stack
• push(item): Thêm item vào đỉnh stack
• peek(): Trả về giá trị đầu tiên của đỉnh stack

Xây dựng

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

  enqueue(item) {
    return this.queue.unshift(item);
  }

  dequeue() {
    return this.queue.pop();
  }

  peek() {
    return this.queue[this.length - 1];
  }

  get length() {
    return this.queue.length;
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

Ngoài ra chúng ta có thể xây dựng bằng closure:

https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

https://dev.to/rinsama77/data-structure-stack-and-queue-4ecd

Ứng dụng