Triển khai Stack trong JavaScript

Posted on by adminChuyên mục:Kiến thức Internet

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 trong JavaScript

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

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.là một. Một ngăn xếp hoạt động giải trí dựa trên nguyên tắc LIFO ( tức là Last-In, First-Out ). LIFO có nghĩa là thành phần được thêm gần đây nhất là thành phần tiên phong bị xóa. Một stack có hai hoạt động giải trí 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

Minh họa thao tác Push và Pop trong 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 thành phần vào mảng với phương pháp 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 .

Minh họa thao tác push() trong 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 thành phần 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 ( ) :

Minh họa thao tác pop() trong Stack

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 tác dụng

    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 vần âm từ ngăn xếp và nối chúng lại với nhau .

Tổng kết về Stack trong JavaScript

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 JAVAKHÓA HỌC PHPTrong 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ệuStack có hai phương pháp chínhvàđể thêm thành phần vào và xóa thành phần ở cuối mảng .

—

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 trong thực tiễn + Tuyển dụng ngay !

Đc : Tầng 3, 25T2, N05, Nguyễn Thị Thập, CG cầu giấy, Thành Phố Hà Nội

SĐT : 02435574074 – 0968051561

E-Mail : [email protected]

Fanpage: https://facebook.com/NIIT.ICT/

# niit # niithanoi niiticthanoi # hoclaptrinh # khoahoclaptrinh # hoclaptrinhjava # hoclaptrinhphp # python # php # java

admin