Trong hướng dẫn này, mình sẽ giới thiệu cho bạn cấu trúc dữ liệu Stack trong JavaScript và chỉ cho bạn cách sử dụng một mảng để tạo ra Stack.
Stack là gì nhỉ?
Stack là một cấu trúc dữ liệu chứa một danh sách các phần tử. Một ngăn xếp hoạt động dựa trên nguyên tắc LIFO (tức là Last-In, First-Out).
> Còn Queue thì là kiểu FIFO (First In, First Out)
LIFO có nghĩa là phần tử được thêm gần đây nhất là phần tử đầu tiên bị xóa.
Một stack có hai hoạt động chính chỉ xảy ra ở đầu stack đó là: push và pop.
-
Thao tác push thêm một phần tử vào trên cùng của stack
-
Trong khi thao tác pop sẽ xóa một phần tử khỏi đầu stack
Tên Stack (ngăn xếp) tên bắt nguồn từ sự tương tự với một tập hợp các ngăn xếp vật lý, ví dụ: Các cuốn sách xếp chồng lên nhau.
Một stack có nhiều ứng dụng. Ví dụ, đơn giản nhất là đảo ngược một từ. Để làm điều đó, bạn push một từ vào stack, từng chữ cái và pop các chữ cái từ ngăn xếp.
Các ứng dụng khác của stack là cơ chế Ctrl + Z trong trình soạn thảo văn bản, phân tích cú pháp, gọi hàm và chuyển đổi biểu thức (infix thành postfix, infix thành prefix, postfix thành infix và prefix thành infix).
Quay lại với JavaScript. Kiểu dữ liệu mảng trong JS cung cấp các phương thức push() và pop() cho phép bạn sử dụng một mảng như một stack.
Phương thức push()
Phương thức push() cho phép bạn thêm một hoặc nhiều phần tử vào cuối mảng. Phương thức push() trả về giá trị của thuộc tính length chỉ định số phần tử trong mảng.
Nếu bạn coi một mảng là một Stack, thì phương thức push() sẽ thêm một hoặc nhiều phần tử ở trên cùng của ngăn xếp.
Ví dụ sau tạo một mảng trống có tên là stack và thêm vào đó năm số, lần lượt vào cuối mảng stack. Nó giống như đẩy từng số vào đầu stack.
// Tạo một mảng rỗng và coi nó như một stack
let stack = [];
// Đẩy phần tử vào mảng với phương thức push
stack.push(1);
console.log(stack); // [1]
stack.push(2);
console.log(stack); // [1,2]
stack.push(3);
console.log(stack); // [1,2,3]
stack.push(4);
console.log(stack); // [1,2,3,4]
stack.push(5);
console.log(stack); // [1,2,3,4,5]
Hình sau đây minh họa thao tác push 5 số vào stack.
Ban đầu, stack trống. Sau đó, chúng ta gọi phương thức push() để thêm từng số vào stack. Sau 5 lần gọi, stack có 5 phần tử.
Lưu ý rằng phương thức push() cũng cho phép bạn thêm nhiều mục vào cuối mảng cùng một lúc.
Phương thức pop()
Phương thức pop() loại bỏ phần tử ở cuối mảng và trả lại phần tử cho trình gọi. Nếu mảng trống, phương thức pop() trả về undefined.
Ví dụ sau đây cho thấy cách bật các phần tử từ trên cùng của ngăn xếp bằng phương thức pop().
// Bật phần tử cuối ra khỏi mảng
console.log(stack.pop()); // 5
console.log(stack); // [1,2,3,4];
console.log(stack.pop()); // 4
console.log(stack); // [1,2,3];
console.log(stack.pop()); // 3
console.log(stack); // [1,2];
console.log(stack.pop()); // 2
console.log(stack); // [1];
console.log(stack.pop()); // 1
console.log(stack); // []; -> Mảng trống
console.log(stack.pop()); // undefined
Hình sau đây minh họa thao tác pop():
Ban đầu, stack có 5 phần tử. Phương thức pop() xóa từng phần tử ở cuối mảng, tức là ở đầu ngăn xếp từng phần một. Sau năm lần pop(), stack trống.
Đảo ngược chuỗi bằng cách sử dụng Stack trong JavaScript
Ví dụ sau đây cho bạn thấy cách đảo ngược một chuỗi bằng cách sử dụng Stack trong JS.
function daoNguocChuoi(chuoi) {
let stack = [];
// Đẩy từng ký tự vào stack
for (let i = 0; i < chuoi.length; i++) {
stack.push(chuoi[i]);
}
// Tạo biến chứa kết quả
let chuoiDaDaoNguoc = "";
while (stack.length > 0) {
// Nối từng ký tự bị bật ra khỏi stack
// vào với nhau
chuoiDaDaoNguoc += stack.pop();
}
return chuoiDaDaoNguoc;
}
// Thử đảo ngược chuỗi
console.log(daoNguocChuoi("NIIT ICT Ha noi")); // ion aH TCI TIIN
Cách thức hoạt động chương trình đảo ngược chuỗi trên:
Hàm daoNguocChuoi() chấp nhận một đối số chuoi và trả về phiên bản đã đảo ngược của nó với logic sau:
-
Đầu tiên, lặp qua
chuoi và push từng chữ cái vào mảng stack.
-
Thứ hai, pop từng chữ cái từ ngăn xếp và nối chúng lại với nhau.
Tổng kết về Stack trong JavaScript
Trong hướng dẫn này, mình tôi đã chỉ cho bạn cách sử dụng mảng làm cấu trúc dữ liệu Stack trong JavaScript.
Stack có hai phương thức chính push() và pop() để thêm phần tử vào và xóa phần tử ở cuối mảng.
> Bạn đang tìm hiểu về lập trình? tham khảo ngay KHÓA HỌC JAVA hoặc KHÓA HỌC PHP (Full stack) để học theo lộ trình bài bản hơn.
---
HỌC VIỆN ĐÀO TẠO CNTT NIIT - ICT HÀ NỘI
Học Lập trình chất lượng cao (Since 2002). Học thực tế + Tuyển dụng ngay!
Đc: Tầng 3, 25T2, N05, Nguyễn Thị Thập, Cầu Giấy, Hà Nội
SĐT: 02435574074 - 0968051561
Email: hello@niithanoi.edu.vn
Fanpage: https://facebook.com/NIIT.ICT/
#niit #niithanoi niiticthanoi #hoclaptrinh #khoahoclaptrinh #hoclaptrinhjava #hoclaptrinhphp #python #php #java