Hi guys, hôm nay phaken.com chia sẻ cho các bạn bộ câu hỏi phỏng vấn cấu trúc dữ liệu & giải thuật. Đây là bộ câu hỏi với tỷ lệ gặp khá cao 70%, không những vậy nó còn là kiến thức cơ bản để các bạn có thể ứng dụng trong công việc và học tập. Mời mọi người cùng tham khảo nhé! Còn về code thì trong bài này mình dùng javascript cho tiện nhé!

Tìm phần tử ở giữa Linked List sau 1 lần duyệt

Để tìm phần tử ở giữa của một danh sách liên kết (Linked List) chỉ sau một lần duyệt, bạn có thể sử dụng phương pháp “Pointer chạy nhanh và chạy chậm” (Fast and Slow Pointer method). Ý tưởng là bạn sẽ có hai con trỏ: một con trỏ chạy nhanh (fast pointer) di chuyển 2 nút/lần và một con trỏ chạy chậm (slow pointer) di chuyển 1 nút/lần. Khi con trỏ nhanh đến cuối danh sách, con trỏ chậm sẽ ở giữa danh sách. Dưới đây là cách thực hiện:

1. Khởi tạo hai con trỏ, slow và fast, cùng trỏ đến đầu danh sách liên kết.
2. Trong mỗi bước lặp, di chuyển slow 1 nút và fast 2 nút.
3. Khi fast đến cuối danh sách (nghĩa là fast là NULL hoặc fast.next là NULL), slow sẽ ở vị trí giữa của danh sách.

Dưới đây là một ví dụ về mã giả (pseudocode) thực hiện phương pháp này:

function findMiddle(head) {
if (head == null) {
return null; // Danh sách rỗng không có phần tử giữa
}
slow = head;
fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // Di chuyển slow 1 bước
fast = fast.next.next; // Di chuyển fast 2 bước
}
// Khi vòng lặp kết thúc, slow sẽ ở vị trí giữa của danh sách
return slow;
}

Lưu ý: Trong trường hợp danh sách có số lượng phần tử chẵn, có hai phần tử có thể được coi là “ở giữa”. Phương pháp trên sẽ trả về phần tử đầu tiên trong hai phần tử giữa đó.

Bạn có thể đọc thêm kiến thứ LinkList ở đây!

LinkList javascript:

Làm thế nào đế xác định một danh sách liên kết vòng?

Để xác định một danh sách liên kết có chứa vòng hay không, bạn cũng có thể sử dụng thuật toán “Tortoise and Hare” (Rùa và Thỏ), giống như khi tìm phần tử giữa. Trong trường hợp này, thuật toán hoạt động dựa trên nguyên tắc sau: nếu có một vòng trong danh sách, thì con trỏ “Thỏ” (di chuyển nhanh gấp đôi so với “Rùa”) cuối cùng sẽ gặp lại “Rùa” ở một điểm nào đó trong vòng.

Dưới đây là cách thực hiện thuật toán này bằng JavaScript:

class ListNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next; // Di chuyển slow 1 bước
fast = fast.next.next; // Di chuyển fast 2 bước
// Nếu slow và fast gặp nhau, có nghĩa là danh sách có vòng
if (slow === fast) {
return true;
}
}
// Nếu fast chạy đến cuối danh sách mà không gặp slow, danh sách không có vòng
return false;
}
// Ví dụ sử dụng
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = head.next; // Tạo một vòng
console.log(hasCycle(head)); // In ra true, vì danh sách có vòng

Trong ví dụ trên, một danh sách liên kết được tạo với một vòng: nút cuối cùng liên kết trở lại nút thứ hai, tạo thành một vòng. Hàm hasCycle sẽ trả về true khi phát hiện vòng và false nếu không có vòng trong danh sách liên kết.

Xác định giá trị 2 phần tử trùng nhau trong một mảng các số nguyên (từ 1-100)

Để xác định giá trị của 2 phần tử trùng nhau trong một mảng các số nguyên từ 1 đến 100, bạn có thể sử dụng một số phương pháp khác nhau. Một trong những cách đơn giản và hiệu quả là sử dụng một bảng hash (trong JavaScript, đó có thể là một đối tượng hoặc một Set) để theo dõi các số đã xuất hiện trong mảng. Khi gặp một số đã tồn tại trong bảng hash, bạn đã tìm thấy số trùng lặp.

Dưới đây là cách thực hiện bằng JavaScript:

function findDuplicate(nums) {
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) {
return num; // Số này đã xuất hiện trước đó, do đó nó là giá trị trùng lặp
}
seen.add(num);
}
return null; // Không tìm thấy số trùng lặp
}
// Ví dụ sử dụng
const nums = [1, 3, 4, 2, 5, 3]; // Mảng số nguyên với 3 là số trùng lặp
console.log(findDuplicate(nums)); // In ra 3

Phương pháp này có độ phức tạp về thời gian là O(n) và độ phức tạp về không gian là O(n), với n là số lượng phần tử trong mảng. Điều này là do bạn cần duyệt qua mỗi phần tử một lần và lưu trữ các phần tử đã thấy trong một cấu trúc dữ liệu bổ sung.

Nếu mảng chỉ chứa các số nguyên từ 1 đến 100 và chỉ có một giá trị trùng lặp, bạn cũng có thể sử dụng một phương pháp toán học bằng cách tính tổng của tất cả các số từ 1 đến 100 và so sánh nó với tổng thực tế của mảng. Sự chênh lệch giữa hai tổng này sẽ là giá trị trùng lặp. Tuy nhiên, phương pháp này chỉ hiệu quả khi chỉ có một giá trị trùng lặp.

Đảo một xâu ký tự?

Để đảo một xâu ký tự trong JavaScript, bạn có thể sử dụng một số phương pháp khác nhau. Một trong những cách đơn giản nhất là sử dụng các phương thức chuỗi và mảng có sẵn như split, reverse, và join. Dưới đây là cách thực hiện:

function reverseString(s) {
// Chuyển đổi xâu ký tự thành mảng, đảo mảng, và sau đó nối lại thành xâu ký tự
return s.split('').reverse().join('');
}
// Ví dụ sử dụng
const originalString = "Hello, World!";
const reversedString = reverseString(originalString);
console.log(reversedString); // "!dlroW ,olleH"

Trong đoạn mã trên, hàm reverseString nhận vào một xâu ký tự s, sau đó:

• Sử dụng split('') để chuyển đổi xâu ký tự thành một mảng của các ký tự.
• Sử dụng reverse() để đảo ngược thứ tự của các ký tự trong mảng.
• Cuối cùng, sử dụng join('') để nối các ký tự trong mảng đảo ngược lại thành một xâu ký tự mới.

Phương pháp này là một cách đơn giản và hiệu quả để đảo một xâu ký tự trong JavaScript.

Stack vs Queue? ứng dụng trong các bài toán nào thực tế, ví dụ, sự giống và khác nhau, nên dung cái nào?

Stack (Ngăn xếp) và Queue (Hàng đợi)

Stack và Queue là hai cấu trúc dữ liệu cơ bản được sử dụng rộng rãi trong lập trình và có ứng dụng trong nhiều bài toán thực tế. Chúng khác nhau chủ yếu ở cách thức tổ chức và quản lý dữ liệu.

Stack

• Đặc điểm: LIFO (Last In, First Out) – phần tử cuối cùng được thêm vào là phần tử đầu tiên được lấy ra.
• Ứng dụng:
• Quản lý các hoạt động gọi hàm trong các ngôn ngữ lập trình.
• Giải bài toán đảo ngược, như đảo ngược chuỗi.
• Xử lý biểu thức toán học (ví dụ, chuyển đổi từ biểu thức infix sang postfix).
• Duyệt cây theo thứ tự sâu (Depth-First Search).

Queue

• Đặc điểm: FIFO (First In, First Out) – phần tử đầu tiên được thêm vào là phần tử đầu tiên được lấy ra.
• Ứng dụng:
• Quản lý các tiến trình trong hệ điều hành.
• Xử lý các yêu cầu trên máy chủ, như trong các hệ thống hàng đợi.
• Duyệt cây theo chiều rộng (Breadth-First Search).
• Mô phỏng hàng đợi trong thực tế, như hàng đợi tại ngân hàng.

Sự Giống và Khác Nhau

• Giống nhau: Cả hai đều là cấu trúc dữ liệu dùng để lưu trữ và quản lý dữ liệu. Trong cả hai cấu trúc, việc thêm (enqueue/push) và lấy ra (dequeue/pop) dữ liệu tuân theo một trật tự nhất định.
• Khác nhau:
• Trật tự thao tác: Stack tuân theo LIFO, trong khi Queue tuân theo FIFO.
• Ứng dụng: Stack thường được sử dụng trong các tình huống xử lý có tính chất “ngược”, còn Queue được ứng dụng trong các tình huống xử lý có tính chất “tuần tự”.

Nên Dùng Cái Nào?

• Lựa chọn phụ thuộc vào bài toán cụ thể bạn đang giải quyết:
• Sử dụng Stack khi bạn cần xử lý dữ liệu theo trật tự ngược lại hoặc cần duyệt cây/theo dõi các phần tử theo thứ tự sâu.
• Sử dụng Queue khi bạn cần xử lý dữ liệu theo thứ tự chúng được thêm vào hoặc khi mô phỏng các tình huống hàng đợi trong thực tế.

Cả hai cấu trúc này đều có vai trò quan trọng trong việc giải quyết các vấn đề lập trình và thiết kế thuật toán, và việc lựa chọn sử dụng cái nào phụ thuộc vào yêu cầu cụ thể của bài toán bạn đang đối mặt.

Xác định nhiều phần tử trùng giá trị trong mảng bất kỳ

Để xác định nhiều phần tử trùng giá trị trong một mảng bất kỳ trong JavaScript, bạn có thể sử dụng một đối tượng để lưu trữ số lần xuất hiện của mỗi phần tử. Đối với các giá trị dạng số nguyên và chuỗi, việc này khá đơn giản. Tuy nhiên, để so sánh các đối tượng, bạn cần một cách để biểu diễn chúng dưới dạng chuỗi hoặc sử dụng một phương pháp so sánh đối tượng tùy chỉnh, vì JavaScript không so sánh trực tiếp được đối tượng theo giá trị.

Dưới đây là cách bạn có thể xác định các phần tử trùng giá trị trong mảng cho cả số nguyên, chuỗi, và đối tượng:

function findDuplicates(arr) {
const elementCount = {};
const duplicates = [];
arr.forEach(item => {
// Biểu diễn đối tượng dưới dạng chuỗi JSON để so sánh
const key = typeof item === 'object' ? JSON.stringify(item) : item;
elementCount[key] = (elementCount[key] || 0) + 1;
});
for (const [key, count] of Object.entries(elementCount)) {
if (count > 1) {
// Chuyển đổi chuỗi JSON trở lại thành đối tượng nếu cần
duplicates.push(typeof arr[0] === 'object' ? JSON.parse(key) : key);
}
}
return duplicates;
}
// Ví dụ sử dụng
const arr = [1, "apple", 1, "banana", "apple", { id: 1, name: "John" }, { id: 1, name: "John" }];
console.log(findDuplicates(arr));

Trong ví dụ trên:

• Chúng tôi sử dụng JSON.stringify để biểu diễn các đối tượng dưới dạng chuỗi, cho phép chúng ta sử dụng chuỗi này làm khóa trong đối tượng elementCount. Điều này giúp so sánh giá trị của các đối tượng.
• forEach được sử dụng để duyệt qua mỗi phần tử trong mảng và đếm số lần xuất hiện của chúng.
• Cuối cùng, chúng tôi duyệt qua đối tượng elementCount để xác định những phần tử xuất hiện nhiều hơn một lần và thêm chúng vào mảng duplicates.

Lưu ý: Phương pháp này có một số hạn chế khi sử dụng JSON.stringify với đối tượng, như không xác định được sự khác biệt giữa các đối tượng có cùng cấu trúc nhưng khác tham chiếu và có thể không hoạt động đúng với các đối tượng chứa các thuộc tính có giá trị là hàm hoặc các loại đặc biệt khác.

Singly Linked List – Danh sách liên kết đơn VS Doubly Linked List – Danh sách liên kết kép ứng dụng trong các bài toán nào thực tế, ví dụ, sự giống và khác nhau, nen dung cái nào?

Singly Linked List (Danh sách liên kết đơn) và Doubly Linked List (Danh sách liên kết kép)

Cả Singly Linked List và Doubly Linked List đều là những cấu trúc dữ liệu cơ bản được sử dụng để lưu trữ một dãy các đối tượng một cách linh hoạt với khả năng thêm hoặc loại bỏ các phần tử một cách dễ dàng.

Singly Linked List

• Đặc điểm: Mỗi nút (node) chứa dữ liệu và một liên kết (link) đến nút tiếp theo trong danh sách. Không có liên kết trở lại nút trước đó.
• Ứng dụng:
• Quản lý các tác vụ trong hệ điều hành.
• Triển khai stack.
• Các ứng dụng cần dễ dàng thêm hoặc xoá các phần tử ở đầu danh sách.

Doubly Linked List

• Đặc điểm: Mỗi nút chứa dữ liệu, một liên kết đến nút tiếp theo và một liên kết đến nút trước đó. Điều này cho phép duyệt danh sách theo cả hai hướng.
• Ứng dụng:
• Triển khai các cấu trúc dữ liệu như hàng đợi (queue) và deque.
• Cần duyệt hoặc chỉnh sửa danh sách từ cả hai hướng.
• Quản lý các ứng dụng có yêu cầu cao về thao tác trên danh sách như trình duyệt web, ứng dụng soạn thảo văn bản.

Sự Giống và Khác Nhau

• Giống nhau: Cả hai đều lưu trữ dữ liệu theo dạng danh sách, cho phép thêm và loại bỏ phần tử một cách linh hoạt không cần phải dịch chuyển các phần tử như trong mảng.
• Khác nhau:
• Singly Linked List chỉ cho phép duyệt từ đầu đến cuối danh sách, làm cho việc truy cập hoặc xóa một nút ở cuối danh sách trở nên kém hiệu quả.
• Doubly Linked List cho phép duyệt từ cả hai hướng, từ đầu đến cuối hoặc ngược lại, làm tăng khả năng linh hoạt nhưng đồng thời cũng tăng chi phí bộ nhớ do cần lưu thêm liên kết đến nút trước đó.

Nên Dùng Cái Nào?

• Lựa chọn tùy thuộc vào yêu cầu cụ thể của bài toán:
• Singly Linked List thích hợp cho các ứng dụng đơn giản, nơi chỉ cần duyệt danh sách theo một hướng và không yêu cầu truy cập nhanh đến các nút trước đó.
• Doubly Linked List phù hợp với các ứng dụng phức tạp hơn, cần truy cập hoặc chỉnh sửa danh sách từ cả hai hướng, hoặc khi cần thực hiện các thao tác trên danh sách một cách linh hoạt và hiệu quả hơn.

Cả hai loại danh sách liên kết đều có những ưu và nhược điểm riêng biệt, do đó việc lựa chọn sử dụng loại nào phụ thuộc vào yêu cầu cụ thể của ứng dụng và bài toán cần giải quyết.

List video về Single LinkList :

List video về Double LinkList :

Viết một chương trình in ra màn hình dãy Fibonacci

Dãy Fibonacci là một dãy số trong đó, mỗi số là tổng của hai số trước đó. Dãy bắt đầu từ 0 và 1. Dưới đây là một chương trình JavaScript đơn giản để in ra dãy Fibonacci:

function fibonacci(n) {
let n1 = 0, n2 = 1, nextTerm;
console.log('Dãy Fibonacci:');
for (let i = 1; i <= n; i++) {
console.log(n1);
nextTerm = n1 + n2;
n1 = n2;
n2 = nextTerm;
}
}
// Gọi hàm và in dãy Fibonacci với n số đầu tiên
fibonacci(10); // Thay đổi giá trị này để in nhiều hoặc ít số hơn

Chương trình này sử dụng một vòng lặp for để tính và in ra n số đầu tiên trong dãy Fibonacci. n1 và n2 lần lượt là hai số đầu tiên trong dãy, và nextTerm được sử dụng để lưu trữ tổng của hai số này, tức là số tiếp theo trong dãy.

Bạn chỉ cần thay đổi giá trị trong lời gọi hàm fibonacci(10); để in ra số lượng số Fibonacci mà bạn muốn.

Viết chương trình kiểm tra một số có phải là Palindrome không?

Dưới đây là một chương trình JavaScript để kiểm tra xem một số có phải là palindrome không. Một số được coi là palindrome nếu nó đọc giống nhau từ trái sang phải và từ phải sang trái.

function isPalindrome(number) {
// Chuyển đổi số thành chuỗi
const str = number.toString();
// Kiểm tra chuỗi đó có giống với chuỗi đảo ngược của nó không
const reversedStr = str.split('').reverse().join('');
// So sánh và trả về kết quả
return str === reversedStr;
}
// Ví dụ
const number = 12321;
console.log(`${number} là palindrome?`, isPalindrome(number)); // true
const anotherNumber = 123456;
console.log(`${anotherNumber} là palindrome?`, isPalindrome(anotherNumber)); // false

Chương trình này hoạt động bằng cách đầu tiên chuyển đổi số được kiểm tra thành một chuỗi. Sau đó, nó tạo một chuỗi đảo ngược bằng cách sử dụng các phương thức split(), reverse(), và join() của JavaScript. Cuối cùng, nó so sánh chuỗi ban đầu với chuỗi đảo ngược để xác định xem số đó có phải là palindrome không.

Trình bày về cây nhị phân tìm kiếm – Binary search tree. sơ đồ + hình ảnh, ứng dụng trong các bài toán nào thực tế, ví dụ, sự giống và khác nhau?

Cây Nhị Phân Tìm Kiếm (Binary Search Tree – BST)

Cây nhị phân tìm kiếm là một cấu trúc dữ liệu cây, trong đó mỗi nút có tối đa hai nút con, được gọi là nút con trái và nút con phải. Cây BST có tính chất đặc biệt là giá trị của mỗi nút phải lớn hơn tất cả các giá trị trong cây con trái của nó và nhỏ hơn (hoặc bằng, tùy thuộc vào định nghĩa) tất cả các giá trị trong cây con phải của nó. Tính chất này giúp việc tìm kiếm, thêm, và xóa các phần tử trong BST trở nên hiệu quả hơn so với các cấu trúc dữ liệu không có cấu trúc.

Ứng Dụng

BST được sử dụng rộng rãi trong các bài toán thực tế như:

• Cơ sở dữ liệu: Quản lý dữ liệu có cấu trúc giúp việc tìm kiếm và cập nhật dữ liệu nhanh chóng.
• Các hệ thống tìm kiếm: Phân loại và lưu trữ thông tin để tối ưu hóa việc truy xuất dữ liệu.
• Tối ưu hóa truy xuất dữ liệu: Cung cấp cách tiếp cận hiệu quả để tìm kiếm và truy xuất dữ liệu.
• Autocomplete: Sử dụng cây Trie (một biến thể của BST) để tìm kiếm nhanh các từ khóa gợi ý.
• Cấu trúc dữ liệu trong trò chơi: Quản lý các đối tượng trong trò chơi để tối ưu hóa việc truy vấn và cập nhật trạng thái.

Sơ Đồ và Hình Ảnh

Dưới đây là mô tả sơ đồ của một cây nhị phân tìm kiếm cơ bản:

        8
/ \
3   10
/ \    \
1   6    14
/ \   /
4   7 13

Trong sơ đồ này:

• Mỗi nút chứa một giá trị.
• Nút con trái của một nút có giá trị nhỏ hơn nút đó.
• Nút con phải của một nút có giá trị lớn hơn nút đó.

Sự Giống và Khác Nhau so với Các Cấu Trúc Dữ Liệu Khác

• Giống: Giống như các cấu trúc dữ liệu cây khác, BST cho phép lưu trữ dữ liệu theo cách có cấu trúc, giúp tối ưu hóa việc truy xuất.
• Khác:
• So với cây nhị phân thông thường, BST có thêm tính chất tìm kiếm, làm cho việc tìm kiếm dữ liệu nhanh chóng và hiệu quả hơn.
• So với danh sách liên kết, BST cho phép truy xuất dữ liệu nhanh hơn với độ phức tạp thời gian trung bình là O(log n) cho các thao tác tìm kiếm, thêm, và xóa, so với O(n) của danh sách liên kết.

Đảo vị trí các phần tử trong danh sách liên kết sử dụng đệ quy và duyệt tuần tự?

Để đảo ngược một danh sách liên kết sử dụng đệ quy và duyệt tuần tự, chúng ta sẽ xem xét hai cách tiếp cận khác nhau: một là sử dụng đệ quy, và một là sử dụng duyệt tuần tự (iterative). Cả hai phương pháp này đều có cùng mục đích nhưng theo hai cách thức hoạt động khác nhau.

Đảo Ngược Danh Sách Liên Kết Sử Dụng Đệ Quy

Trong cách tiếp cận này, chúng ta sẽ “đẩy” các phần tử vào call stack thông qua các lời gọi đệ quy và sau đó “pop” chúng ra trong quá trình quay lui (backtracking), đạt được việc đảo ngược danh sách.

class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public ListNode reverseListRecursive(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseListRecursive(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}

Đảo Ngược Danh Sách Liên Kết Sử Dụng Duyệt Tuần Tự

Trong cách tiếp cận này, chúng ta sẽ sử dụng một vòng lặp để di chuyển qua danh sách liên kết từ đầu đến cuối, đảo ngược liên kết giữa các nút một cách tuần tự.

class Solution {
public ListNode reverseListIterative(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev; // prev sẽ là new head của danh sách sau khi đảo ngược
}
}

Sự Khác Biệt

• Đệ Quy:
• Dễ đọc và hiểu hơn.
• Có thể gặp vấn đề về stack overflow với danh sách liên kết rất dài do sử dụng bộ nhớ stack cho mỗi lời gọi đệ quy.
• Duyệt Tuần Tự:
• Hiệu quả hơn về mặt bộ nhớ vì không sử dụng bộ nhớ stack thêm cho mỗi lời gọi hàm.
• Cách tiếp cận này ít trực quan hơn so với đệ quy nhưng tốt hơn cho danh sách liên kết có kích thước lớn.

Lựa Chọn Phương Pháp

• Sử dụng đệ quy cho các danh sách liên kết có kích thước nhỏ đến trung bình để tận hưởng mã nguồn gọn gàng và dễ hiểu.
• Sử dụng duyệt tuần tự cho các danh sách liên kết lớn để tránh vấn đề với giới hạn độ sâu của

Cài đặt Stack trong js

Để cài đặt một Stack (Ngăn xếp) trong JavaScript, bạn có thể sử dụng một mảng để lưu trữ các phần tử. Stack là một cấu trúc dữ liệu tuân theo nguyên tắc LIFO (Last In, First Out), tức là phần tử cuối cùng được thêm vào là phần tử đầu tiên được lấy ra. Dưới đây là một ví dụ về cách cài đặt Stack sử dụng mảng trong JavaScript:

class Stack {
constructor() {
this.items = []; // Mảng để lưu trữ các phần tử trong Stack
}
// Thêm một phần tử vào đỉnh của Stack
push(element) {
this.items.push(element);
}
// Xóa và trả về phần tử ở đỉnh của Stack
pop() {
if (this.items.length == 0) {
return "Underflow"; // Stack rỗng
}
return this.items.pop();
}
// Trả về phần tử ở đỉnh của Stack mà không xóa nó
peek() {
return this.items[this.items.length - 1];
}
// Kiểm tra xem Stack có rỗng không
isEmpty() {
return this.items.length == 0;
}
// Trả về kích thước của Stack
size() {
return this.items.length;
}
// Xóa tất cả phần tử khỏi Stack
clear() {
this.items = [];
}
// In ra các phần tử của Stack
print() {
console.log(this.items.toString());
}
}
// Sử dụng Stack
const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.peek()); // 30
console.log(stack.pop()); // 30
console.log(stack.size()); // 2
stack.print(); // 10,20

Trong ví dụ trên, Stack được cài đặt với các phương thức sau:

• push(element): Thêm một phần tử vào đỉnh của Stack.
• pop(): Xóa và trả về phần tử ở đỉnh của Stack.
• peek(): Trả về phần tử ở đỉnh của Stack mà không xóa nó.
• isEmpty(): Kiểm tra xem Stack có rỗng không.
• size(): Trả về kích thước của Stack.
• clear(): Xóa tất cả phần tử khỏi Stack.
• print(): In ra các phần tử của Stack.

Cách tiếp cận này cho phép bạn quản lý một Stack một cách linh hoạt và hiệu quả trong JavaScript.

Cài đặt QUEUE trong js

Để cài đặt một Queue (Hàng đợi) trong JavaScript, bạn có thể sử dụng mảng để lưu trữ các phần tử. Queue là một cấu trúc dữ liệu tuân theo nguyên tắc FIFO (First In, First Out), tức là phần tử đầu tiên được thêm vào là phần tử đầu tiên được lấy ra. Dưới đây là một ví dụ về cách cài đặt Queue sử dụng mảng trong JavaScript:

class Queue {
constructor() {
this.items = []; // Mảng để lưu trữ các phần tử trong Queue
}
// Thêm một phần tử vào cuối Queue
enqueue(element) {
this.items.push(element);
}
// Xóa và trả về phần tử đầu tiên của Queue
dequeue() {
if (this.isEmpty()) {
return "Underflow"; // Queue rỗng
}
return this.items.shift();
}
// Trả về phần tử đầu tiên của Queue mà không xóa nó
front() {
if (this.isEmpty()) {
return "No elements in Queue";
}
return this.items[0];
}
// Kiểm tra xem Queue có rỗng không
isEmpty() {
return this.items.length === 0;
}
// Trả về kích thước của Queue
size() {
return this.items.length;
}
// Xóa tất cả phần tử khỏi Queue
clear() {
this.items = [];
}
// In ra các phần tử của Queue
print() {
console.log(this.items.toString());
}
}
// Sử dụng Queue
const queue = new Queue();
console.log(queue.isEmpty()); // true
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.front()); // 10
console.log(queue.dequeue()); // 10
console.log(queue.size()); // 2
queue.print(); // 20,30

Trong ví dụ trên, Queue được cài đặt với các phương thức sau:

• enqueue(element): Thêm một phần tử vào cuối Queue.
• dequeue(): Xóa và trả về phần tử đầu tiên của Queue.
• front(): Trả về phần tử đầu tiên của Queue mà không xóa nó.
• isEmpty(): Kiểm tra xem Queue có rỗng không.
• size(): Trả về kích thước của Queue.
• clear(): Xóa tất cả phần tử khỏi Queue.
• print(): In ra các phần tử của Queue.

Cách tiếp cận này giúp quản lý một Queue một cách linh hoạt và hiệu quả trong JavaScript, cho phép thực hiện các thao tác hàng đợi cơ bản như thêm, xóa và truy cập phần tử.

Nếu bạn nào chưa vững kiến thức về stack và queue thì đây là list video dành cho bạn nhé: