Linked List - Stack - Queue

Danh sách liên kết là một trong những cấu trúc phổ biến và thường được sử dụng để quản lý dữ liệu trong chương trình. Các cấu trúc dữ liệu này rất phong phú để tùy vào nhu cầu mà lập trình viên sẽ ứng dụng như:

• Linked list - danh sách liên kết.
• Stack - ngăn xếp.
• Queue - hàng đợi.

Linked list - danh sách liên kết

Trong các ứng dụng, danh sách liên kết là 1 cấu trúc dữ liệu linh hoạt (không bị cố định kích thước như mảng) và được sử dụng rất nhiều từ Snake (rắn săn mồi) cho đến danh sách các dòng dữ liệu khi làm việc với cơ sở dữ liệu.

Gần giống với mảng, danh sách liên kết là một chuỗi các phần tử chứa dữ liệu trong nó, nhưng khác với mảng, mỗi phần tử trong danh sách (còn được gọi là node) chứa trong nó dữ liệu cần lưu và cả dữ liệu để liên kết đến node sau nó.

Với tính cơ động của mình, danh sách liên kết được sử dụng nhiều để tổ chức các dữ liệu mà người lập trình không biết trước kích thước. Ngoài ra danh sách liên kết còn được sử dụng để tổ chức dữ liệu một cách thứ tự, chẳng hạn như Stack và Queue là những cấu trúc dữ liệu có thứ tự có thể hiện thực được từ danh sách liên kết. Ngôn ngữ C++ cũng hiện thực 1 lớp dữ liệu để xử lý danh sách liên kết hiệu quả và tiện lợi.

Stack - ngăn xếp

Khi xếp 1 chồng đĩa trong bếp, thông thường đĩa trên cùng được đặt cuối cùng và khi lấy sẽ lấy từ đĩa trên cùng đó. Đó là một hình ảnh trong thực tế của Stack.

Khi lấy đĩa từ trên cùng, hành động đó được gọi là pop, ngược lại khi để đĩa lên trên cùng được gọi là push. Một điều cần phải lưu ý khi hiện thực hóa cấu trúc dữ liệu này là Stack chỉ có thể truy cập được phần tử trên cùng của nó (chỉ có thể lấy cái đĩa trên cùng của chồng đĩa). Ngoài ra, Stack có một đặc điểm rất hay đó là thứ tự của các phần tử được đưa vào Stack sẽ là Vào trước – Ra sau. Vì những đặc điểm này của Stack cho nên chúng có một số ứng dụng sau:

• Dùng để đảo ngược 1 chuỗi các ký tự.
• Dùng để hiện thực hóa tính năng undo của phần mềm.
• Dùng để quản lý những dữ liệu mà chúng ta chỉ cần quan tâm đến phần tử được push vào sau cùng của Stack (ví dụ như quản lý State Game, trạng thái của nhân vật trong trò chơi, …).

Đối với các ngôn ngữ lập trình hiện đại, Stack cũng được hỗ trợ sẵn vì nhu cầu cao của loại cấu trúc dữ liệu này, có thể thấy được C++ cũng hiện thực 1 bộ STL trong đó có Stack cho nhiều loại cấu trúc dữ liệu hữu ích.

Queue - hàng đợi

Khi xếp hàng để mua hàng, người đến trước sẽ được thanh toán trước, người đến sau sẽ phải thanh toán sau. Đó là hình ảnh thực tế của Queue. Khi một người đi ra khỏi hàng đợi, được gọi là dequeue; khi một người bước vào xếp hàng, được gọi là enqueue. Khi quản lý dữ liệu bằng cấu trúc này, nó sẽ tạo ra sự thứ tự trong dữ liệu đưa vào, vì đặc điểm này mà Queue có một số ứng dụng sau:

• Cấu trúc hàng đợi thông điệp.
• Cấu trúc hàng đợi cho người chơi trong các trò chơi có tính năng tự tìm đối thủ.
• Cấu trúc các bộ đệm truyền tải dữ liệu.