- vừa được xem lúc

Tập 1: Data Structure - Stack

0 0 24

Người đăng: Tran Dinh Thang

Theo Viblo Asia

Giới thiệu

Stack là một cấu trúc dữ liệu cơ bản và được ứng dụng rộng rãi trong các chương trình máy tính

1. Khái niệm

Stack (ngăn xếp) là một cấu trúc dữ liệu hoạt động theo nguyên lý LIFO (vào sau ra trước)

Một ngăn xếp là như một thùng chứa, nó chứa các dữ liệu bên trong thùng chứa đó

Cơ chế của stack là dữ liệu được đưa vào (push) và khi muốn lấy ra thì sẽ lấy dữ liệu từ mới nhất đến cũ nhất (pop) cho tới khi stack trống

Sau khi đọc khái niệm nếu các bạn còn thấy mơ hồ thì hãy qua phần ví dụ, mình sẽ ví dụ cụ thể hơn về stack

2. Ví dụ

Có nhiều bài viết có lấy ví dụ về chồng đĩa (không biết là đĩa DVD thời xưa hay là đĩa đựng thức ăn nữa)

Nhưng để dễ hình dung hơn khi đang đọc bài viết này, mình sẽ lấy một ví dụ đơn giản ngay trên trình duyệt bạn đang online

Khi bạn truy cập vào trình duyệt, search Google và bạn nhấn vào Kết quả tìm kiếm nào đó (ví dụ là link 1), sau đó bạn lại nhấn vào link 2, link 3,... nghĩa là bạn đã đẩy vào stack theo thứ tự link 1 -> link 2 -> link 3 -> ...

Và khi bạn nhấn nút back ở góc trên bên trái thì bạn sẽ được quay lại theo từng link là link 3 -> link 2 -> link 1

3. Code Example (Using javascript)

Interface: Nhìn tổng quát về các thuộc tính và phương thức của stack

class Stack { #stack; #size; constructor() { this.#stack = []; this.#size = 0; } get stack() {} get size() {} // add value vào stack push(value) {} // remove value ra khỏi stack pop() {} // lấy value mới nhất nhưng không remove nó peek() {} // kiểm tra stack có đang trống không? isEmpty() {}
}

Push method: Đưa một giá trị vào stack

push(value) { this.#stack.push(value); this.#size++;
}

Pop method: Xoá giá trị mới nhất trong stack

pop() { if (this.#size > 0) { this.#stack.pop(); this.#size--; return; } console.log('Stack is empty');
}

Peek method: Lấy giá trị mới nhất nhưng vẫn giữ nguyên stack

peek() { if (this.#size > 0) { return this.#stack[this.#size - 1]; } return 'Stack is empty';
}

isEmpty method: Kiểm tra stack có đang rỗng không?

isEmpty() { return this.#size === 0;
}

Using:

const stack = new Stack(); stack.push(1);
stack.pop();
stack.push(2);
stack.push(3); console.log('Stack', stack.stack);
console.log('size', stack.size);
console.log('isEmpty', stack.isEmpty());
console.log('peek', stack.peek());

Toàn bộ source code:

class Stack { #stack; #size; constructor() { this.#stack = []; this.#size = 0; } get stack() { return this.#stack; } get size() { return this.#size; } push(value) { this.#stack.push(value); this.#size++; } pop() { if (this.#size > 0) { this.#stack.pop(); this.#size--; return; } console.log('Stack is empty'); } peek() { if (this.#size > 0) { return this.#stack[this.#size - 1]; } return 'Stack is empty'; } isEmpty() { return this.#size === 0; }
} const stack = new Stack(); stack.push(1);
stack.pop();
stack.push(2); console.log('Stack', stack.stack);
console.log('size', stack.size);
console.log('isEmpty', stack.isEmpty());
console.log('peek', stack.peek());

4. Tổng kết

Như vậy ở trên mình đã giải thích đơn giản về ngăn xếp. Trong tập tiếp theo của series [Lặn sâu] Cấu trúc dữ liệu, mình sẽ giới thiệu về Queue, một anh em họ hàng cũng gần với Stack. Cảm ơn các bạn đã đọc.

Kham khảo

Bình luận

Bài viết tương tự

- vừa được xem lúc

Giới thiệu Typescript - Sự khác nhau giữa Typescript và Javascript

Typescript là gì. TypeScript là một ngôn ngữ giúp cung cấp quy mô lớn hơn so với JavaScript.

0 0 496

- vừa được xem lúc

Bạn đã biết các tips này khi làm việc với chuỗi trong JavaScript chưa ?

Hi xin chào các bạn, tiếp tục chuỗi chủ đề về cái thằng JavaScript này, hôm nay mình sẽ giới thiệu cho các bạn một số thủ thuật hay ho khi làm việc với chuỗi trong JavaScript có thể bạn đã hoặc chưa từng dùng. Cụ thể như nào thì hãy cùng mình tìm hiểu trong bài viết này nhé (go).

0 0 413

- vừa được xem lúc

Một số phương thức với object trong Javascript

Trong Javascript có hỗ trợ các loại dữ liệu cơ bản là giống với hầu hết những ngôn ngữ lập trình khác. Bài viết này mình sẽ giới thiệu về Object và một số phương thức thường dùng với nó.

0 0 134

- vừa được xem lúc

Tìm hiểu về thư viện axios

Giới thiệu. Axios là gì? Axios là một thư viện HTTP Client dựa trên Promise.

0 0 117

- vừa được xem lúc

Imports và Exports trong JavaScript ES6

. Giới thiệu. ES6 cung cấp cho chúng ta import (nhập), export (xuất) các functions, biến từ module này sang module khác và sử dụng nó trong các file khác.

0 0 93

- vừa được xem lúc

Bài toán đọc số thành chữ (phần 2) - Hoàn chỉnh chương trình dưới 100 dòng code

Tiếp tục bài viết còn dang dở ở phần trước Phân tích bài toán đọc số thành chữ (phần 1) - Phân tích đề và những mảnh ghép đầu tiên. Bạn nào chưa đọc thì có thể xem ở link trên trước nhé.

0 0 228