Stack và Queue là gì ? Cấu trúc dữ liệu quan trọng cho lập trình viên

Stack

 

 

Hay còn gọi là hàng đợi một cấu trúc dữ liệu phổ biến trong lập trình. Nguyên tắc của nó là Last In First Out (Vào cuối nhưng ra trước)

 

 

Ứng dụng:

 

 

- Undo/Redo

 

 

- Browser history (forward, backward)

 

 

- Function stack in JS (callback)

 

 

Queue

 

 

Hay còn gọi là hàng đợi, cũng là một cấu trúc dữ liệu rất phổ biến trong lập trình. Khác với Stack, Queue có nguyên lý hoạt động như tên gọi của nó First In First Out (Vào trước thì ra trước)

 

 

Ứng dụng

 

 

- Máy in

 

 

- Hàng đợi

 

 

- Message queue

 

 

Tại sao nên dùng LinkedList để implement thành Stack và Queue hơn Array ?

 

 

Với Array

 

 

Với Queue

 

 

Khi thêm 1 item vào. cuối -> Độ phức tạp thường sẽ là O(1), tuy nhiên, trường hợp xâu nhất của JS (Trong JS Array là Dymanic Array, xem thêm >> Sự khác nhau giữa Static và Dynamic Arrays là gì ?) sẽ tự động phân bổ lại bộ nhớ và khi thêm vào cuối của mảng (Worst case => O(n))

 

 

Khi dequeue một phần tử đầu tiên (Xoá) sử dụng Array => Độ phức tạp là O(n) Vì các item array nếu xoá ở các phần tử đầu phải dịch chuyển lên trên

 

 

Javascript là Garbage collected language ?

 

 

Là gì ?

trannhatsang.com/2024/12/11/stack-va-queue-la-gi/

Done