Đã đă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:
//en.wikipedia.org/wiki/Stack_[abstract_data_type]
//en.wikipedia.org/wiki/Queue_[abstract_data_type]
//dev.to/rinsama77/data-structure-stack-and-queue-4ecd
Ứng dụng