Khám phá các và hàng đợi qua JavaScript
Rất thường xuyên, một danh sách liên kết kép được phân tách đầy đủ có thể quá mức cần thiết cho những gì bạn đang cố gắng đạt được. Trong bài viết này, ta sẽ khám phá hai biến thể tối giản cực kỳ phổ biến cho danh sách được liên kết: ngăn xếp và hàng đợi .
Ngăn xếp và hàng đợi là các phương pháp đối lập để xử lý dữ liệu đến, đặc biệt là khi chúng cần được xóa theo một thứ tự cụ thể. Chúng thường ít được coi là cấu trúc dữ liệu và nhiều hơn là kiểu dữ liệu trừu tượng, nghĩa là chúng đại diện cho một cách sử dụng cụ thể hơn là một cấu trúc chính xác. Vì vậy, chúng là một mẫu có thể triển khai theo nhiều cách khác nhau với các cấu trúc dữ liệu khác như mảng, danh sách được liên kết và thậm chí cả cây.
Yêu cầu
Có hiểu biết cơ bản về danh sách được liên kết là điều cần thiết để hiểu các triển khai danh sách, bạn có thể xem tổng quan tại đây .
Mặc dù không cần thiết để hiểu về ngăn xếp và hàng đợi, nhưng bạn đã có thể nắm rõ những điều cơ bản của Ký hiệu Big O, mà tôi đã viết một đoạn giới thiệu ngắn ở đây .
Ngăn xếp
Các ngăn xếp được coi là một cấu trúc LIFO , nghĩa là xếp sau cùng ra trước . Ta thêm các mục vào ngăn xếp của bạn và nếu một số điều kiện khác được đáp ứng, chẳng hạn như bộ đếm thời gian đã hết hoặc một nhiệm vụ đã hoàn thành, thì mục được thêm mới nhất là mục đầu tiên bị xóa và là mục duy nhất mà ta có thể tương tác. Tôi muốn hình dung điều này giống như rửa và làm khô một chồng đĩa, khi bạn thêm vào đầu chồng đĩa, bạn bị hạn chế chỉ làm việc với đĩa trên cùng trước khi bạn có quyền truy cập vào phần còn lại.
Bạn đã sử dụng nhiều ngăn xếp, như ngăn xếp cuộc gọi đệ quy hoặc ngăn xếp cuộc gọi JavaScript tiêu chuẩn khi bạn thực hiện các yêu cầu không đồng bộ. Nhu cầu kiểm soát chặt chẽ thứ tự của các hoạt động theo cách này là cực kỳ phổ biến và thậm chí sẽ giúp ta theo một số cách ít trực quan hơn như duyệt qua cây và xếp hạng kết quả tìm kiếm.
Phiên bản cơ bản nhất của điều này sẽ chỉ là với một mảng đơn giản. Ngăn xếp có triển khai mảng chỉ là O(1) , giống như với danh sách được liên kết vì ta chỉ thao tác phần đuôi và không cần lập index lại. Ta chỉ có thể sử dụng các phương pháp push và pop thông thường để thực hiện việc này. Miễn là ta chỉ sử dụng hai hàm này để tương tác với dữ liệu của bạn , về mặt kỹ thuật, ta sẽ có một ngăn xếp chức năng, ngay cả khi có một chút mờ nhạt.
const stack = [];
const add = val => stack.push(val);
const remove = () => stack.pop();
add('one');
add('two');
add('three');
remove();
console.log(stack); // ["one", "two"]
Danh sách được liên kết phức tạp hơn một chút, ta có các node bình thường chỉ với một con trỏ và một số phương thức add và remove . Nếu không có gì trong danh sách, hãy đặt nó làm đầu và đuôi hoặc null, nếu không, hãy thay đổi con trỏ trên mục trước nó. Không quan trọng nếu ta thêm / bớt trên đầu hay đuôi, miễn là đó là cái duy nhất mà ta đang tương tác.
Phương pháp này sẽ được ưu tiên hơn nếu bạn đã kết nối với một database chứa nhiều nút. Vì các mảng được tải ở một kích thước cố định, nên các danh sách được liên kết sẽ tốt hơn nếu chỉ tải vào các phần dữ liệu cần thiết.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
};
class Stack {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
add(val) {
const newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
const temp = this.head;
this.head = newNode;
this.head.next = temp;
};
this.length++;
return this;
}
remove() {
if (!this.head) return null;
let temp = this.head;
this.head = this.head.next;
this.length--;
return temp.val;
}
};
let stack = new Stack()
stack.add('one')
stack.add('two')
stack.add('three')
stack.remove()
console.log(stack) // two -> one
Hàng đợi
Hàng đợi là sự đảo ngược của các ngăn xếp có cấu trúc FIFO , nghĩa là xuất trước vào trước . Điều này giống hệt như đứng xếp hàng, bạn xuất hiện trước nên bạn phải đi trước.
Tương tự, ta vẫn có thể thực hiện một mảng, nhưng lần này thì khác. Vì ta đang làm việc ngay từ đầu khi ta xóa một thứ gì đó, mỗi lần xóa nghĩa là máy tính của ta cần lặp lại phần còn lại của mảng và lập index lại mọi thứ, cho ta O(n) .
const queue = [];
const add = val => queue.push(val);
const remove = () => queue.shift();
add('one');
add('two');
add('three');
remove();
console.log(queue); // ["two", "three"]
Trong trường hợp này, danh sách được liên kết hầu như luôn vượt trội hơn khi xử lý lượng dữ liệu lớn hơn vì nó tránh được vấn đề lập index lại.
Không quan trọng ta thêm vào đầu nào miễn là ta loại bỏ đầu kia, trong trường hợp này, ta sẽ thêm vào đuôi và loại bỏ đầu.
class Queue {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
enqueue(val) {
const newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
};
this.length++;
return this;
}
dequeue() {
if (!this.head) return null;
if (this.head === this.tail) this.last = null;
let temp = this.head;
this.head = this.head.next;
this.length--;
return temp.val;
}
}
let queue = new Queue();
queue.enqueue('one');
queue.enqueue('two');
queue.enqueue('three');
queue.dequeue();
console.log(queue); // two -> three
Bớt tư tưởng
Điều này có vẻ giống như việc tách các sợi tóc khỏi các danh sách và mảng được liên kết thông thường của ta , nhưng khi ta tiến tới các cấu trúc ngày càng phức tạp, ngăn xếp và hàng đợi sẽ trở thành một thành phần thiết yếu đối với cách ta cấu trúc và truyền dữ liệu.
Các tin liên quan
Khám phá cây qua JavaScript2020-02-23
Giới thiệu về danh sách được liên kết qua JavaScript - Phần 2: Triển khai
2020-02-23
Câu hỏi phỏng vấn JavaScript: Gotchas phổ biến
2020-02-21
Giới thiệu về danh sách được liên kết qua JavaScript - Phần 1: Tổng quan
2020-02-21
Hiểu Radix Sắp xếp Thông qua JavaScript
2020-02-18
Cách xây dựng PWA trong Vanilla JavaScript
2020-02-17
Hiểu về Sắp xếp nhanh qua JavaScript
2020-02-14
Hiểu bản đồ và thiết lập đối tượng trong JavaScript
2020-02-12
Hiểu Hợp nhất Sắp xếp Thông qua JavaScript
2020-02-08
Tạo biểu mẫu tùy chỉnh bằng API dữ liệu biểu mẫu JavaScript
2020-02-06
